54. Updated

[YongLAGCC]

54. Spiral Matrix

Layer by Layer

Time Complexity: O(N)O(N), where NN is the total number of elements in the input matrix

Space Complexity: O(N)O(N), the information stored in list.

错误点： 因为第三个for loop， col > col1. 所以最后一个for loop，row = row2， 而不是 = row2 - 1。

另外注意 if condition， 非常的重要。

class Solution { public List spiralOrder(int[][] matrix) { List ans = new ArrayList<>(); if(matrix.length == 0) return ans;

    int row = matrix.length - 1; 
    int col = matrix[0].length -1; 
    int nr = 0, nc = 0; 

    while(nr <= row && nc <= col) {

        for(int c = nc; c <= col; c++) {
            ans.add(matrix[nr][c]);
        }
        for(int r = nr+1; r <= row; r++) {
            ans.add(matrix[r][col]);
        }
        if(nr < row && nc < col){
            for(int c = col-1; c > nc; c--) {
                ans.add(matrix[row][c]);
            }
            for(int r = row; r > nr; r--) {
                ans.add(matrix[r][nc]);
            }
        }
        row--;
        col--;
        nr++; 
        nc++; 
    }
     return ans;     
}

}

[YongLAGCC]

Two pointers. 4：50 -4: 58PM

Time Complexity: O(m + n);

Space Complexity: O(1);

错误点：while loop condition.

class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int sum = m + n - 1; int len1 = m - 1; int len2 = n - 1;

    while(len1 >= 0 && len2 >=0 )
    {
        nums1[sum--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
    }
     System.arraycopy(nums2, 0, nums1, 0, len2 + 1);  

}

}

[YongLAGCC]

242. Valid Anagram

Time complexity is O(n) because accessing the counter is constant

Space complexity: O(1)

错误点， 最后一个for loop出了错误， 用了的 s.length() 和arr[s.charAt(j) !-=0.

class Solution { public boolean isAnagram(String s, String t) { if(s.length() != t.length()) return false;

    int [] arr = new int [26]; 

    for(int i = 0; i < s.length(); ++i){
        arr[s.charAt(i) - 'a']++;
        arr[t.charAt(i) - 'a']--;
    }
    for(int j = 0; j < arr.length; ++j) {
        if(arr[j] != 0)
            return false; 
    }
    return true; 
}

}

[YongLAGCC]

Time complexity: O(N). the number N of digits in the input.

Space complexity: O(1) since the output is just a string.

错误点： StringBuilder 和 helper() 需要留心细节。 还有nothing方程 细节

class Solution {

        String below20 [] = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    String tens[] = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

public String numberToWords(int num) {

    if(num == 0) return "Zero";      
    return nothing(num);

}

public String nothing(int num){

    StringBuilder sb = new StringBuilder(); 

    if(num / 1000000000 > 0)
    {
        sb.append(helper(num / 1000000000));
        sb.append(" Billion ");
        if(num % 1000000000 == 0)
        {
            return sb.toString().trim(); 
        }
        sb.append(nothing(num % 1000000000));

    }
    else if(num / 1000000 > 0)
    {
        sb.append(helper(num / 1000000) ); 
        sb.append(" Million ");
        if(num % 1000000 == 0)
        {
            return sb.toString().trim(); 
        }
        sb.append(nothing(num % 1000000) ); 

    }
  else if(num / 1000 > 0) {
        sb.append(helper (num/ 1000) ); 
        sb.append(" Thousand "); 
        if(num % 1000 == 0) 
            return sb.toString().trim(); 
        sb.append(helper(num % 1000)); 
      }
     else {
          sb.append(helper(num) );

    }
    return sb.toString(); 
}
public String helper(int num){
    StringBuilder sb = new StringBuilder(); 
   if(num == 0) return ""; 
   if(num < 20) sb.append(below20[num]);

   else if(num < 100)
    {
       sb.append(tens[num/10]);
       if(num % 10 > 0)
           sb.append(" ");
        sb.append(below20[num % 10]);

    }
    else {
        sb.append(below20[num / 100] );
        sb.append(" Hundred ");
        sb.append(helper(num % 100));
    }
 return sb.toString().trim();    
}

}

[YongLAGCC]

Sort Characters By Frequency

Time Complexity : O(nlogn)， sorted。 String to list， O（n) etc.

Space Complexity : O(n).

错误： 想法单一， 目标逻辑条理不够，for loop 逻辑不够清晰 （需重来）

： Lambda funtion comparsion 不熟

class Solution { public String frequencySort(String s) { if(s == "" || s.length() == 0) return s;

    char input [] = s.toCharArray(); 

    Arrays.sort(input); 
    List<String> list = new ArrayList<>(); 

    StringBuilder sb = new StringBuilder(); 
    sb.append(input[0]);

    for(int i = 1; i < input.length; ++i)
    {
        if(input[i] != input[i - 1])
        { 
            list.add(sb.toString()); 
            sb = new StringBuilder(); 
        }
        sb.append(input[i]); 

    }
    list.add(sb.toString());  

  Collections.sort(list, (a, b) -> b.length() - a.length());

    StringBuilder ans = new StringBuilder(); 
    for(String str: list) ans.append(str); 

    return ans.toString(); 
}

}