LeetCode-08/08/2022

Posted on In

This is a record of my craking process for Leetcode.

Word Break ()#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        if(s.length() == 0) return set.contains(s);
        boolean[] dp = new boolean[s.length()];
        for(int i = 0; i < s.length(); i++){
            if(set.contains(s.substring(0, i + 1))){
                dp[i] = true;
                continue;
            }
            int tmp = 0;
            while(tmp < i){
                if(dp[tmp] && set.contains(s.substring(tmp + 1, i + 1))){
                    dp[i] = true;
                    break;
                }
                tmp++;
            }
            if(dp[i]) continue;
            dp[i] = false;
        }
        return dp[s.length() - 1];
    }
}

Unique Binary Search Trees II()#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        Map<Pair<Integer, Integer>, List<TreeNode>> memo = new HashMap<>();
        return generateTreesWithRoot(1, n, memo);
    }
    public List<TreeNode> generateTreesWithRoot(int l, int r, Map<Pair<Integer, Integer>, List<TreeNode>> memo) {
        List<TreeNode> res = new ArrayList<>();
        if(l > r) {
            res.add(null);
            return res;
        }

        if(memo.containsKey(new Pair<>(l, r))) {
            return memo.get(new Pair<>(l, r));
        }

        for(int i = l; i <= r; i++) {
            List<TreeNode> leftSubTrees = generateTreesWithRoot(l, i - 1, memo);
            List<TreeNode> rightSubTrees = generateTreesWithRoot(i + 1, r, memo);
            for (TreeNode left: leftSubTrees) {
                for (TreeNode right: rightSubTrees) {
                    TreeNode root = new TreeNode(i, left, right);
                    res.add(root);
                }
            }
        }
        memo.put(new Pair<>(l, r), res);
        return res;
    }
}

Number of Music Playlists()#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int numMusicPlaylists(int n, int goal, int k) {
        int MOD = 1_000_000_007;

        // Initialize the DP table
        long[][] dp = new long[goal + 1][n + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= goal; i++) {
            for (int j = 1; j <= Math.min(i, n); j++) {
                // The i-th song is a new song
                dp[i][j] = dp[i - 1][j - 1] * (n - j + 1) % MOD;
                // The i-th song is a song we have played before
                if (j > k) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j] * (j - k)) % MOD;
                }
            }
        }

        return (int) dp[goal][n];
    }
}

Search in a 2D matrix()#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = m * n - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            int mid_row = mid / n;
            int mid_col = mid - mid_row * n;

            if(matrix[mid_row][mid_col] == target) {
                return true;
            }
            if(matrix[mid_row][mid_col] < target){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}