《漫画算法》笔记——给定数,求删除k个数字后的最小值
2023-12-21 23:57:32
/**
* 题目:给定一个数,求 删除k个数字后的最小值
* 思路:考虑 “如何删除一个数字,得到最小值”,
* 不难想到,应该优先删除“靠前,值大”的数字,
* 观察到:如果一个数字大于它右边的那个数字,那么删除它并让自己右边的数顶替上来,必然能够降低整体的数值;
* 综上分析,可知:从左向右遍历,找到第一个“自己右边比自己小”的数字
*/
public static void main(String[] args) {
System.out.println(removeKDigits2("1000270936",1));
}
public static String removeKDigits2(String s,int k){
String res=s;
for (int i = 0; i < k; i++) {// 准备删除第i+1个数,只删除一个数
boolean hasCut=false;// 检查 在res[0,...,res.len-2]中的字符是否被删除
for (int j = 0; j < res.length()-1; j++) {
if(res.charAt(j)>res.charAt(j+1)){
hasCut=true;
res=res.substring(0,j)+res.substring(j+1);
break;
}
}
if(!hasCut){// 在res[0,...,res.len-2]中的字符都没有被删除,那么删除最后一个字符
res=res.substring(0,res.length()-1);
}
res=removeLeft0s(res);// 删完一个数后,检查左边的0
}
if(res.length()==0){// 删完了,我觉得没必要加啊
return "";
}
return res;
}
private static String removeLeft0s(String res) {
int i=0;
for(;i<res.length();i++){
if(res.charAt(i)!='0'){
break;
}
}
return res.substring(i);
}
上述代码实现的缺点:
- 每次删除一个字符,都从剩余字符串的头部开始遍历,这样之前做的“是否存在逆序”检查结果就浪费了。比较节省的思路是,应该考虑接住上次检查的结果,继续进行。
.substring()
的底层实现比较费:创建新字符串,并逐个复制字符。
基于这些缺点,提出使用栈实现上述的思路。具体地,每次遍历到一个新字符,检查它是否大于栈顶,如果是,那么直接把这个新字符压入栈;如果否,那么弹出栈顶(表示删除这个栈顶字符,更新删除次数)。
- 下面的代码借助
char[] stack
和int top
实现了栈的功能,(之所以这样做,我想,是因为后续方便打印出结果)、使用int offset
标记第一个非零数字的位置。
public static String removeKDigits3(String s,int k){
int slen=s.length();
char[] stack=new char[slen-k];// stack, ready to store the remaining nums
int top=0;
for (int i = 0; i < slen; i++) {
char c=s.charAt(i);
while (k>0&&top>0&&stack[top-1]>c){ // !! 栈顶元素是stack[top-1]
top--;
k--;
}
stack[top++]=c;
}
int offset=0;// 记录第一个非零数字的位置
for (int i = 0; i < stack.length; i++) {
if(stack[i]!='0'){
break;
}
offset++;
}
// System.out.println(stack);
return offset==stack.length?"0":new String(stack,offset,stack.length-offset);
}
文章来源:https://blog.csdn.net/qq_43448491/article/details/135141165
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!