Day 29 of LeetCode

Documenting LeetCode solving.

Q88

198. House Robber

Medium. 1D DP.

class Solution {
    public int rob(int[] nums) {
        int rob1 = 0, rob2 = 0;

        // [rob1, rob2, n, n + 1, ...]
        for (int n : nums) {
            int temp = Math.max(n + rob1, rob2);
            rob1 = rob2;
            rob2 = temp;
        }

        return rob2;
    }
}

Start reviewing.

R1 （Review 1）

217. Contains Duplicate

Easy.

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int n : nums) {
            if (set.contains(n)) {
                return true;
            }
            set.add(n);
        }

        return false;
    }
}

R2

242. Valid Anagram

Easy.

Used hashmap in python, int[] is easier in java.

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

        int[] sCount = encode(s);
        int[] tCount = encode(t);

        for (int i = 0; i < sCount.length; i++) {
            if (sCount[i] != tCount[i]) {
                return false;
            }
        }

        return true;
    }

    public int[] encode(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            int delta = c - 'a';
            counts[delta]++;
        }

        return counts;
    }
}

R3

1. Two Sum

Easy.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }

        return null;
    }
}

R4

49. Group Anagrams

Medium.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> code2Group = new HashMap<>();

        for (String str : strs) {
            String code = encode(str);
            if (!code2Group.containsKey(code)) {
                code2Group.put(code, new ArrayList<>());
            }
            code2Group.get(code).add(str);
        }

        List<List<String>> res = new ArrayList<>();
        for (List<String> group : code2Group.values()) {
            res.add(group);
        }

        return res;
    }

    public String encode(String s) {
        char[] code = new char[26];
        for (char c : s.toCharArray()) {
            int delta = c - 'a';
            code[delta]++;
        }

        return new String(code);
    }
}