代码随想录第四十一天

Posted on In

复习

509 斐波那契数

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

70 爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i < n + 1; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

746 使用最小花费爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;

        if (n <= 1) return 0;
        int[] dp = new int[n + 1];

        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i < n + 1; i++){
            dp[i] = Math.min(dp[i - 1] +cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[n];
    }
}

62 不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++){
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
}

63 不同路径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
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[][] dp = new int[m][n];
        for (int i = 0; i < m && obstacleGrid[i][0] != 1; i++){
            dp[i][0] = 1;
        }
        for (int i = 0; i < n && obstacleGrid[0][i] != 1; i++){
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                if (obstacleGrid[i][j] != 1){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[m - 1][n - 1];
    }
}

343 拆分整数

动态规划5部曲：

  1. dp[i] 表示，拆分i时最大乘积是多少
  2. 递推公式
    一种是两个数：j 和 i-j 的乘积
    另一种两个数以上：j 和 dp[i-j]的乘积
    再算上每次对dp[i]的赋值比较
  3. dp初始化
    只考虑dp[2] = 1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;

        for (int i = 3; i < n + 1; i++){
            for (int j = 1; j <= i - j; j++){
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }

        return dp[n];
    }
}

96 不同的二叉搜索树

  1. dp[i]表示，有多少不同的二叉搜索树
  2. 递推公式
    以dp[3]为例：
    头节点为1
    右子树2个元素 * 左子树有0个搜索树
    头节点为2
    右子树1个 * 左子树1个
    头节点为3
    右子树0个 * 左子树2个

2个元素 dp[2]
1个元素 dp[1]
0个元素 dp[0]

dp[3] = dp[2]*dp[0] + dp[1]*dp[1] + dp[0] * dp[2];
dp[4] = 30 21 12 03;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n +1];

        dp[0] = 1;

        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= i; j++){
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
}

每日一题 387 First Unique Character in a String:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int firstUniqChar(String s) {
        int[] record = new int[26];

        for (int i = 0; i < s.length(); i++){
            record[s.charAt(i) - 'a']++;
        }

        for (int i = 0; i < s.length(); i++){
            if (record[s.charAt(i) - 'a'] == 1){
                return i;
            }
        }

        return -1;
    }
}

每日一题 49 Group Anagrams

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String i :strs){
            char[] chars = i.toCharArray();
            Arrays.sort(chars);

            String str = new String(chars);
            if (!map.containsKey(str)){
                map.put(str, new ArrayList<String>());
            } 
            map.get(str).add(i);
        }

        return new ArrayList<>(map.values());
    }
}