Fork me on GitHub

Remove K Digits

Posted on

Description

https://leetcode.com/problems/remove-k-digits/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    struct cmp {
        bool operator() (pair<int, char>& left, pair<int, char>& right) {
            return left.second > right.second;
        }
    };
    string removeKdigits(string num, int k) {
        if (num.size() <= k) return string("0");
        
        //Check Zero
        int preNoZero = 0;
        int count = 0;
        int index = -1;
        for (int i = 0; i < num.size(); ++i) {
            if (num[i] == '0' && count <= k) {
                preNoZero = count;
                index = i;
            }else {
                count += 1;
            }
        }
        num.erase(0, index + 1);
        k -= preNoZero;
        
        
        int pick = num.size() - k;
        string ret;
        int last = 0;
        while (pick > 0) {
            char minum = '9' + 1;
            int targetIndex = -1;
            for (int i = last; i < num.size(); ++i) {
                if (num[i] < minum && num.size() - i >= pick) {
                    minum = num[i];
                    targetIndex = i;
                }
            }
            --pick;
            ret += minum;
            num.erase(targetIndex, 1);
            last = targetIndex;
        }
        if (ret.size() == 0) return string("0");
        return ret;
    }
};