当前位置:网站首页>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);
}
边栏推荐
猜你喜欢
随机推荐
Detailed explanation of the use of Oracle's windowing function (2)
用汇编带你看Golang里到底有没有值类型、引用类型
How to submit a PR?【OpenHarmony Growth Plan】【OpenHarmony Open Source Community】
web逆向之丁香园
Single-click to cancel the function
Auto.js中APP应用相关指令
石油化工行业商业供应链管理系统:标准化供应商管理,优化企业供应链采购流程
CGO Preliminary Cognition and Basic Data Type Conversion
ACM解题笔记——HDU 1401 Solitaire(DBFS)
Introduction to PostgreSQL
Are you hungry - Institution tree radio
PostgreSQL — 安装及常用命令
Auto.js找图找色常用功能
F. Binary String Reconstruction
sklearn 笔记 TSNE
函数:函数删除操作语法&使用例——《mysql 从入门到内卷再到入土》
B. Trouble Sort
wget编译升级故障解决
ACM模板笔记:八数码问题——使用BFS+康托展开打表解决
C. Rotation Matching