删去k个数字后的最小值 - ToB企服应用市场:ToB评测及商务社交产业平台

/**
* 删除整数的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
}

复制代码

/**
* 删除整数的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[num.length()];//默认值是'0'
int top = 0;
for (int i = 0; i < num.length(); i++) {
char c = num.charAt(i);//当前位数字字符
//finalChar[top - 1]代表的是上一位，c是当前位
while (top > 0 && finalChar[top - 1] > c && k > 0) {
top--;//保证在finalChar字符数组，当前位字符，替换左边一位
k--;//删除次数迭代
}
//top>0保证，首位一定会进入到finalChar字符数组
finalChar[top++] = c;//先进行finalChar[top] = c赋值操作，再进行top=top+1操作
}
int offset = 0;//偏移量
while(offset < newLen && finalChar[offset] == '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
}

复制代码