当前位置:网站首页>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);
}
边栏推荐
猜你喜欢
随机推荐
svg+元素js实现在图片上描点成框,并获取相对图片的坐标位置
【Windows】你不能访问此共享文件夹,因为你组织的安全策略阻止未经身份验证的来宾访问,这些策略可帮助保护你的电脑
JS中的filter、map、reduce
B. Same Parity Summands
C. Rotation Matching
日期选择器组件(限制年份 设定仅展示的月份)
OPPO Enco X2 迎来秋季产品升级 旗舰体验全面拉满
Detailed explanation of the use of Oracle's windowing function (2)
Kubernetes Notes / Getting Started / Production Environment / Installing Kubernetes with Deployment Tools / Starting a Cluster with kubeadm / Creating a Cluster with kubeadm
流程控制结构——《mysql 从入门到内卷再到入土》
PostgreSQL — 安装及常用命令
基于Pix4Dmapper的运动结构恢复法无人机影像三维模型重建
金鱼哥RHCA回忆录:CL210OpenStack操作的故障排除--章节实验
【实用软件】【VSCode】使用技巧大全(持续更新)
优雅退出在Golang中的实现
Detailed explanation and use of each module of ansible
npm‘ 不是内部或外部命令,也不是可运行的程序 或批处理文件
Knowledge map Knowledge Graph
ACM模板笔记:最长不下降/上升子序列
MySQL查询数据库中的表和字段