找最小数 - 华为OD统一考试(E卷)

2024华为OD机试（E卷+D卷+C卷）最新题库【超值优惠】Java/Python/C++合集

题目描述

给一个正整数NUM1，计算出新正整数NUM2，NUM2为NUM1中移除N位数字后的结果需要使得NUM2的值最小。

输入描述

输入的第一行为一个字符串，字符串由0-9字符组成，记录正整数NUM1，NUM1长度小于32。
输入的第二行为需要移除的数字的个数，小于NUM1长度。

输出描述

输出一个数字字符串，记录最小值NUM2。

示例1

输入：
2615371
4输出：
131说明：

示例2

输入：输出：说明：

题解

问题分析

这道题可以归类为贪心算法。目标是在尽量靠左的地方删除比后面大的数字，使得剩下的数字更小。删除操作中优先考虑移除高位的数字，尽量保持低位数字小。

解题的基本思路：

使用一个栈来存储字符。
从左到右遍历数字字符串，如果当前数字比栈顶的数字小且还可以删除数字，就弹出栈顶数字。
遍历完成后，如果删除的数字还不够，则继续从后向前删除栈顶数字。
最后，将栈中剩下的数字拼接成结果，并移除前导零。

时间复杂度

时间复杂度为O(n)，因为每个数字最多进出栈一次。
空间复杂度为O(n)，用于存储栈中的数字。

Java

import java.util.Scanner;
import java.util.Stack;
/*** @author code5bug*/
public class Main {public static String removeDigits(String num, int k) {Stack<Character> stack = new Stack<>();for (char digit : num.toCharArray()) {while (!stack.isEmpty() && k > 0 && stack.peek() > digit) {stack.pop();k--;}stack.push(digit);}// 如果 k 还大于 0，继续从栈顶删除while (k > 0) {stack.pop();k--;}// 构建结果StringBuilder result = new StringBuilder();for (char digit : stack) {if (!(result.length() == 0 && digit == '0')) { // 去掉前导零result.append(digit);}}// 如果结果为空，则返回 "0"return result.length() == 0 ? "0" : result.toString();}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取控制台输入String num = scanner.nextLine();int k = scanner.nextInt();// 计算并输出结果System.out.println(removeDigits(num, k));}
}

Python

def remove_digits(num: str, k: int) -> str:stack = []for digit in num:while stack and k > 0 and stack[-1] > digit:stack.pop()k -= 1stack.append(digit)# 如果 k 还大于 0，继续从后面弹出while k > 0:stack.pop()k -= 1# 去掉前导零result = ''.join(stack).lstrip('0')# 如果结果为空，返回 '0'return result if result else '0'if __name__ == "__main__":# 从控制台读取输入num = input()k = int(input())# 输出结果print(remove_digits(num, k))

C++

#include <iostream>
#include <vector>using namespace std;int main() {string num;int k;cin >> num >> k;vector<char> stack;for (char ch: num) {while (!stack.empty() && stack.back() > ch && k > 0) {stack.pop_back();k--;}stack.push_back(ch);}// 还可以删除数字则继续删除while (!stack.empty() && k > 0) {stack.pop_back();k--;}string result;for (char c: stack) {// 确保 result 不是 0 前导的数字字符串if (result.empty() && c == '0')continue;result += c;}cout << (result.empty() ? "0" : result) << endl;return 0;
}