原文链接
【华为OD机试 】 找最小数(C++ Java JavaScript Python)
题目描述
给一个正整数NUM1,计算出新正整数NUM2,NUM2为NUM1中移除N位数字后的结果,需要使得NUM2的值最小。
输入描述
1.输入的第一行为一个字符串,字符串由0-9字符组成,记录正整数NUM1,NUM1长度小于32。
2.输入的第二行为需要移除的数字的个数,小于NUM1长度。
输出描述
输出一个数字字符串,记录最小值NUM2。
用例
输入 | 2615371 4 |
---|---|
输出 | 131 |
说明 | 无 |
C++
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
string num1;
int removeCount;
cin >> num1;
cin >> removeCount;
vector<int> arr(num1.size());
for (int i = 0; i < num1.size(); i++) {
arr[i] = num1[i] - '0';
}
if (arr.size() == removeCount) {
cout << "0" << endl;
return 0;
}
int remainCount = arr.size() - removeCount;
vector<int> stack;
for (int i = 0; i < arr.size(); i++) {
while (!stack.empty() && removeCount > 0 && stack.back() > arr[i]) {
stack.pop_back();
removeCount--;
}
stack.push_back(arr[i]);
}
while (stack.size() > remainCount) {
stack.pop_back();
}
while (stack[0] == 0 && stack.size() != 1) {
stack.erase(stack.begin());
}
for (auto it : stack) {
cout << it;
}
cout << endl;
return 0;
}
java
import java.util.Scanner;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String num1 = sc.next();
int removeCount = sc.nextInt();
ArrayList<Integer> arr = new ArrayList<>();
for (int i = 0; i < num1.length(); i++) {
arr.add(num1.charAt(i) - '0');
}
if (arr.size() == removeCount) {
System.out.println("0");
return;
}
int remainCount = arr.size() - removeCount;
ArrayList<Integer> stack = new ArrayList<>();
for (int i = 0; i < arr.size(); i++) {
while (!stack.isEmpty() && removeCount > 0 && stack.get(stack.size()-1) > arr.get(i)) {
stack.remove(stack.size()-1);
removeCount--;
}
stack.add(arr.get(i));
}
while (stack.size() > remainCount) {
stack.remove(stack.size()-1);
}
while (stack.get(0) == 0 && stack.size() != 1) {
stack.remove(0);
}
for (int it : stack) {
System.out.print(it);
}
System.out.println();
}
}
javaScript
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.on('line', (num1) => {
rl.once('line', (removeCountInput) => {
let removeCount = Number(removeCountInput);
const arr = [...num1].map(Number);
if (arr.length === removeCount) {
console.log('0');
return;
}
const remainCount = arr.length - removeCount;
const stack = [];
for (let i = 0; i < arr.length; i++) {
while (stack.length > 0 && removeCount > 0 && stack[stack.length - 1] > arr[i]) {
stack.pop();
removeCount--;
}
stack.push(arr[i]);
}
while (stack.length > remainCount) {
stack.pop();
}
while (stack[0] === 0 && stack.length !== 1) {
stack.shift();
}
console.log(stack.join(''));
});
});
python
num1=input()
removeCount=int(input())
arr = list(map(int, num1))
if len(arr) == removeCount:
print('0')
exit()
remainCount = len(arr) - removeCount
stack = []
for i in range(len(arr)):
while stack and removeCount > 0 and stack[-1] > arr[i]:
stack.pop()
removeCount -= 1
stack.append(arr[i])
while len(stack) > remainCount:
stack.pop()
while stack[0] == 0 and len(stack) != 1:
stack.pop(0)
print(''.join(str(i) for i in stack))
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。