@hanyu92 I didn't see a big runtime difference between the two implementations, as they share the common logic.
edward5
@edward5
Posts made by edward5

RE: Java AC solution, 19ms, beat 100.00%.

No one really care about integer overflow problem?
I went through a few posts about the O(n) solution. But never mentioned about the integer overflow problem. Taking hash map solution for example,
when checking left or right boundary, the solution only simply use map.containsKey(key 1) or map.containsKey(key+1) to do it. But do you think about what if the key is a Integer_MIN_VALUE or Integer_MAX_VALUE? Giving you an example, given array {2147483647, 2147483648, 2147483647}, then most of your functions would lead to an integer overflow. 
share my 4ms 4 line recursive java code
Idea is simple. I don't emphasize it anymore. Just post my code here.
public int integerReplacement(int n) { if(n == 1) return 0; if(n %2 == 0) return 1 + integerReplacement(n >>> 1); if(n == 3  (n & 3) == 1) return 1 + integerReplacement(n1); return 1 + integerReplacement(n+1); }

RE: Java AC solution, 19ms, beat 100.00%.
Brilliant solution! I made a bit modification based on your version of code and shared it here:
public List<String> addOperators(String num, int target) { List<String> ans = new ArrayList<String>(); backtrack(num, 0, (long) target, 0, 0, ans, new char[2*num.length()], 0); return ans; } private void backtrack(String num, int idx, long tar, long val, long pre, List<String> ans, char[] res, int len) { if(idx == num.length() && tar == val) ans.add(new String(res, 0, len)); int j = idx==0? len : len+1; long x = 0; for(int i = idx; i < num.length(); i++) { x = x*10 + (num.charAt(i)  '0'); if(x < 10 && iidx > 0) break; // stop when leading zero found res[j++] = num.charAt(i); if(idx == 0){ backtrack(num, i+1, tar, val+x, x, ans, res, j); continue; } res[len] = '+'; backtrack(num, i+1, tar, val+x, x, ans, res, j); res[len] = ''; backtrack(num, i+1, tar, valx, x, ans, res, j); res[len] = '*'; backtrack(num, i+1, tar, valpre+pre*x, pre*x, ans, res, j); } }

RE: This is a typical monotonic queue problem
@liji94188
descList.remove(0) is O(n) time complexity, not O(1) 
My 5ms java solution without Stack and Deque, beats 98% of solutions
First to first, there is no stack or deque used in my solution. The only thing I did is just to transfer original string into char array.
My idea is:
Key: Use a counter to count how many times ".." appears before we handle a normal string of part of the path. go through the char array from end to start
 ignore all '/' characters
 get string between '/'
 handle this string in 4 branches:
4.a if it is empty or equals to ".", do nothing
4.b if it is equals to "..", counter++
4.c if the counter is greater than 0, then counter
4.d else ( counter == 0) do concatenation of result with current part of path.
My code:
public String simplifyPath(String path) { String ans = ""; char[] chars = path.toCharArray(); int i = chars.length  1; // a counter to count how many times ".." shows up int count = 0; while ( i >=0) { int j = i; while( j >= 0 && chars[j] == '/') j; int k = j; while(k >=0 && chars[k] != '/') k; String part = String.valueOf(chars, k+1, jk); if (part.isEmpty()  part.equals(".")){ // do nothing } // count appearence of ".." else if(part.equals("..")) count++; // ignore current part, //because there is ".." after it else if (count > 0) count; // count == 0, no need to ignore current part // and do result concatenation else ans = "/" + part + ans; i = k; } return ans.isEmpty()? "/" : ans; }

Why "000" is not considered as a test case?
Obviously, "000" is also a string that meets additive number requirements. However, it is not shown up in the test cases.
My code gives a false result for this specific case which would be true by default. But my code could still pass all test cases. I think someone should add it into test cases. 
Anyone tried divide Integer.MIN_VALUE by Integer.MAX_VALUE?
what happens when you do this calculation? Anyone tried to do it? I ran this case in leetcode, unfortunately, it could not show me a correct result.

RE: Simple Divide and Conquer AC solution without Segment Tree
This solution has a better runtime rather than that one with O(n) complexity and stack