題目： LeetCode - 402. Remove K Digits

題目說明

給一個字串及一個整數 k，字串代表一個整數，求刪除 k 個數字後，結果是最小的數字。

解題思路

  • 想法： 由於數字比大小是從高位往低位比，所以我們的目的是讓高位數盡可能的小。

  • 解法一： 定義一個字串 res，遍歷 num，若是 res 的最後一位數比現在遍歷到的元素大，就刪除最後一位數，直到已經刪除了 k 個數字，或是 res 已經刪除光了。最後再 res.resize(digits)，因為我們只需要 digits 位數，而後面的數字一定會比前面的大，所以直接刪除掉後面的數字。最後如果 res 前面是 0 的話就把 0 拿掉即可。

  • 解法二： 和解法一類似，只是在放入的時候就判斷是否有 leading zero 的情況。

  • 解法三： 和解法二相同，只是不再定義新的字串，而是將直接將結果存在 num 裡面。

參考解法

解法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string removeKdigits(string num, int k) {
        int n = num.size();
        if(n == k)
            return "0";
        int digits = n - k;
        string res;
        for(auto i : num)
        {
            while(k && !res.empty() && res.back() > i)
                res.pop_back(), --k;
            res.push_back(i);
        }
        // 避免結果太長
        res.resize(digits);
        while(!res.empty() && res.front() == '0')
            res.erase(res.begin());
        return res.empty() ? "0" : res;
    }
};

解法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string removeKdigits(string num, int k) {
        int n = num.size();
        if(n == k)
            return "0";
        string res;
        for(auto i : num)
        {
            while(k && !res.empty() && res.back() > i)
                res.pop_back(), --k;
            if(!res.empty() || i != '0')
                res.push_back(i);
        }
        while(k--)
            res.pop_back();
        return res.empty() ? "0" : res;
    }
};

解法三：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string removeKdigits(string num, int k) {
        int n = num.size();
        if(n == k)
            return "0";
        int size = 0;
        for(auto i : num)
        {
            while(k && size && num[size - 1] > i)
                --size, --k;
            if(size || i != '0')
                num[size++] = i;
        }
        num.resize(size - k);
        return num.empty() ? "0" : num;
    }
};