网站名查询,wordpress引用轮播图文件,店铺设计方案,张家港建网站费用转载自 漫画#xff1a;删去k个数字后的最小值 我们来举一个栗子#xff1a;
给定整数 541270936#xff0c;要求删去一个数#xff0c;让剩下的整数尽可能小。
此时#xff0c;无论删除哪一个数字#xff0c;最后的结果都是从9位整数变成8位整数。既然同样是8位整数删去k个数字后的最小值 我们来举一个栗子
给定整数 541270936要求删去一个数让剩下的整数尽可能小。
此时无论删除哪一个数字最后的结果都是从9位整数变成8位整数。既然同样是8位整数我们显然应该优先把高位的数字降低这样对新整数的值影响最大。 如何把高位的数字降低呢很简单我们把原整数的所有数字从左到右进行比较如果发现某一位的数字大于它右面的数字那么在删除该数字后必然会使得该数位的值降低因为右面比它小的数字顶替了它的位置。
在咱们这个例子中数字5右侧的数字4小于5所以删除数字5最高位数字降低成了4。 /*** 删除整数的k个数字获得删除后的最小值* param num 原整数* param k 删除数量*/public static String removeKDigits(String num, int k) {String numNew num;for(int i0; ik; i){boolean hasCut false;//从左向右遍历找到比自己右侧数字大的数字并删除for(int j0; jnumNew.length()-1;j){if(numNew.charAt(j) numNew.charAt(j1)){numNew numNew.substring(0, j) numNew.substring(j1,numNew.length());hasCut true;break;}}//如果没有找到要删除的数字则删除最后一个数字if(!hasCut){numNew numNew.substring(0, numNew.length()-1);}//清除整数左侧的数字0numNew removeZero(numNew);}//如果整数的所有数字都被删除了直接返回0if(numNew.length() 0){return 0;}return numNew;}private static String removeZero(String num){for(int i0; inum.length()-1; i){if(num.charAt(0) ! 0){break;}num num.substring(1, num.length()) ;}return num;}public static void main(String[] args) {System.out.println(removeKDigits(1593212,3));System.out.println(removeKDigits(30200,1));System.out.println(removeKDigits(10,2));System.out.println(removeKDigits(541270936,3));}
小灰的代码使用了两层循环外层循环基于删除次数k内层循环从左到右遍历所有数字。
当遍历到需要删除的数字时利用字符串的自身方法subString() 把对应数字删除并重新拼接字符串。
显然这段代码的时间复杂度是Okn。 结果提交以后...... 翻译过来就是恭喜你打败了16.56%的小伙伴 1.每一次内层循环都需要从头遍历所有数字
比如给定的整数是 11111111111114132我们在第一轮循环中需要遍历大部分数字一直遍历到数字4发现41从而删除4。
以目前的代码逻辑下一轮循环中我们要从头开始遍历再次重复遍历大部分数字一直遍历到数字3发现32从而删除3。
事实上我们应该停留在上一次删除的位置继续进行比较。而不是从头开始。
2.subString方法本身性能不高
subString方法的底层实现涉及到了新字符串的创建以及逐个字符的拷贝。这个方法自身的时间复杂度是On。
因此我们应该避免在每删除以后数字后就调用subString方法。 /*** 删除整数的k个数字获得删除后的最小值* param num 原整数* param k 删除数量*/public static String removeKDigits(String num, int k) {//新整数的最终长度 原整数长度 - kint newLength num.length() - k;//创建一个栈用于接收所有的数字char[] stack new char[num.length()];int top 0;for (int i 0; i num.length(); i) {//遍历当前数字char c num.charAt(i);//当栈顶数字大于遍历到的当前数字栈顶数字出栈相当于删除数字while (top 0 stack[top-1] c k 0) {top - 1;k - 1;}//遍历到的当前数字入栈stack[top] c;}// 找到栈中第一个非零数字的位置以此构建新的整数字符串int offset 0;while (offset newLength stack[offset] 0) {offset;}return offset newLength? 0: new String(stack, offset, newLength - offset);}public static void main(String[] args) {System.out.println(removeKDigits(1593212,3));System.out.println(removeKDigits(30200,1));System.out.println(removeKDigits(10,2));System.out.println(removeKDigits(541270936,3));}
代码中非常巧妙地运用了栈的特性在遍历原整数的数字时让所有数字一个个入栈当某个数字需要删除时让该数字出栈。最后程序把栈中的元素转化为字符串结果。
我们仍然以整数 541270936k3 为例
遍历到数字5数字5入栈 遍历到数字4发现栈顶54栈顶5出栈数字4入栈 遍历到数字1发现栈顶41栈顶4出栈数字1入栈 继续遍历数字2数字7依次入栈。 遍历数字0发现栈顶70栈顶7出栈数字0入栈 此时k的次数已经用完无需再比较剩下的数字一口气入栈 此时栈中的元素就是最终的结果。
代码只对所有数字遍历了一趟遍历的时间复杂度是On而后把栈转化为字符串的时间复杂度也是On所以最终的时间复杂度是On。
同时程序中利用栈来回溯遍历过的数字以及删除数字所以程序的空间复杂度是On。 leetcode原题链接如下有兴趣的小伙伴可以自己尝试哦
https://leetcode.com/problems/remove-k-digits/description/
