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

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

华为od机试

题目描述

给一个正整数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 -= 1
        stack.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;
}