【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试【单调栈】2023C-找最小数【欧弟算法】全网注释最详细分类最全的华为OD真题题解

2023-12-13 20:56:21

题目描述与示例

题目描述

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

输入

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

输出

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

示例一

输入

2615371
4

输出

131

说明

移除 2657 这四个数字,剩下 131 按原有顺序排列组成 131 为最小值。

示例二

输入

12345
2

输出

123

示例三

输入

10345
2

输出

034

解题思路

注意,本题和LC402. 移掉K位数字完全一致。

代码

Python

# 题目:2023B-找最小数
# 分值:200
# 作者:闭着眼睛学数理化
# 算法:单调栈
# 代码看不懂的地方,请直接在群上提问


NUM1 = input()
n = int(input())
# rest_n 表示剩余的删除次数
rest_n = n

# 构建一个单调栈,
# 单调栈从栈底至栈顶单调递增
# 即大的数字放在栈顶
stack = list()

# 遍历数字字符串NUM1中的每一个字符ch
for ch in NUM1:
    # 出栈的情况:
    # 1. 栈不为空
    # 2. ch小于栈顶元素
    # 3. 剩余的删除次数大于0
    # 即可以弹出栈顶元素,这样才能使得栈顶元素尽可能小
    while len(stack) and ch < stack[-1] and rest_n > 0:
        stack.pop()
        rest_n -= 1
    # 对于每一个ch,都应该入栈
    stack.append(ch)

# 结束循环时,栈中元素不一定恰好为len(NUM1)-n
# 所以取较小的数前 len(NUM1)-n 个数组合成字符串
print("".join(stack[:len(NUM1)-n]))

Java

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String NUM1 = scanner.nextLine();
        int n = scanner.nextInt();
        
        int rest_n = n;
        Stack<Character> stack = new Stack<>();

        for (char ch : NUM1.toCharArray()) {
            while (!stack.isEmpty() && ch < stack.peek() && rest_n > 0) {
                stack.pop();
                rest_n--;
            }
            stack.push(ch);
        }

        StringBuilder result = new StringBuilder();
        int len = NUM1.length() - n;
        for (int i = 0; i < len; i++) {
            result.append(stack.get(i));
        }
        
        System.out.println(result.toString());
    }
}

C++

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
    string NUM1;
    int n;
    cin >> NUM1 >> n;

    int rest_n = n;
    stack<char> stack;

    for (char ch : NUM1) {
        while (!stack.empty() && ch < stack.top() && rest_n > 0) {
            stack.pop();
            rest_n--;
        }
        stack.push(ch);
    }

    string result;
    int len = NUM1.size() - n;
    while (!stack.empty()) {
        result = stack.top() + result;
        stack.pop();
    }
    result = result.substr(0, len);

    cout << result << endl;

    return 0;
}

时空复杂度

时间复杂度:O(M)。仅需一次遍历字符串NUM1

空间复杂度:O(M)。单调栈所占用的额外空间。

M为字符串NUM1的长度。


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

文章来源:https://blog.csdn.net/weixin_48157259/article/details/134980772
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。