Spiral Matrix

Similar to Spiral Matrix II. Just a little change since matrix here is m-by-n size.


Below is my algorithm.:

 public class Solution {  
   public List<Integer> spiralOrder(int[][] matrix) {  
     ArrayList<Integer> res = new ArrayList<Integer>();  
     if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return res;  
     int row = matrix.length;  
     int col = matrix[0].length;  
     int end = row*col;  
     int m = 1,i = 0, j = 0, times = 0;  
     while(m <= end){  
       for(j = i; (j <= col - 1 - times) && ( m <= end) ; j++){ res.add(matrix[i][j]); m ++;} j--;  
       for(i++; i <= row - 1 - times && m <= end; i++){ res.add(matrix[i][j]); m ++;} i--;  
       for(j--; (j >= times) && (m <= end); j--){ res.add(matrix[i][j]); m ++;} j++;  
       for(i--; i >= times+1 && m <= end; i--){ res.add(matrix[i][j]); m ++;} i++;  
       times ++;  
     }  
     return res;  
   }  
 }  

Single Number

Thanks Wei for suggesting this problem to me. This is a very tricky, but simple question. People may not think of the approach at first glance. Once it came to your mind, then remaining thing become much easier.

For XOR operation, one rule we need to know is: x^y=y^x. Order DOES NOT matter.

Check out my code below:

 public class Solution {  
   public int singleNumber(int[] A) {  
     if(A.length == 0) return 0;  
     int tmpRes = A[0];  
     for(int i = 1; i < A.length; i++){  
       tmpRes ^= A[i]; //x^y = y^x, so x ^ y ^ ~x ^ z ^ ~y = x ^ ~x ^ y ^ ~y ^ z = 0 ^ 0 ^ z = z  
     }  
     return tmpRes;  
   }  
 }  

And also thank Code_Ganker for his alternative solutions. Brilliant! His algorithm:

 public int singleNumber(int[] A) {  
   int[] digits = new int[32];  
   for(int i=0;i<32;i++)  
   {  
     for(int j=0;j<A.length;j++)  
     {  
       digits[i] += (A[j]>>i)&1;// get cumulative sum on each bit  
     }  
   }  
   int res = 0;  
   for(int i=0;i<32;i++)  
   {  
     res += (digits[i]%2)<<i;  
   }  
   return res;  
 }  

Substring with Concatenation of All Words

Honestly, this question is not very difficult, but its AC rate is not that low. Logic is simple and easy to understand. Check out my code below, and if any questions, please let me know.

 public class Solution {  
   public ArrayList<Integer> findSubstring(String S, String[] L) {  
     if(S == null || L == null){  
       return null;  
     }  
     int strLen = L[0].length();  
     if (strLen == 0) return null;  
     HashMap<String,Integer> wordsMap = new HashMap<String,Integer>();  
     ArrayList<Integer> resultIdx = new ArrayList<Integer>();  
     //for(int i = 0; i < L.length; i ++) wordsMap.put(L[i],1);  
     initialMap(wordsMap,L);  
     for(int i = 0;i <= S.length() - strLen * L.length;i ++){  
       String currentStr = S.substring(i,i+strLen * L.length);  
       if(check(currentStr,wordsMap,strLen)) {  
         resultIdx.add(i);  
         //i += strLen * L.length;  
       }  
         //i++;  
         initialMap(wordsMap,L);  
     }  
     return resultIdx;  
   }  
   public void initialMap(HashMap<String, Integer> wordsMap, String[] L){  
     wordsMap.clear();  
     for(int i = 0; i < L.length; i ++) {  
     if(!wordsMap.containsKey(L[i])) wordsMap.put(L[i],1);  
     else {  
         int val = wordsMap.get(L[i]);  
         val ++;  
         // wordsMap.remove(L[i]);  
         wordsMap.put(L[i],val);  
       }    
     }  
   }  
   public boolean check(String currentStr, HashMap<String, Integer> wordsMap, int strLen){  
     for(int i = 0;i <= currentStr.length() - strLen;i += strLen){  
       String cmpntStr = currentStr.substring(i,i+ strLen);  
       if(wordsMap.containsKey(cmpntStr)){  
         int val = wordsMap.get(cmpntStr);  
         val--;  
         if(val < 0) return false;  
         wordsMap.put(cmpntStr,val);  
       }  
       else{  
         return false;  
       }  
     }  
     return true;  
   }  
 }  

Maximum Depth of Binary Tree

Very simple, just get the max depth. But one confusing thing is that depth of root should be 0, and height of leaf should be 0. For understanding about depth and height, please check this link out:

http://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height

But the AC answer shows that if there is only one root, maximum depth of this tree is 1. Need to discuss about this with my friend. 

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public int maxDepth(TreeNode root) {  
     if(root == null) return 0;  
     int maxDepthVal = 0;  
     maxDepthVal = Math.max(maxDepthVal, Math.max(maxDepth(root.right),maxDepth(root.left)) + 1 );  
     return maxDepthVal;  
   }  
 }