402. Remove K Digits
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.
new solution update 2022.02.18
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| class Solution { public: string removeKdigits(string s, int k) { if(s.length() == k) return "0"; string res = ""; for(int i = 0; i < s.length(); i++) { while(res.length() > 0 and k > 0 and res.back() > s[i]) { k--; res.pop_back(); } res += s[i]; if(res == "0") res.pop_back(); } while(k and res.length()) { k--; res.pop_back(); } return res.length() == 0 ? "0" : res; } };
|
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 48 49 50 51
| class Solution { private: char getMinimum(map<char,list<int>> &chars, int maxPos) { int res = 10; for(auto p : chars) { if(!p.second.empty() && (p.first & 0b1111) < res && p.second.front() <= maxPos) res = (p.first & 0b1111); } return res | 0b110000; } public: string removeKdigits(string num, int k) { if(k == 0) return num; if(k == num.length()) return "0"; stringstream res; map<char, list<int>> chars; int pos, prev = -1, len = 0; for(pos = 0; pos <= k + 1; pos++) { chars[num[pos]].push_back(pos); }
while(len != num.length() - k) { char choosed = getMinimum(chars, k + len); for(int i = chars[choosed].front() + k; i > 0 && pos < num.length(); i--, pos++) { chars[num[pos]].push_back(pos); }
prev = chars[choosed].front();
for(auto p = chars.begin(); p != chars.end(); p++) { while(!p->second.empty() && p->second.front() <= prev) { p->second.pop_front(); } }
res<<choosed; len++; if(num.length() - prev - 1 == num.length() - k - len) { res<<num.substr(prev + 1); break; } } string ret = res.str(); for(pos = 0; pos < ret.length() && ret[pos] == '0'; pos++) {} if(pos != 0) ret = ret.substr(pos); return ret == "" ? "0" : ret; } };
|