做PHP网站前端网站进不去,怎么在网站上做按钮,网站地域分站怎么做,酒店网站开发合同/*** 题目#xff1a;给定一个数#xff0c;求 删除k个数字后的最小值* 思路#xff1a;考虑 “如何删除一个数字#xff0c;得到最小值”#xff0c;* 不难想到#xff0c;应该优先删除“靠前#xff0c;值大”的数字#xff0c;* 观察到#xff1a;如果一个数字大于… /*** 题目给定一个数求 删除k个数字后的最小值* 思路考虑 “如何删除一个数字得到最小值”* 不难想到应该优先删除“靠前值大”的数字* 观察到如果一个数字大于它右边的那个数字那么删除它并让自己右边的数顶替上来必然能够降低整体的数值* 综上分析可知从左向右遍历找到第一个“自己右边比自己小”的数字*/public static void main(String[] args) {System.out.println(removeKDigits2(1000270936,1));}public static String removeKDigits2(String s,int k){String ress;for (int i 0; i k; i) {// 准备删除第i1个数只删除一个数boolean hasCutfalse;// 检查 在res[0,...,res.len-2]中的字符是否被删除for (int j 0; j res.length()-1; j) {if(res.charAt(j)res.charAt(j1)){hasCuttrue;resres.substring(0,j)res.substring(j1);break;}}if(!hasCut){// 在res[0,...,res.len-2]中的字符都没有被删除那么删除最后一个字符resres.substring(0,res.length()-1);}resremoveLeft0s(res);// 删完一个数后检查左边的0}if(res.length()0){// 删完了我觉得没必要加啊return ;}return res;}private static String removeLeft0s(String res) {int i0;for(;ires.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 slens.length();char[] stacknew char[slen-k];// stack, ready to store the remaining numsint top0;for (int i 0; i slen; i) {char cs.charAt(i);while (k0top0stack[top-1]c){ // !! 栈顶元素是stack[top-1]top--;k--;}stack[top]c;}int offset0;// 记录第一个非零数字的位置for (int i 0; i stack.length; i) {if(stack[i]!0){break;}offset;}
// System.out.println(stack);return offsetstack.length?0:new String(stack,offset,stack.length-offset);}
