leetcode402-移掉K位数字

原题

给定一个以字符串表示的非负整数 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/

发表评论

电子邮件地址不会被公开。