Day 30 of LeetCode

LeetCode 30 days challenge completed! 🎉

I want to extend my challenge cuz there are still many topics haven't been covered, let's roll!!

Q89

213. House Robber II

Medium. 1D DP.

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        // Edge case
        if (n == 1) return nums[0];
        // Use House Robber I solution to compute the max rob money of
        // nums[0, n-2] (without end) and nums[1, n-1](without start)
        // and take the larger one of them.
        return Math.max(helper(nums, 0, n - 2), helper(nums, 1, n - 1));
    }

    public int helper(int[] nums, int start, int end) {
        int rob1 = 0, rob2 = 0;
        // [0, 0, 2, 3, 2]
        for (int i = start; i <= end; i++) {
            int temp = Math.max(nums[i] + rob1, rob2);
            rob1 = rob2;
            rob2 = temp;
        }

        return rob2;
    }
}

Q90

5. Longest Palindromic Substring

Medium.

class Solution {
    public String longestPalindrome(String s) {
        String res = "";

        for (int i = 0; i < s.length(); i++) {
            // Odd length
            String s1 = Pali(s, i, i);
            // Even length
            String s2 = Pali(s, i, i + 1);

            res = s1.length() > res.length() ? s1 : res;
            res = s2.length() > res.length() ? s2 : res;
        }

        return res;
    }

    public String Pali(String s, int l, int r) {
        // Check if it's a palidromic string from center
        while (l >= 0 && r < s.length() &&
               s.charAt(l) == s.charAt(r)) {
            l--; // -1
            r++; // 2
        }
        // Not (l, r + 1), because left and right pointers are updated 
        // before return.
        return s.substring(l + 1, r);
    }
}

R5

347. Top K Frequent Elements

Medium.

Solution 1: Array count.

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> val2Freq = new HashMap<>(); // {val : freq}
        for (int n : nums) {
            val2Freq.put(n, val2Freq.getOrDefault(n, 0) + 1);
        }

        ArrayList<Integer>[] freq2Vals = new ArrayList[nums.length + 1]; // [[], [3], [2], [1]]
        for (int val : val2Freq.keySet()) {
            int freq = val2Freq.get(val);
            if (freq2Vals[freq] == null) {
                freq2Vals[freq] = new ArrayList<>();
            }
            freq2Vals[freq].add(val);
        }

        int[] res = new int[k];
        int p = 0;
        for (int i = freq2Vals.length - 1; i >= 0; i--) {
            ArrayList<Integer> valList = freq2Vals[i];
            if (valList == null) {
                continue;
            }
            for (int j = 0; j < valList.size(); j++) {
                res[p] = valList.get(j);
                p++;
                if (p == k) {
                    return res;
                }
            } 
        }

        return null;
    }

Solution 2: Min heap

PriorityQueue implementation in Java.

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> val2Freq = new HashMap<>();
        for (int n : nums) {
            val2Freq.put(n, val2Freq.getOrDefault(n, 0) + 1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>>
            pq = new PriorityQueue<>((entry1, entry2) -> {
                return entry1.getValue().compareTo(entry2.getValue());
            });

        for (Map.Entry<Integer, Integer> entry : val2Freq.entrySet()) {
            pq.offer(entry);
            if (pq.size() > k) {
                pq.poll();
            }
        }

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = pq.poll().getKey();
        }

        return res;
    }
}

R6

238. Product of Array Except Self

Medium.

class Solution {

    // [1, 2, 3, 4]
    // curr = 24 (1, 2, 6, 24)
    // [1, 1, 2, 6]

    // [1, 2, 3, 4]
    // curr = 24 (1, 4, 12, 24)
    // [24, 12, 8, 6]

    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, 1);

        // Prefix
        int curr = 1;
        // Left production
        for (int i = 0; i < n; i++) {
            res[i] *= curr;
            curr *= nums[i];
        }
        // Postfix
        curr = 1;
        // Right production
        for (int i = n - 1; i >= 0; i--) {
            res[i] *= curr;
            curr *= nums[i];
        }

        return res;
    }
}

R7

271. Encode and Decode Strings

Medium.

public class Solution {
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str.length());
            sb.append("#");
            sb.append(str);
        }
        return sb.toString();
    }

    public List<String> decode(String str) {
        List<String> res = new ArrayList<>();
        int i = 0;

        // "4#leet4#code"
        //    i   j 

        while (i < str.length()) {
            int j = i;
            while (str.charAt(j) != '#') {
                j++;
            }
            int len = Integer.parseInt(str.substring(i, j));
            i = j + 1;
            j = j + len + 1;
            String s = str.substring(i, j);
            res.add(s);
            i = j;
        }

        return res;
    }
}

R8

128. Longest Consecutive Sequence

Medium.

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> numSet = new HashSet<>();
        for (int n : nums) {
            numSet.add(n);
        }

        int res = 0;
        for (int n : numSet) {
            // Check if it's the first
            if (!numSet.contains(n - 1)) {
                int len = 1;
                while (numSet.contains(n + len)) {
                    len++;
                }
                res = Math.max(res, len);
            }
        }

        return res;
    }
}