返回目录

题目描述

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

输入描述

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

输出描述

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

示例：

解题思路

维护一个单调递增的栈来实现移除数字

1. 初始化一个空栈 stack，用于存储需要保留的数字。
2. 遍历输入的正整数 NUM1 中的每个字符。
3. 对于当前字符，检查栈顶元素是否大于当前字符，如果是，则出栈并减少需要移除的数字个数。这样可以确保移除的数字使得新正整数 NUM2 的值最小。
4. 将当前字符入栈。
5. 遍历完成后，如果仍有需要移除的数字个数，从栈顶开始移除剩余的数字。
6. 将栈中的字符连接成一个字符串，去除前导零，输出结果。如果结果为空，则输出 “0”。

Python算法源码

# Python 3

# 导入处理标准输入/输出的必要模块
import sys

# 定义一个函数来处理输入并执行所需操作
def main():
    # 读取输入：一串数字和需要移除的数字个数
    num = input()
    k = int(input())

    # 初始化一个空栈来存储数字
    stack = []

    # 遍历输入字符串中的每个数字
    for i in num:
        # 当栈不为空、需要移除数字大于 0 且栈顶元素大于当前数字时，
        # 弹出栈顶元素并减少需要移除的数字的计数
        while stack and k > 0 and stack[-1] > i:
            k -= 1
            stack.pop()
    
        # 将当前数字添加到栈中
        stack.append(i)

    # 将栈转换为字符串，移除前导零
    result = ''.join(stack[:len(stack) - k]).lstrip('0') or '0'

    # 打印结果
    print(result)

# 调用主函数开始程序执行
if __name__ == "__main__":
    main()

C语言算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    // 读取输入的正整数 NUM1 和需要移除的数字个数
    char num[1000];
    int k;
    scanf("%s %d", num, &k);

    // 使用一个数组作为栈来存储结果
    char stack[1000];
    int top = -1;

    // 遍历输入的数字字符串
    for (int i = 0; num[i] != '\0'; i++) {
        char digit = num[i];
        // 当栈非空、k 大于 0 且栈顶元素大于当前数字时，弹出栈顶元素并减小 k
        while (top >= 0 && k > 0 && stack[top] > digit) {
            top--;
            k--;
        }
        // 将当前数字压入栈中
        stack[++top] = digit;
    }

    // 构建结果字符串，移除多余的 k 个数字
    stack[top + 1 - k] = '\0';

    // 删除结果字符串中的前导零
    int start = 0;
    while (stack[start] == '0') {
        start++;
    }

    // 如果结果为空，则输出 "0"
    if (stack[start] == '\0') {
        printf("0\n");
    } else {
        // 输出结果
        printf("%s\n", stack + start);
    }

    return 0;
}

Java算法源码

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        // 读取输入的正整数 NUM1 和需要移除的数字个数
        Scanner scanner = new Scanner(System.in);
        String num = scanner.next();
        int k = scanner.nextInt();
      
        // 使用一个栈来存储结果
        Stack<Character> stack = new Stack<>();
      
        // 遍历输入的数字字符串
        for (char i : num.toCharArray()) {
            // 当栈非空、k 大于 0 且栈顶元素大于当前数字时，弹出栈顶元素并减小 k
            while (!stack.isEmpty() && k > 0 && stack.peek() > i) {
                k--;
                stack.pop();
            }
            // 将当前数字压入栈中
            stack.push(i);
        }
      
        // 构建结果字符串，移除多余的 k 个数字
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty() && k > 0) {
            stack.pop();
            k--;
        }
        for (char ch : stack) {
            result.append(ch);
        }
      
        // 删除结果字符串中的前导零
        int start = 0;
        while (start < result.length() && result.charAt(start) == '0') {
            start++;
        }
      
        // 如果结果为空，则输出 "0"
        if (start == result.length()) {
            System.out.println("0");
        } else {
            // 输出结果
            System.out.println(result.substring(start));
        }
    }
}