西安响应式网站开发,网站空间多少钱一年,信息手机网站模板下载软件,客户网站建设公司文章目录 题目描述与示例题目描述输入输出示例一输入输出说明 示例二输入输出 示例三输入输出 解题思路代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
给一个正整数 NUM1#xff0c;计算出新正整数 NUM2。NUM2 为 NUM1 中移… 文章目录 题目描述与示例题目描述输入输出示例一输入输出说明 示例二输入输出 示例三输入输出 解题思路代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
给一个正整数 NUM1计算出新正整数 NUM2。NUM2 为 NUM1 中移除 N 位数字后的结果需要使得 NUM2 的值最小。
输入
输入的第一行为一个字符串字符串由 0-9 字符组成记录正整数 NUM1NUM1 长度小于 32。输入的第二行为需要移除的数字的个数小于 NUM1 长度。
输出
输出一个数字字符串记录最小值 NUM2。
示例一
输入
2615371
4输出
131说明
移除 2、6、5、7 这四个数字剩下 1、3、1 按原有顺序排列组成 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;StackCharacter 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 stringusing namespace std;int main() {string NUM1;int n;cin NUM1 n;int rest_n n;stackchar 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动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
