删去k个数字后的最小值
8.删去k个数字后的最小值题目
给出一个整数，从该整数中去掉k个数字，要求剩下的数字形成的新整数经可能小。应该怎样选取被去掉的数字？
其中整数的长度大于或即是k，给出的整数的巨细可以高出long类型的数字范围。
举例：整数1593210，删除3个数字，新整数最小为1210；整数5674201，删除3个数字，新整数最小值为4210。
思路
上例：整数1593210，要求删除1个数字，找出最小的整数。
此时，无论删除那个数字，结果都是从7位整数，变为6位整数。既然都是6位整数，显然优先将高位的数字降低，这样对新整数的值影响最大。
但是不代表，优先删除最高位的整数，比方1593210，假如移除最高位1，结果是593210，这不是最小值，由于有193210就比593210小。
这删除一位的分析，最小值，能直接看出来，移除9是最小的，153210。但是盘算机，是不能看的，以是要找出，删除一位时的规律，才能写程序。
还是1593210，删除9得到最小值的规律。很简单，把原整数的全部数字从左到右举行比较， 假如发现某一位数字大于它右面的数字，那么在删除该数字后，一定会使该数位的值降低，由于右面比它小的数字顶替了它的位置。
1593210，删除3位的最小值。按照规律，移除9 -> 153210，移除5 -> 13210，移除3 -> 1210，1210为最小值。
这样依次求得局部最优解，最终得到全局最优解的思想，叫作贪婪算法。10549
代码
第一版
/**
* 删除整数的k个整数，获取函数后的最小值
*
* @param num 原整数
* @param k 删除数量
* @return 最小值
*/
public static String removeKDigits(String num, int k) {
String newNum = num;
for (int i = 0; i < k; i++) {
boolean hasCut = false;
//每次移除一位，保证当前步，移除1位的最小值
for (int j = 0; j < newNum.length() - 1; j++) {
//char类型 在java里可以直接比较
if (newNum.charAt(j) > newNum.charAt(j + 1)) {
newNum = newNum.substring(0, j) + newNum.substring(j + 1);//substring(i),等于substring(i,str.length())
hasCut = true;
break;
}
}
//从左往右遍历，未找到左位大于右位的数字，移除最后一位
if (!hasCut)
newNum = newNum.substring(0, newNum.length() - 1);//substring(i,j)截取范围是[i,j),i,j代表的是索引
newNum = removeZero(newNum);//移除整数左侧的数字0
}
if (newNum.length() == 0)
return "0";//所有数字都被删除，返回字符串0
return newNum;
}
private static String removeZero(String num) {
for (int i = 0; i < num.length()-1; i++) {
if (num.charAt(0) != '0')
break;
num = num.substring(1);
}
return num;
}
public static void main(String[] args) {
System.out.println(removeKDigits("1593210", 3));//1210
System.out.println(removeKDigits("301200", 1));//1200
System.out.println(removeKDigits("20", 2));//0
System.out.println(removeKDigits("5674201", 3));//4201
}第二版
上述代码，利用了2层循环，外层循环次数，就是删除的数字个数k，内存从左到右遍历全部数字。符合条件(当前位大于后一位)的数字，利用substring()函数，截取字符串，构成新字符串。代码复杂度O(kn)。
代码的功能实现正常，但是性能欠好。
[*]每次都从左往右遍历，但是由于每次删除是删除的首个满足条件的数字，以是下次，只要从上一次删除的位置开始往右遍历即可。
[*]substring()底层实现，涉及到新字符串的创建，以及字符的逐个赋值。这个方法的时间复杂度是O(n)。因此应该，避免每删除一个数字，就调用substring方法。
/**
* 删除整数的k个整数，获取函数后的最小值
*
* @param num 原整数
* @param k 删除数量
* @return 最小值
*/
public static String removeKDigits(String num, int k) {
int newLen = num.length() - k;
//使用原字符串的长度，可能会有冗余，但是是为了满足对于k==num.length()的情况，finalChar也能保存字符
char[] finalChar = new char;//默认值是'0'
int top = 0;
for (int i = 0; i < num.length(); i++) {
char c = num.charAt(i);//当前位数字字符
//finalChar代表的是上一位，c是当前位
while (top > 0 && finalChar > c && k > 0) {
top--;//保证在finalChar字符数组，当前位字符，替换左边一位
k--;//删除次数迭代
}
//top>0保证，首位一定会进入到finalChar字符数组
finalChar = c;//先进行finalChar = c赋值操作，再进行top=top+1操作
}
int offset = 0;//偏移量
while(offset < newLen && finalChar == '0')//获取最后字符数组中，首个不等于0字符的数字的索引，即是移除最后数字的左边的0
offset++;
return offset == newLen ? "0"
: new String(finalChar,offset,newLen - offset);
//使用new String(finalChar,offset,newLen - offset)，是为了去掉，左侧的'0'，和创建字符数组时的默认值'0'
}
public static void main(String[] args) {
System.out.println(removeKDigits("1593210", 3));//1210
System.out.println(removeKDigits("301200", 1));//1200
System.out.println(removeKDigits("20", 2));//0
System.out.println(removeKDigits("5674201", 3));//4201
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]