当前位置:网站首页>LeetCode-402-移掉K位数字
LeetCode-402-移掉K位数字
2022-08-10 20:54:00 【z754916067】
题目
思路
- 感觉给数字排序没有用,应该使用回溯进行循环比较。
- 写了一个回溯,超出时间限制了…回溯确实时间复杂度也高,记录一下,润去题解
//target为目标删除多少数字 now为当前删除多少数字 char为上次删除字符 为了进行回溯
public void Back(StringBuilder nownum,int target,int now){
if(target==now){
//比较两个字符串的大小 不能直接转 长度会超过
//赋给ans
ans = Compare(nownum.toString(),ans);
return;
}//否则开始减
for(int i=0;i<nownum.length();i++) {
StringBuilder sb = new StringBuilder(nownum);
Back(sb.deleteCharAt(i), target, now + 1);
}
}
- 对字符串进行从左至右的遍历,对每一个遍历到的元素,看是否需要选择性丢弃之前的前面相邻的元素,因为对于aabbce来说,就可以判断aabbc好,还是aabbe好
- 需要注意的是,如果碰见一个单调递增的数字,那么会永远选择不丢弃,但题意要求必须丢弃k个,为了解决这个问题,每次丢弃的时候要需要让k减去1,即完成一次丢弃,减到0的时候可以终止遍历,因为已经丢够k次了。
- 但也有可能,遍历结束后k还没有减到0,此时可以保留n-k的数字的意思,所以遍历后选取前n-k个即可。
代码
public String removeKdigits(String num, int k) {
int remain = num.length()-k;
//创建stack用来接收
Stack<Character> cs = new Stack<>();
for(int i=0;i<num.length();i++){
//弹出栈顶 与其比较将哪个放入栈中
while(k!=0 && !cs.isEmpty() && cs.peek()>num.charAt(i)){
cs.pop();
k-=1;
}
cs.push(num.charAt(i));
}
//取前n-k个
StringBuilder ans = new StringBuilder();
while(!cs.isEmpty()) ans.append(cs.pop());
String ans1 = ans.reverse().substring(0,remain);
//删除前导0
int nums=0;
for(int i=0;i<ans1.length();i++){
if(ans1.charAt(i)=='0') nums++;
else break;
}
if(nums==ans1.length()) return "0";
else return ans1.substring(nums);
}
边栏推荐
猜你喜欢
The use of TortoiseSVN little turtle
关于 NFT 版权保护的争议
apr_thread使用内存之谜
【CMU博士论文】视频多模态学习:探索模型和任务复杂性,152页pdf
【golang map】 深入了解map内部存储协议
ACM模板笔记:最长不下降/上升子序列
ACM解题笔记——HDU 1401 Solitaire(DBFS)
JS中的filter、map、reduce
带你一文读懂SaaS版多租户商城系统对多品牌企业的应用价值
Future-oriented IT infrastructure management architecture - Unified IaaS
随机推荐
ArcPy读取Excel时序数据、批量反距离加权IDW插值与掩膜
ACM模板笔记:八数码问题——使用BFS+康托展开打表解决
Single-click to cancel the function
Detailed explanation and use of each module of ansible
C. Social Distance
测试代码新的规则
大小端的理解以及宏定义实现的理解
mysql性能监控与执行计划
TortoiseSVN小乌龟的使用
每次打开chrome会跳出What's new
A fullGC problem troubleshooting caused by groovy
2021DASCTF实战精英夏令营暨DASCTF July X CBCTF 4th
PostgreSQL — 安装及常用命令
win10 xbox录屏功能不能录声音怎么办
paddle 35 paddledetection保存训练过程中的log信息
MATLAB神经网络拟合工具箱Neural Net Fitting使用方法
The use of TortoiseSVN little turtle
卡片盒笔记法的操作步骤
B. Same Parity Summands
F. Binary String Reconstruction