## Wednesday, September 21, 2016

### LeetCode 402 - Remove K Digits

https://leetcode.com/problems/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.
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.
```
X. Using Ordered Stack
Use StringBuilder as stack
https://discuss.leetcode.com/topic/59580/short-10-lines-o-n-java-code
``````    public static String removeKdigits(String num, int k) {
StringBuilder sb = new StringBuilder();
for(char c : num.toCharArray()) {
while(k > 0 && sb.length() != 0 && sb.charAt(sb.length() - 1) > c) {
sb.setLength(sb.length() - 1);
k--;
}
if(sb.length() != 0 || c != '0') sb.append(c);  // Only append when it is not leading zero
}
if(k >= sb.length()) return "0";
sb.setLength(sb.length() - k);  // use all remaining k
return sb.toString();
}``````
setLength(len -1) O(1)
```public void setLength(int newLength) {
if (newLength < 0)
throw new StringIndexOutOfBoundsException(newLength);    ensureCapacityInternal(newLength);
if (count < newLength) {
Arrays.fill(value, count, newLength, '\0');    }

count = newLength;}```
Use array as stack
https://discuss.leetcode.com/topic/59412/a-greedy-method-using-stack-o-n-time-and-o-n-space
https://discuss.leetcode.com/topic/59501/6ms-java-solution-with-detailed-comment
``````    public String removeKdigits(String num, int k) {
int digits = num.length() - k;
char[] stk = new char[num.length()];
int top = 0;
// k keeps track of how many characters we can remove
// if the previous character in stk is larger than the current one
// then removing it will get a smaller number
// but we can only do so when k is larger than 0
for (int i = 0; i < num.length(); ++i) {
char c = num.charAt(i);
while (top > 0 && stk[top-1] > c && k > 0) {
top -= 1;
k -= 1;
}
stk[top++] = c;
}
// find the index of first non-zero digit
int idx = 0;
while (idx < digits && stk[idx] == '0') idx++;
return idx == digits? "0": new String(stk, idx, digits - idx);
}``````
http://www.cnblogs.com/grandyang/p/5883736.html
http://blog.csdn.net/qq508618087/article/details/52584133

http://www.voidcn.com/blog/yeqiuzs/article/p-6204756.html
``````    public String removeKdigits(String num, int k) {
int len = num.length();
//corner case
if(k==len)
return "0";

Stack<Character> stack = new Stack<>();
int i =0;
while(i<num.length()){
//whenever meet a digit which is less than the previous digit, discard the previous one
while(k>0 && !stack.isEmpty() && stack.peek()>num.charAt(i)){
stack.pop();
k--;
}
stack.push(num.charAt(i));
i++;
}

// corner case like "1111"
while(k>0){
stack.pop();
k--;
}

//construct the number from the stack
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty())
sb.append(stack.pop());
sb.reverse();

//remove all the 0 at the head
while(sb.length()>1 && sb.charAt(0)=='0')
sb.deleteCharAt(0);
return sb.toString();
}``````
https://discuss.leetcode.com/topic/59646/straightforward-java-solution-using-stack
```public String removeKdigits(String num, int k) {
Stack<Integer> stack = new Stack<Integer>();
if (num.length() == 0 || num.length() <= k)
return "0";

for (int i = 0; i < num.length(); i++) {
int cur = num.charAt(i) - '0';
while (!stack.isEmpty() && cur < stack.peek()
&& num.length() - i - 1 >= (num.length() - k) - stack.size()) {
stack.pop();
}
if (stack.size()<num.length()-k)
stack.push(cur);
}

StringBuilder res = new StringBuilder();
while (!stack.isEmpty())
res.insert(0, stack.pop());

while (res.length() > 0 && res.charAt(0) == '0')
res.deleteCharAt(0);

if (res.length() == 0)
return "0";
return res.toString();
}```
http://www.cnblogs.com/grandyang/p/5883736.html

```    string removeKdigits(string num, int k) {
string res = "";
int n = num.size(), keep = n - k;
for (char c : num) {
while (k && res.size() && res.back() > c) {
res.pop_back();
--k;
}
res.push_back(c);
}
res.resize(keep);
while (!res.empty() && res[0] == '0') res.erase(res.begin());
return res.empty() ? "0" : res;
}```
http://blog.csdn.net/mebiuw/article/details/52576884
* 这是一个非常简单的问题，贪心解决法 * 即 removeKdigits(num,k) = removeKdigits(removeKdigits(num,1),k-1) * 进行最多K轮的删除，每次从头开始寻找一位删除： * 1、要么第二位是0，这样相当于至少删了两位，很值得，必须这么做 * 2、不然，找到第一个出现下降转折的位置 删除 * */ public String removeKdigits(String num, int k) { int n; while(true){ n = num.length(); if(n <= k || n == 0) return "0"; if(k-- == 0) return num; if(num.charAt(1) == '0'){ int firstNotZero = 1; while(firstNotZero < num.length() && num.charAt(firstNotZero) == '0') firstNotZero ++; num=num.substring(firstNotZero); } else{ int startIndex = 0; while(startIndex < num.length() - 1 && num.charAt(startIndex) <= num.charAt(startIndex + 1)) startIndex ++; num=num.substring(0,startIndex)+num.substring(startIndex+1); } } }

X.

def removeKdigits(self, num, k): """ :type num: str :type k: int :rtype: str """ size = len(num) ans = '0' numd = collections.defaultdict(collections.deque) for i, n in enumerate(num): numd[n].append(i) p = 0 for x in range(size - k): for y in '0123456789': while numd[y] and numd[y][0] < p: numd[y].popleft() if numd[y] and numd[y][0] <= k + x: p = numd[y][0] ans += y numd[y].popleft() break return str(int(ans))

X.  https://discuss.leetcode.com/topic/59871/two-algorithms-with-detailed-explaination
The first algorithm is straight-forward. Let's think about the simplest case: how to remove 1 digit from the number so that the new number is the smallest possible？ Well, one can simply scan from left to right, and remove the first "peak" digit; the peak digit is larger than its right neighbor. One can repeat this procedure k times, and obtain the first algorithm:
``````string removeKdigits(string num, int k) {
while (k > 0) {
int n = num.size();
int i = 0;
while (i+1<n && num[i]<=num[i+1])  i++;
num.erase(i, 1);
k--;
}
int s = 0;
while (s<(int)num.size()-1 && num[s]=='0')  s++;
num.erase(0, s);

return num=="" ? "0" : num;
}``````

String findMin(String s, k){}
e.g.
input
s=pineapple, k==3,

output: ale
ale is the lexical order smallest subsequnce of length 3.

1. find the first occur position of distinct char.
2. then start from that position.
3. dfs to find lenght==3, subsequence(dfs, combination way); . visit 1point3acres.com for more.
4. find the one with smallest lexical order.

pop的时候需要看后面还剩几个元素了

f->e->d->c->cb->cba
1. public class Solution {
2.         鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
3.         public String removeKdigits(String num, int k) {. 1point3acres.com/bbs
4.         if(num == null || num.length() == 0) return num;
5.         int len = num.length();. 1point3acres.com/bbs
6.         if(len == k) return "";
7.         Stack<Character> stack = new Stack<Character>();
8.         char []ch = num.toCharArray();
9.         int i = 0, n = num.length();
10.         while(i < len){

11.             while(!stack.isEmpty() && stack.size() + n-i > k &&  stack.peek() > ch[i]){
12.                 stack.pop();
13.             }.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
14.             stack.push(ch[i++]);
16.
17.         // handle corner case 1111 or 1234, when k = 2. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
19.             stack.pop();
20.         }
21.
22.         StringBuilder sb = new StringBuilder();
23.         while(!stack.isEmpty()). Waral 鍗氬鏈夋洿澶氭枃绔�,
24.           sb.insert(0, stack.pop());
25.
26.         return sb.toString();
27.
28.     }

29.         public static void main(String[] args) {.鏈枃鍘熷垱鑷�1point3acres璁哄潧
30.                 Solution s = new Solution();
31.                 String str="xyzabc";
32.                 int k=3;
33.                 System.out.println(s.removeKdigits(str, k));
34.         }. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
35. }