1220. Count Vowels Permutation
Posted Updated LeetCode / Hard2 minutes read (About 291 words)

1220. Count Vowels Permutation

Question

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

  • Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')

  • Each vowel 'a' may only be followed by an 'e'.

  • Each vowel 'e' may only be followed by an 'a' or an 'i'.

  • Each vowel 'i' may not be followed by another 'i'.

  • Each vowel 'o' may only be followed by an 'i' or a 'u'.

  • Each vowel 'u' may only be followed by an 'a'.

Since the answer may be too large, return it modulo 10^9 + 7.

Solution

DFS搜索，记忆化剪枝。
每次根据上一个字母last来从哈希表里选择下一个可选字母进行遍历，并计算总的可组成数sum。

Code

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
class Solution {
    final int MOD = (int) Math.pow(10, 9) + 7;
    int[][] memo;
    HashMap<Character, Character[]> map;
    public int countVowelPermutation(int n) {
        if(n == 1) return 5;
        map = new HashMap<>();
        memo = new int[26][n+1];
        Character[] vowels = {'a', 'e', 'i', 'o', 'u'}, 
        a = {'e'}, e = {'a','i'}, i = {'a','e','o','u'}, o = {'i', 'u'}, u = {'a'};
        map.put('a', a);
        map.put('e', e);
        map.put('i', i);
        map.put('o', o);
        map.put('u', u);
        
        int ans = 0;
        
        for(char vowel : vowels){
            ans += count(vowel, n-1);
            ans %= MOD;
        }
        return ans;
    }
    
    private int count(char last, int n){
        if(memo[last-'a'][n] != 0) return memo[last-'a'][n];
        if(n == 1){
            memo[last-'a'][n] = map.get(last).length;
            return memo[last-'a'][n];
        }
        
        int sum = 0;
        for(char next : map.get(last)){
            sum += count(next, n-1);
            sum %= MOD;
        }
        memo[last-'a'][n] = sum;
        return sum;
    }
}
377. Combination Sum IV
Posted Updated LeetCode / Medium2 minutes read (About 296 words)

377. Combination Sum IV

Question

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Solution

记忆化搜索，memo[]数组用来记录达到某个总和时的可行方案数量。
辅助方法count记录累计的总和memo[total]。

递归DFS，记忆化剪枝，如果memo[]数组不为空，则直接返回记忆内容。
当total等于target时，该组合成立，返回1。

遍历nums[]数组中的每个元素，并将总组合数相加记录到memo[total]中。
最后返回总组合数memo[total]。

*非常奇怪的是，当我使用int[]数组进行记忆化搜索时部分case会超时，推测是因为我判断int[]数组是否被记录是通过是否等于0而非是否为空导致的。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    int[] numbers;
    Integer[] memo;
    public int combinationSum4(int[] nums, int target) {
        numbers = nums;
        memo = new Integer[target+1];
        return count(0, target);
    }
    
    private int count(int total, int target){
        if(memo[total] != null) return memo[total];
        if(total == target) return 1;
    
        int sum = 0;
        for(int i = 0; i < numbers.length; i++){
            if(total + numbers[i] <= target) sum += count(total + numbers[i], target);
        }
        memo[total] = sum;
        
        return memo[total];
    }
}
576. Out of Boundary Paths
Posted Updated LeetCode / Medium / 复习3 minutes read (About 449 words)

576. Out of Boundary Paths

Question

There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball.

Given the five integers m, n, maxMove, startRow, startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 109 + 7.

Solution

DFS，记忆化搜索哦剪枝。

记忆化搜索

三维数组memo[][][]用来记录起点为startRow, startColumn，剩余距离为maxMove时的总路径数。
注意需要将memo[][][]所有数值初始化为-1。否则在进行BFS搜索时，无法对maxMove等于0的情况进行剪枝。

DFS

当当前位置越界，则为一个有效路径，返回1。
当剩余步数为0时，无法继续移动，返回0。

如果当前位置与剩余步数的状态已经被搜索并记录过，则直接返回memo[startRow][startColumn][maxMove]。
如果未搜索，则将maxMove减一，并向四周移动一格，对当前位置的四个方向进行递归。
记忆当前位置的四个方向的总路径数之和，模除后返回。

Code

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
class Solution {
    final int MOD = (int) Math.pow(10, 9) + 7;
    long[][][] memo;
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        memo = new long[m][n][maxMove];
       for(int i = 0; i < m; i++){
           for(int j = 0; j < n; j++){
               for(int k = 0; k < maxMove; k++){
                   memo[i][j][k] = -1;
               }
           }
       }
        return (int) dfs(m, n, maxMove, startRow, startColumn);
    }
    
    private long dfs(int m, int n, int maxMove, int startRow, int startColumn){
        if(startRow < 0 || startRow >= m || startColumn < 0 || startColumn >= n) return 1;
        if(maxMove == 0) return 0;
        
        maxMove--;
        if(memo[startRow][startColumn][maxMove] != -1) return memo[startRow][startColumn][maxMove];
        
        long left = dfs(m, n, maxMove, startRow-1, startColumn);
        long right = dfs(m, n, maxMove, startRow+1, startColumn);
        long up = dfs(m, n, maxMove, startRow, startColumn+1);
        long down = dfs(m, n, maxMove, startRow, startColumn-1);

        memo[startRow][startColumn][maxMove] = (left + right + up + down) % MOD;
        return memo[startRow][startColumn][maxMove];
    }
}
509. Fibonacci Number
Posted Updated a minute read (About 163 words)

509. Fibonacci Number

Question

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Solution 1

记忆化搜索，在递归时递归过的n放入数组memo中记录。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    int[] memo;
    public int fib(int n) {
        if(n == 0 || n == 1) return n;
        memo = new int[n+1];
        return fibo(n);
    }
    
    private int fibo(int n){
        if(n == 0 || n == 1) return n;
        if(memo[n] == 0) memo[n] = fibo(n-1) + fibo(n-2);
        return memo[n];
    }
}

Solution 2

递归，当n等于0或者1时返回固定值。
否则返回fib(n-1)+fib(n-2)。

Code

1
2
3
4
5
6
class Solution {
    public int fib(int n) {
        if(n == 0 || n == 1) return n;
        return fib(n-1) + fib(n-2);
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 305 words)

2320. Count Number of Ways to Place Houses

Question

There is a street with n * 2 plots, where there are n plots on each side of the street. The plots on each side are numbered from 1 to n. On each plot, a house can be placed.

Return the number of ways houses can be placed such that no two houses are adjacent to each other on the same side of the street. Since the answer may be very large, return it modulo 10<sup>9</sup><span> </span>+ 7.

Note that if a house is placed on the i<sup>th</sup> plot on one side of the street, a house can also be placed on the i<sup>th</sup> plot on the other side of the street.

Solution

计算单侧河道可以放置的种类。
一开始用的是DFS搜素来计算可以放置的种类。
计算后发现是以（2，3）开始的斐波那契数列。

因此直接计算n位置的斐波那契数列值即可。
然后两边可以匹配的种类就是其平方。

记忆化搜索

在计算斐波那契数列时，由于要多次重复计算前面的位置，因此可以采用记忆化搜索记录对应的斐波那契额值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    long[] memo;
    public int countHousePlacements(int n) {
        memo = new long[n+1];
        long res = fibo(n);
        res *= res;
        res %= 1000000007;
        return (int) res;
    }
    
    private long fibo(int n){
        if(n == 1) return 2;
        else if(n == 2) return 3;
        if(memo[n] != 0) return memo[n];
        memo[n] = fibo(n-1) % 1000000007 + fibo(n-2) % 1000000007;

        return memo[n];
    }
}
Posted Updated LeetCode / Hard / 复习3 minutes read (About 449 words)

2318. Number of Distinct Roll Sequences

Question

You are given an integer n. You roll a fair 6-sided dice n times. Determine the total number of distinct sequences of rolls possible such that the following conditions are satisfied:

  1. The greatest common divisor of any adjacent values in the sequence is equal to 1.
  2. There is at least a gap of 2 rolls between equal valued rolls. More formally, if the value of the i<sup>th</sup> roll is equal to the value of the j<sup>th</sup> roll, then abs(i - j) > 2.

Return the* total number** of distinct sequences possible*. Since the answer may be very large, return it modulo 10<sup>9</sup><span> </span>+ 7.

Two sequences are considered distinct if at least one element is different.

Solution

DFS+记忆化搜索剪枝。
辅助方法getValidNext计算前两个位置为last1和last2时的所有的下一个有效值，将返回值储存在next[][]数组中。

DFS搜索

DFS搜索，传入剩余骰子数量n，前两个骰子的值x和y。
从next[x][y]中得到所有有效值。并进行递归。
将返回结果加和并返回。
当n等于0时，只有一个组合，因此返回1。

记忆化搜索

在搜索时会重复计算很多相同的x，y与n的组合，因此可以采用记忆化搜索进行剪枝。
用memo[][][]数组记录x，y与n的状态。如果此前已经计算过其结果，则直接返回memo[x][y][n]。

Code

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
class Solution {
    List<Integer>[][] next;
    int[][][] memo;
    public int distinctSequences(int n) {
        next = new ArrayList[7][7];
        for(int i = 0; i <= 6; i++){
            for(int j = 0; j <= 6; j++){
                next[i][j] = getValidNext(i, j);
            }
        }
        memo = new int[7][7][10001];
        return count(n, 0, 0);
    }
    
    private int count(int n, int x, int y){
        if(n == 0) return 1;
        if(memo[x][y][n] != 0) return memo[x][y][n];
        List<Integer> validNext = next[x][y];
        int sum = 0;
        for(int z : validNext){
            sum += count(n-1, y, z);
            sum %= 1000000007;
        }
        memo[x][y][n] = sum;
        return sum;
    }
    
    private List<Integer> getValidNext(int last1, int last2){
        List<Integer> arr = new ArrayList<>();
        for(int i = 1; i <= 6; i++){
            if(last1 == 0 && last2 == 0) arr.add(i);
            else if(i == last1 || i == last2) continue;
            else if((last2 & 1) == 0 && (i & 1) == 0) continue;
            else if((last2 == 3 || last2 == 6) && (i == 3 || i == 6)) continue;
            else arr.add(i);
        }
        return arr;
    }
}
354. Russian Doll Envelopes
Posted Updated LeetCode / Hard / 复习7 minutes read (About 979 words)

354. Russian Doll Envelopes

Question

You are given a 2D array of integers envelopes where envelopes[i] = [w<sub>i</sub>, h<sub>i</sub>] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Solution 1

最长递增子数列

这道题是LIS问题（Longest Increasing Subsequence） 的升级版。
后一个数组中的两个元素应该同时严格大于前一个数组中的两个元素。
因此我们需要维护一个宽度和高度同时严格单调递增的数列。

排序

我们可以对数组以宽度进行比较排序。当二者的宽度相等时，以高度的倒序排序。
（采用倒序排序是为了下面处理时排除不严格大于上一个数组的情况。）

递增数列

我们可以维护一个递增动态数组arr，记录高度组成的单调递增数列。（LIS）
首先将数组中的第一个元素的高度加入动态数组。
然后遍历数组envelopes[]：

  • 如果当前数组的高度height大于单调递增数列的最大值：
    • 则当前的数组的宽度和高度均严格大于数组中最后一个高度对应的数组。
    • 数组是优先以宽度的顺序排列，相等时以高度的倒序排列。由于相同宽度时高度大的在前，因此当当前高度大于之前的最大高度，则宽度也一定大于之前的最大宽度。
  • 如果小于或者等于单调递增数列的最大值：
    • 单调数列中高度的增长越平缓，我们在后面找到更多严格大于height的可能性就越大，因此可以用贪心思想，更新单调数列中的第一个大于当前高度的值。
    • 由于单调递增数列是有序的，因此可以采用二分搜索来寻找第一个大于当前高度的值的下标，并将其更新为当前的height。

排序的时间复杂度为O(nlogn)，遍历数组的时间复杂度为O(n)，二分搜索的时间复杂度为O(logn)。
总的时间复杂度为O(nlogn)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a,b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        
        List<Integer> arr = new ArrayList<>();
        arr.add(envelopes[0][1]);
        for(int i = 1; i < envelopes.length; i++){
            int height = envelopes[i][1];
            if(height > arr.get(arr.size()-1)){
                arr.add(height);
            }
            else{
                int index = Collections.binarySearch(arr, height);
                if(index < 0) index = -index-1;
                arr.set(index, height);
            }
        }
        return arr.size();
    }
}

Solution 2

注意这个方法在LeetCode中会超时，仅仅是记录一下思路，也可以采用动态规划的方法。
记忆化搜索剪枝。
记忆化搜索每个envelope。

memorazation()方法，返回当前的envelope中可以包含的最大数量。
当数组memo[i]不等于0时，返回memo[i]。
否则初始化最大值max为1。
遍历数组中的所有元素，如果宽度于长度都大于envelopes[i]，则向下递归搜索该元素。
比较并更新max和递归结果的返回值+1。
最后将当前位置memo[i]设置为包含的最大数量max。

遍历所有元素时间复杂度O(n)。
记忆化搜索元素的子项时间复杂度O(n)。
时间复杂度为O(n2)。

Code

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
class Solution {
    int[][] dolls;
    int[] memo;
    
    public int maxEnvelopes(int[][] envelopes) {
        dolls = envelopes;
        memo = new int[dolls.length];
        int res = 0;
        for(int i = 0; i < dolls.length; i++){
            if(memo[i] != 0) continue;
            memorazation(i);
            res = Math.max(res, memo[i]);
        }
        return res;
    }
    
    private int memorazation(int i){
        if(memo[i] != 0){
            return memo[i];
        }
        int max = 1;
        for(int k = 0; k < dolls.length; k++){
            if(dolls[k][0] < dolls[i][0] && dolls[k][1] < dolls[i][1]){
                max = Math.max(max, memorazation(k) + 1);
            }
        }
        return memo[i] = max;
    }
}
Posted Updated LeetCode / Hard / 复习3 minutes read (About 488 words)

329. Longest Increasing Path in a Matrix

Question

Given an m x n integers matrix, return *the length of the longest increasing path in *matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Solution

第一次就通过DFS和DP的知识自己摸索出了记忆化搜索，非常开心！: )

记忆化搜索，采用DFS搜索，并动态规划的思想保存搜索结果。

递归计算从x, y点出发的最大长度，并在递归中记录子位置的最大长度。
通过子位置的最大长度对递归树进行剪枝。

记忆化搜索

初始化一个memo[][]数组，记录已经搜索过的x, y位置的最大长度。
对所有下一个位置进行DFS搜索，如果越界或不满足递增规律，则返回最大长度1。
（这里应该返回0，但是为了下一步的记忆化搜索判断的遍历因此返回1。如果返回0的话则后面返回最大值不需要-1，但此时由于会重复搜索因此速度会降低。）

如果x, y的位置已经搜索过了（即memo[x][y] != 0），则直接返回memo[x][y]的值+1。

搜索完所有位置的最大长度，将其中的最大值保存在memo[][]中。
最后返回最大值+1。

将每个位置遍历，返回memo[][]中的最大值。

Code

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
class Solution {
    int[][] mat, memo, moves = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int m, n, max;
    
    public int longestIncreasingPath(int[][] matrix) {
        mat = matrix;
        m = matrix.length;
        n = matrix[0].length;
        memo = new int[m][n];
        
        max = 0;
        for(int x = 0; x < m; x++){
            for(int y = 0; y < n; y++){
                dfs(x, y, -1);
                max = Math.max(max, memo[x][y]);
            }
        }
        return max;
    }
    
    private int dfs(int x, int y, int parent){
        if(x < 0 || y < 0 || x >= m || y >= n || parent >= mat[x][y]) return 1;
        if(memo[x][y] != 0) return memo[x][y] + 1;
        int best = 0;
        for(int[] move : moves){
            int count = dfs(x + move[0], y + move[1], mat[x][y]);
            best = Math.max(best, count);
        }
        memo[x][y] = best;
        return best + 1;
    }
}
Follow

Recents

Archives

Links

×