Saturday, July 22, 2017

[Leetcode] Remove K Digits, Solution

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.


[Thoughts]

首先分析一下什么样的数是最小的数。数总是有0~9的数字组成,高位的数字越小,这个数就越小。

所以,在对一个数做删除数字处理的时候,首先要从高位上把大的数字干掉,尽可能保留小的。

举个例子 num = "143219", k = 4

这个数字可以按照递增和递减分成三段 “1”, “4321”, “9”。递减子段上除了最后一个数字,其他的都可以被删除。

如果递减子段都处理完了,还没有删满k个,那就从最右边删(因为剩下的都是递增区间段了。)






[Code]
1:    string removeKdigits(string num, int k) {  
2:      string res = "";  
3:        
4:      for(int i =0; i<num.size(); i++) {  
5:        while(res.size()>0 && res.back() > num[i]&& k>0) {  
6:          res.pop_back();  
7:          k--;  
8:        }  
9:        res.push_back(num[i]);  
10:      }  
11:        
12:      // if k != 0, remove the digit from right  
13:      res.erase(res.size() - k, k);  
14:        
15:      // trim the zero  
16:      int i =0;  
17:      while(res[i] == '0' && i<res.size()-1) i++;  
18:        
19:      res.erase(0, i);  
20:        
21:      return res.size() == 0? "0": res;  
22:    }  


No comments: