当前位置:网站首页>LeetCode-402 - Remove K digits
LeetCode-402 - Remove K digits
2022-08-10 21:27:00 【z754916067】
题目
思路
- It feels useless to sort the numbers,Backtracking should be used for circular comparisons.
- wrote a backtrace,超出时间限制了…Backtracking is indeed time-complex,记录一下,润去题解
//targetHow many numbers to remove for the target nowHow many digits to delete for the current charfor the last deleted character For backtracking
public void Back(StringBuilder nownum,int target,int now){
if(target==now){
//比较两个字符串的大小 不能直接转 length will exceed
//赋给ans
ans = Compare(nownum.toString(),ans);
return;
}//Otherwise start subtracting
for(int i=0;i<nownum.length();i++) {
StringBuilder sb = new StringBuilder(nownum);
Back(sb.deleteCharAt(i), target, now + 1);
}
}
- Traverse the string from left to right,for each element traversed,See if you need to selectively discard the previous adjacent elements,因为对于aabbce来说,就可以判断aabbc好,还是aabbe好
- 需要注意的是,If you encounter a monotonically increasing number,Then you will always choose not to discard,But the meaning of the question must be discardedk个,为了解决这个问题,You need to let it go every time you throw it awayk减去1,That is, a discard is completed,减到0traversal can be terminated,Because enough has been lostk次了.
- 但也有可能,遍历结束后k还没有减到0,It can be reserved at this timen-kthe meaning of the numbers,So after traversal select beforen-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++){
//弹出栈顶 It compares which is put on the stack
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);
}
边栏推荐
- Oracle 的开窗函数使用详解(二)
- sklearn 笔记 TSNE
- Auto.js中的悬浮窗
- Detailed explanation of the use of Oracle's windowing function (2)
- 直播课堂系统08-腾讯云对象存储和课程分类管理
- Live Classroom System 08-Tencent Cloud Object Storage and Course Classification Management
- Live Classroom System 08 Supplement - Tencent Cloud Object Storage and Course Classification Management
- Uniapp编译后小程序的代码反编译一些思路
- 【PCBA方案设计】蓝牙跳绳方案
- npm WARN config global `--global`, `--local` are deprecated. Use `--location=global` instead.
猜你喜欢
我的世界整合包 云服务器搭建方法(ECS)
玩转doxygen 之RT-THREAD
LeetCode-36-二叉搜索树与双向链表
Redis 性能影响 - 异步机制和响应延迟
Future与CompletableFuture
Live Classroom System 08 Supplement - Tencent Cloud Object Storage and Course Classification Management
npm warn config global `--global`, `--local` are deprecated. use `--location=global` instead.
找的笔试题的复盘(一)
日期选择器组件(限制年份 设定仅展示的月份)
华为路由器旁挂引流实验(使用流策略)
随机推荐
优化是一种习惯●出发点是'站在靠近临界'的地方
化学制品制造业数智化供应链管理系统:建立端到端供应链采购一体化平台
数字化转型:如何引导创新领导者
ACM模板笔记:最长不下降/上升子序列
论文解读(g-U-Nets)《Graph U-Nets》
kuberentes Auditing 入门
Live Classroom System 08-Tencent Cloud Object Storage and Course Classification Management
第五届“强网杯”全国网络安全挑战赛(线上赛)
mysql性能监控与执行计划
Huawei router clock near the drainage experiment (using stream strategy)
第四届红帽杯网络安全大赛
Application of Spatial 3D Model Reconstruction Based on Pix4Dmapper - Spatial Analysis and Site Selection
日期选择器组件(限制年份 设定仅展示的月份)
apr_thread使用内存之谜
组合导航精度分析
直播课堂系统08补-腾讯云对象存储和课程分类管理
C. Social Distance
姜还是老的辣,看看老战哥的老底儿和严谨劲儿
PPT的两个实用技巧
paddle 35 paddledetection保存训练过程中的log信息