即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

leetcode:Remove K Digits

编程语言 Ray_sysu 15℃ 0评论

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个数字来获得最小的结果。这里采用贪心算法的思想,先来考虑如何去掉1位数字来获得最小的结果。我最开始想的是去掉最大的一个数字,后来发现这个思路有问题。举例来说,12219,去掉1位我们应该去掉哪个?去掉2,变成1219;去掉9,变成1221.显然,去掉2结果更小一些。然而2是处在一个什么位置上呢?

2是这个数字从左往右检索的第一个“峰值”。意思是说,他比前一个数字大,也比后面一个数字大。去掉这种值,获得的结果最小。去掉k个数字,可以理解为去掉1个数字的操作执行k次。

所以最初的代码是这样的:

string removeKdigits(string num, int k) {


        while (k > 0) {                                                                   //连续去掉k个数


            int n = num.size();


            int i = 0;


            while (i+1

            num.erase(i, 1);


            k–;


        }


        int s = 0;


        while (s<(int)num.size()-1 && num[s]=='0')  s++;            //去掉数字开头处(最左边)的0


        num.erase(0, s);


       


        return num==”” ? “0” : num;                                             //若全部去掉则返回0而不是空


    }

查询了一些资料,发现还有一种时间复杂度上更加简单的办法。利用栈,也就是说,将num的每一个数字分别入栈,同时检索“峰值”,若检索到那个值则不入栈,同时确认栈顶元素是不是新的“峰值”,不是则继续执行,避免了上述代码一次次从头检索。代码如下:

string removeKdigits(string num, int k) {


        string res;


        int keep = num.size() – k;


        for (int i=0; i

            while (res.size()>0 && res.back()>num[i] && k>0) {


                res.pop_back();


                k–;


            }


            res.push_back(num[i]);


        }


        res.erase(keep, string::npos);


        


        int s = 0;


        while (s<(int)res.size()-1 && res[s]=='0')  s++;


        res.erase(0, s);


       


        return res==”” ? “0” : res;


    }

这道题的核心就是利用贪心算法,将去掉k个数字的复杂情况转化为去掉1个数字的简单情况。

个人见解,如有错误请读者留言赐教。




转载请注明:CodingBlog » leetcode:Remove K Digits

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情