网站域名过期怎么办,网站设计是什么意思,温州企业网站制作,wordpress是php吗【华为OD-E卷 - 找最小数 100分#xff08;python、java、c、js、c#xff09;】
题目
给一个正整数NUM1#xff0c;计算出新正整数NUM2#xff0c;NUM2为NUM1中移除N位数字后的结果#xff0c;需要使得NUM2的值最小
输入描述
输入的第一行为一个字符串#xff0c;字…【华为OD-E卷 - 找最小数 100分python、java、c、js、c】
题目
给一个正整数NUM1计算出新正整数NUM2NUM2为NUM1中移除N位数字后的结果需要使得NUM2的值最小
输入描述
输入的第一行为一个字符串字符串由0-9字符组成记录正整数NUM1NUM1长度小于32。 输入的第二行为需要移除的数字的个数小于NUM1长度
输出描述
输出一个数字字符串记录最小值NUM2
用例
用例一
输入
2615371
4输出
131python解法
解题思路要删除给定数字字符串中的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])# 去除前导零若结果为空则返回0return result.lstrip(0) or 0num 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) {// 如果需要移除的个数等于字符串长度则返回 0if (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则返回 0return 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 stringusing namespace std;// 获取移除指定个数后的最小数
string getResult(string num1, int removeCount) {// 如果需要移除的字符等于字符串长度返回 0if (num1.length() removeCount) return 0;int remainCount num1.length() - removeCount; // 需要保留的字符数dequechar 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;
}
C解法 解题思路
更新中JS解法 解题思路
更新中注意
如果发现代码有用例覆盖不到的情况欢迎反馈会在第一时间修正更新。 解题不易如对您有帮助欢迎点赞/收藏
