LeetCode(81) -- 49, 50, 54

P49. Group Anagrams (Medium)

Given an array of strings, group anagrams together.

My Solution

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<Word, List<String>> map = new HashMap<>();
        for (String str : strs) {
            Word word = new Word(str);
            List<String> list = map.getOrDefault(word, new ArrayList<>());
            list.add(str);
            map.put(word, list);
        }
        return new ArrayList<>(map.values());
    }

    static class Word {
        int[] freq;
        public Word(String s) {
            freq = new int[26];
            char[] chars = s.toCharArray();
            for (char c : chars) {
                freq[c - 'a']++;
            }
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Word word = (Word) o;
            return Arrays.equals(freq, word.freq);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(freq);
        }
    }
}

99%

The Best Solution

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        
        List<List<String>> list = new ArrayList<List<String>>();
        if(strs==null || strs.length==0)
            return list;
        HashMap<String, List<String>> map = new HashMap<String,List<String>>();
        for( String str: strs ){
            String norStr = getNormalizedString(str);
            if(map.containsKey(norStr)){
                map.get(norStr).add(str);
            }else{
                List<String> subList = new ArrayList<String>();
                subList.add(str);
                map.put(norStr,subList);
                list.add(subList);
            }   
        }
        return list;
    }
    
    String getNormalizedString(String str){
        char[] norStr = new char[26];
        for(int i=0;i<str.length();i++){
            norStr[str.charAt(i)-'a']++;
        }
        
        return new String(norStr);
    }
}

P50. Pow(x, n) (Medium)

Implement pow(x, n), which calculates x raised to the power n (xn).

Discuss

class Solution {
    public double myPow(double x, int n) {
        if(n == 0)
            return 1;
        if(n<0){
            if (n == Integer.MIN_VALUE) {
                n = Integer.MAX_VALUE;
                x = 1/x;
                return x * myPow(x * x, n / 2) * x;
            }
            n = -n;
            x = 1/x;
        }
        return (n%2 == 0) ? myPow(x*x, n/2) : x*myPow(x*x, n/2);
    }
}

The Best Solution

class Solution {
    public double myPow(double x, int n) {
        if(n == 0) return 1;
        double res = myPow(x, n/2);
        if(n % 2 == -1) return res * res * 1/x;
        if(n % 2 == 1) return res * res * x;
        return res * res;
    }
}

100%

P54. Spiral Matrix (Medium)

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

My Solution

public class P54_SpiralMatrix {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        if (matrix.length == 0) {
            return ans;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int l = 0, r = n - 1, t = 0, b = m - 1, i = 0, j = 0;
        int d = 0;
        while (ans.size() < m * n) {
            if (d % 4 == 0) {
                while (j <= r) {
                    ans.add(matrix[i][j]);
                    j++;
                }
                j--;
                i++;
                t++;
            } else if (d % 4 == 1) {
                while (i <= b) {
                    ans.add(matrix[i][j]);
                    i++;
                }
                i--;
                j--;
                r--;
            } else if (d % 4 == 2) {
                while (j >= l) {
                    ans.add(matrix[i][j]);
                    j--;
                }
                j++;
                i--;
                b--;
            } else if (d % 4 == 3) {
                while (i >= t) {
                    ans.add(matrix[i][j]);
                    i--;
                }
                i++;
                j++;
                l++;
            }
            d++;
        }
        return ans;
    }
}

100%

Solution

class Solution {
    public List < Integer > spiralOrder(int[][] matrix) {
        List ans = new ArrayList();
        if (matrix.length == 0)
            return ans;
        int r1 = 0, r2 = matrix.length - 1;
        int c1 = 0, c2 = matrix[0].length - 1;
        while (r1 <= r2 && c1 <= c2) {
            for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
            for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
            if (r1 < r2 && c1 < c2) {
                for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
                for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
            }
            r1++;
            r2--;
            c1++;
            c2--;
        }
        return ans;
    }
}