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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月28日
下一篇 2020年1月29日

相关推荐

  • leetcode41-缺失的第一个正数

    原题 给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3…

    算法 2020年5月11日
    0130
  • leetcode403-青蛙过河

    原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。 给定石子的位置列表(用单…

    算法 2020年6月16日
    04630
  • 剑指offer44-数字序列中某一位的数字

    原题(来源Leetcode) 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位…

    算法 2020年6月15日
    02900
  • leetcode278-第一个错误的版本

    原题 你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。 假…

    算法 2020年1月2日
    090
  • leetcode700-二叉搜索树中的搜索

    原题 给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。 例如, 给定二叉搜索树…

    算法 2020年1月16日
    0100
  • leetcode202-快乐数

    原题 编写一个算法来判断一个数是不是“快乐数”。 一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无…

    算法 2019年12月18日
    0120
  • leetcode92-反转链表

    原题 https://leetcode.cn/problems/reverse-linked-list-ii/description 题解 头插法 /** * Definition…

    算法 2024年3月28日
    0100
  • leetcode135-分发糖果

    原题 老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。 你需要按照以下要求,帮助老师给这些孩子分发糖果: 每个孩子至少分配到 1 个…

    算法 2020年2月17日
    060
  • leetcode410-分割数组的最大值

    原题 给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。 注意:数组长度 n 满足以下条件: 1…

    算法 2020年1月9日
    0690
  • 剑指offer05-替换空格

    原题(来源Leetcode) 请实现一个函数,把字符串 s 中的每个空格替换成"%20"。 示例1: 输入: s = "We are happy." 输出: "We%20are%2…

    算法 2020年4月5日
    0110

发表回复

登录后才能评论