当前位置：首页 > news >正文

【华为OD-E卷 - 114 找最小数 100分（python、java、c++、js、c）】

news 2025/6/29 5:17:05

【华为OD-E卷 - 找最小数 100分（python、java、c++、js、c）】

题目

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

输入描述

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

输出描述

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

用例

用例一：

输入：

2615371
4

输出：

python解法

解题思路：
要删除给定数字字符串中的k个字符，使得剩下的数字最小，可以采用贪心算法。具体步骤如下：

维护一个栈：用于构建最终结果，确保每次添加的数字尽可能小。

遍历每个字符：对于当前字符，若栈顶元素比它大且还有删除次数(k > 0)，则弹出栈顶元素，直到不再满足条件。这样可以保证高位尽可能小。

处理剩余删除次数：遍历完成后，若仍有删除次数未使用，则从末尾删除剩余次数对应的字符。

去除前导零：最终结果可能存在前导零，需去除。若结果为空，返回’0’。

def minimize_number(num, k):# 最终需要保留的长度length = len(num) - kstack = []for digit in num:# 当栈不为空，且还有删除次数，且栈顶数字大于当前数字时，弹出栈顶while stack and k and stack[-1] > digit:stack.pop()k -= 1stack.append(digit)# 截取前length个字符（处理剩余k的情况）result = ''.join(stack[:length])# 去除前导零，若结果为空则返回'0'return result.lstrip('0') or '0'num = input()
k = int(input())
print(minimize_number(num, k))

java解法

解题思路
使用栈模拟单调递增序列
遍历 num 的字符时，使用一个字符数组 result 来存储最终保留的数字。这个数组类似于一个单调递增栈，我们尝试让栈顶元素尽可能小。

移除较大的数字
在遍历 num 时，如果当前字符比 result 的栈顶元素小，并且还可以删除数字（toRemove > 0），那么就弹出栈顶元素（减少 toRemove 的值），从而让剩下的数字形成更小的值。

控制最终结果的长度
最终需要保留 keepLength = num.length() - toRemove 个字符，因此 result 数组的长度设为 keepLength，只允许存入 keepLength 个字符。

去除前导零
由于可能会出现前导 0，如 “10200” 移除 1 个字符后可能变成 “0200”，所以要去掉前导 0，如果去掉后字符串为空，则返回 “0”。

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String num = sc.next(); // 输入的数字字符串int toRemove = sc.nextInt(); // 需要移除的数字个数System.out.println(findSmallest(num, toRemove));}private static String findSmallest(String num, int toRemove) {// 如果需要移除的个数等于字符串长度，则返回 "0"if (num.length() == toRemove) return "0";int keepLength = num.length() - toRemove; // 需要保留的字符数char[] result = new char[keepLength]; // 结果数组（模拟栈）int pos = -1; // 当前存入 result 数组的最后一个元素位置（栈顶指针）for (char ch : num.toCharArray()) { // 遍历字符串中的每个字符// 维护单调递增栈：如果当前字符比栈顶元素小，并且还有删除名额，就弹出栈顶元素while (pos >= 0 && toRemove > 0 && result[pos] > ch) {pos--; // 退栈toRemove--; // 还需要删除的个数减少}// 只有在栈的长度不超过目标长度时，才将当前字符加入if (pos + 1 < keepLength) {result[++pos] = ch; // 入栈} else {// 如果栈已满，则直接减少 toRemove 计数toRemove--;}}// 去除前导零int start = 0;while (start < keepLength && result[start] == '0') start++;// 如果最终所有的数字都是 0，则返回 "0"return start == keepLength ? "0" : new String(result, start, keepLength - start);}
}

C++解法

解题思路
本题的目标是从一个数字字符串 num1 中移除 removeCount 个数字，使得剩下的数字形成的最小值。核心思想是使用单调递增栈，具体步骤如下：

利用双端队列（deque）作为单调递增栈

遍历 num1 的字符：
如果当前字符比 stack（单调递增栈）的栈顶元素小，并且仍然可以删除数字，就弹出栈顶元素（删除较大的数）。
这样可以确保数字整体变小。
将当前字符压入栈。
确保栈的长度符合要求

遍历结束后，如果 stack 仍然比需要保留的长度长，就继续弹出末尾元素。
去除前导零

由于可能会出现 000123 这样的情况，需要去掉前导零。
只要栈的第一个元素是 0 且长度大于 1，就不断弹出前面的 0。
返回最终的最小数字

将 stack 转换成字符串并返回。

#include <iostream>
#include <deque>
#include <string>using namespace std;// 获取移除指定个数后的最小数
string getResult(string num1, int removeCount) {// 如果需要移除的字符等于字符串长度，返回 "0"if (num1.length() == removeCount) return "0";int remainCount = num1.length() - removeCount; // 需要保留的字符数deque<char> stack; // 使用双端队列作为栈// 遍历整个字符串for (int i = 0; i < num1.length(); i++) {// 当栈非空、仍可以删除字符、栈顶元素大于当前字符时，弹出栈顶元素（保证剩下的数字尽可能小）while (!stack.empty() && removeCount > 0 && stack.back() > num1[i]) {stack.pop_back(); // 删除较大的字符removeCount--; // 递减待删除字符数}// 将当前字符压入栈stack.push_back(num1[i]);}// 若栈中元素仍然超出需要保留的个数，弹出多余的元素while (stack.size() > remainCount) {stack.pop_back();}// 去除前导零while (stack.front() == '0' && stack.size() > 1) {stack.pop_front();}// 将双端队列转换为字符串string result(stack.begin(), stack.end());return result;
}int main() {string num1;int count;getline(cin, num1); // 读取字符串cin >> count; // 读取要删除的字符个数cout << getResult(num1, count) << endl; // 输出结果return 0;
}