[LeetCode] Remove K Digits 去掉K位数字

简介:

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

这道题让我们将给定的数字去掉k位,要使得留下来的数字最小,这题跟LeetCode上之前那道Create Maximum Number有些类似,可以借鉴其中的思路,如果n是num的长度,我们要去除k个,那么需要剩下n-k个,我们开始遍历给定数字num的每一位,对于当前遍历到的数字c,进行如下while循环,如果res不为空,且k大于0,且res的最后一位大于c,那么我们应该将res的最后一位移去,且k自减1。当跳出while循环后,我们将c加入res中,最后我们将res的大小重设为n-k。根据题目中的描述,可能会出现"0200"这样不符合要求的情况,所以我们用一个while循环来去掉前面的所有0,然后返回时判断是否为空,为空则返回“0”,参见代码如下:

class Solution {
public:
    string removeKdigits(string num, int k) {
        string res = "";
        int n = num.size(), keep = n - k;
        for (char c : num) {
            while (k && res.size() && res.back() > c) {
                res.pop_back();
                --k;
            }
            res.push_back(c);
        }
        res.resize(keep);
        while (!res.empty() && res[0] == '0') res.erase(res.begin());
        return res.empty() ? "0" : res;
    }
};

本文转自博客园Grandyang的博客,原文链接:去掉K位数字[LeetCode] Remove K Digits ,如需转载请自行联系原博主。

相关文章
|
算法
LeetCode 423. Reconstruct Original Digits
给定一个非空字符串,其中包含字母顺序打乱的英文单词表示的数字0-9。按升序输出原始的数字。
123 0
LeetCode 423. Reconstruct Original Digits
LeetCode 402. Remove K Digits
给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。
83 0
LeetCode 402. Remove K Digits
LeetCode 258. Add Digits
给定一个非负整数 num,反复将各个位上的数字相加,直到结果为一位数。
74 0
LeetCode 258. Add Digits
LeetCode 203. Remove Linked List Elements
删除链表中等于给定值 val 的所有节点。
79 0
LeetCode 203. Remove Linked List Elements
|
存储 前端开发 算法
LeetCode只出现一次的数字使用JavaScript解题|前端学算法
LeetCode只出现一次的数字使用JavaScript解题|前端学算法
145 0
LeetCode 19. 删除链表的倒数第N个节点 Remove Nth Node From End of List
LeetCode 19. 删除链表的倒数第N个节点 Remove Nth Node From End of List
|
算法 PHP
力扣(LeetCode)算法题解:1365. 有多少小于当前数字的数字
力扣(LeetCode)算法题解:1365. 有多少小于当前数字的数字
142 0
|
算法 PHP
力扣(LeetCode)算法题解:1323. 6 和 9 组成的最大数字
力扣(LeetCode)算法题解:1323. 6 和 9 组成的最大数字
140 0
|
算法 PHP
力扣(LeetCode)算法题解:1295. 统计位数为偶数的数字
力扣(LeetCode)算法题解:1295. 统计位数为偶数的数字
118 0
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number