原题
给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。
注意:
- num 的长度小于 10002 且 ≥ k。
- num 不会包含任何前导零。
示例 1:
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2:
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。789
示例 3 :
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字,剩余为空就是0。
解法
思想
要在一个长度为length的字符数组中去掉k位,留下一个最小数字,则是要留下一个length-k位的数字,我们每一次都要保证在剩余位数充足的情况下选择最小的数字。
对于示例一,"1432219"
要选出7-3=4
位数字,我们可以保留最后三位,在前五位中选出一个最小数字1,然后在剩下的"432219"
中选出3位数字,我们可以保留最后两位,在前四位中选出一个最小数字2,然后在剩下的"219"
中选出2位数字,我们可以保留最后一位,在前两位中选出一个最小数字1,然后在剩下的"9"
中选出1位数字,选取9。
得到的结果就是"1219"
代码
class Solution {
public String removeKdigits(String num, int k) {
char[] nums = num.toCharArray();
int start = 0;//下一次选取数字开始的位置
int min = 0;
int origink = k;
char[] result = new char[nums.length-k];//保存结果
while(k<nums.length){
for(int i = start;i<k+1;i++){//保留有限位数,选取最小数字
if(nums[i]<nums[min]){
min = i;
}
}
result[k-origink] = nums[min];
k++;
start = min+1;
min = start;
}
for(int i = 0;i<=result.length;i++){//去除开头的0
if(i==result.length)
return "0";
if(result[i]!='0'){
result = Arrays.copyOfRange(result,i,result.length);
break;
}
}
return String.valueOf(result);
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode402-%e7%a7%bb%e6%8e%89k%e4%bd%8d%e6%95%b0%e5%ad%97/