union find is elegant, but I still didn't get how to detect if there are multiple trees in it instead of a single tree?
gracesrm
@gracesrm
Posts made by gracesrm

RE: AC Java UnionFind solution

RE: Java solution  O(n^2) DP with some explanations
Why do you only check c=='.'  c==s.charAt(i1) without s.charAt(i1)=='.' ?

Why do I get TLE with O(n) solution?
I found two solutions in the discuss. Both of them are O(n) time complexity. The first one got TLE but the second one got AC. Can anyone explain on why the second solution is faster than the first one?
First Solution:
public int trap(int[] height) { if(height == null  height.length<3){ return 0;} int low= 0, high= height.length1; int maxLeft= 0, maxRight=0; int res= 0; while(low <= high){ maxLeft= Math.max(maxLeft, height[low]); maxRight= Math.max(maxRight, height[high]); if(maxLeft < maxRight){ res+= (maxLeft  height[low]); low++; }else{ //maxLeft > maxRight res+= (maxRight  height[high]); high; } } return res; }
Second Solution (dp):
public int trap(int[] height) { int len = height.length; if(len == 0) return 0; int[] maxleft = new int[len]; int[] maxright = new int[len]; int max = Integer.MIN_VALUE; for(int i=0;i<len;i++){ if(height[i] > max){ max = height[i]; } maxleft[i] = max; } max = Integer.MIN_VALUE; for(int i=len1;i>=0;i){ if(height[i] > max){ max = height[i]; } maxright[i] = max; } int ret = 0; for(int i=0;i<len;i++){ int diff = Math.min(maxleft[i],maxright[i])  height[i]; if(diff > 0) ret += diff; } return ret; }

RE: Why the expected result for "bbcaac" is "bca", not "bac"?
thanks for the quick reply.
but i don't think "acdb" is a substring of "cbacdcbc".
I know "a" and "d" appear only once, and "d" should go after "a". To make it smaller, "a" should go before "c" and "b", then how can I decide the position of "c" and "b" compared to "d"? They appeared both before and after "d". 
RE: Why the expected result for "bbcaac" is "bca", not "bac"?
what is smallest lexicographical order?
Given "cbacdcbc"
Return "acdb"why not return "abcd"?

RE: Easy to understand doubleheap solution in Java
What's the time complexity in adding a new number? Is that O(log N)?

RE: My Java Solution
You used a nodeKey map but what if the node has duplicate values?

Error: cannot find symbol: class SortedMap
My code is in the following:
public class NumArray { private SortedMap<Integer,Integer> map; public NumArray(int[] nums) { map= new TreeMap<>(); int sum= 0; for(int i=0; i< nums.length; i++){ sum+= nums[i]; map.put(i, sum); } } void update(int i, int val) { int diff_value= val map.get(i); map.put(i, val); SortedMap<Integer, Integer> subMap= map.subMap(i+1, map.size()); for(Integer index: subMap.keySet()){ int old_value= map.get(index); map.put(index, old_value+ diff_value); } } public int sumRange(int i, int j) { int prev = (i1>=0? map.get(i1): 0); return map.get(j) prev; } }
I got Compile Error of
Line 3: error: cannot find symbol: class SortedMap
Please ignore the code, it exceeds time limit.

RE: Java Solution using the Restoring Division Algorithm
Hi, may I know what does ">>>" mean in line " P = P  (A & (1 << 31)) >>> 31;" ?