What if we consider reflection and rotation(for simplicity we just consider 90, 180, 270 degrees). the key point is how to encode an island so that we easily find its corresponding reflection and rotations. Any suggestion will be appreciated.
panzw
@panzw
Posts made by panzw

What if we consider reflection / rotation? Any good ideas?

RE: BFS Acc Solution (Java and C# code)
@chu4 the condition can be used for pretermination. In BFS, we use
levelmin
to record the min value of each level, whenlevelmin > min
. we don't need to search further because all nodes below will be>= levelmin
. we just need to return secondmin we have seen so far.
This is a little trivial, because the worst case time complexity is stillO(N)
. 
RE: Very simple Java solution
nice use of TreeSet to keep elements in ascending order.

RE: BFS Acc Solution (Java and C# code)
@vonzcy, good point, This program will fail on the test case [2147483646,2147483647], you can use a boolean flag to indicate whether all nodes in the tree have the same value, like this:
public int findSecondMinimumValue(TreeNode root) { if(root == null) return 1; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int min = root.val; int secondMin = Integer.MAX_VALUE; boolean allsame = true; while(!queue.isEmpty()){ int size = queue.size(); int levelmin = Integer.MAX_VALUE; for(int i = 0; i< size; i++){ TreeNode node = queue.poll(); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); levelmin = Math.min(levelmin, node.val); if(node.val != min){ secondMin = Math.min(secondMin, node.val); allsame = false; } } if(levelmin > min) return secondMin; } if(allsame) return 1; return secondMin; }

RE: Java Solution, DFS + BFS
Thanks for sharing, but I have one confusion why stop further DFS when a cell is not a 'B'. I know this can prevent exploring unintended cell. Is there any reason behind this?

RE: In fact most solution was wrong, they can't pass this case
@Beserious said in In fact most solution was wrong, they can't pass this case:
900000000
because 900000000 is not a valid input in terms of overflow. The result is 2281451810. The expected answer in OJ is 2147483647.

RE: 8 lines slide window solution in Java
Same idea, added some comments.
public class Solution { public boolean checkInclusion(String s1, String s2) { int[] map = new int[26]; int sum = s1.length(); // construct frequency map for(int i = 0; i< s1.length(); i++){ map[s1.charAt(i)  'a']++; } for(int r = 0, l = 0; r < s2.length(); r++){ char c = s2.charAt(r); if(map[c  'a'] > 0){ map[c  'a']; sum; //check for permutation match. if(sum == 0) return true; }else{ // if there is enough number for char c or c is never seen before. // we move left pointer next to the position where we first saw char c // or to the r+1(we never see char c before), //and during this process we restore the map. while(l<= r && s2.charAt(l) != s2.charAt(r)){ map[s2.charAt(l)  'a'] ++; l++; sum++; } l++; } } return false; } }

RE: Share some of my ideas.
@jiangxu87
I got the similar idea with you about proving the second point. Basically we use contradiction. Say iftotal gas  total cost >= 0
there is no solution. that means from any gas station we can't travel around circuit.
we can randomly pick a station to start, eggas station i
, we know it will stops at somewhere saygas station j
(j is the last station that is reachable from i). For this interval i to j we knowsum from i to j (gas[x]  cost[x]) < 0
. Next we start fromgas station j + 1
, it will also stops at somewhere say k, we also havesum from j+1 to k (gas[x]  cost[x]) <0
. we repeat this process until we already travel a circle.
We pick out those nonoverlapped intervals but also can fully form the circle.
Based on our analysis, if we sum the value ofinterval total gas  interval total cost
for these segments . we gottotal gas  total cost < 0
, which contradicts our assumption. 
RE: Accepted Java simple solution in 8 lines
@vegito2002 Thanks, you are right. I wish I can give you more upvotes. By the way how did you get
O(NlgN)
for best case? It seems that master theorem can not applied there. But it is not hard to see(N/2) * lgN > T(N/2)
. So we can getT(N) = O(NlgN)
. 
RE: Accepted Java simple solution in 8 lines
@eaglesky But the max_length_of_each_path and max_number_of_leaves can not be achieved at the same time, if max_length_of_each_path is O(n) then in this case the max_number_of_leaves is O(1), if max_number_of_leaves = O(n) then in this case max_number_of_leaves is O(log(n)).