代码随想录第四十三天

Posted on In

复习

509 斐波那契数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 <= 1) 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
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
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 拆分整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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++){
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }

        return dp[n];
    }
}

96 不同的二叉搜索树

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

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

        return dp[n];
    }
}

01背包理论基础 二维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int[] weights;
int[] values;

int size;
int len = weights.length;
int[][] dp = new int[len + 1][size + 1];

for (int i = 1; i < len + 1; i++){
    for (int j = 1; j < size + 1; j++){
        if (j < weights[i - 1]){
            dp[i][j] = dp[i - 1][j];
        } else {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
        }
    }
}

return dp[len][size];

动态规划 01背包理论基础（滚动数组）一维

1
2
3
4
5
6
7
8
9
10
11
12
13
int[] weights;
int[] values;

int size;
int[] dp = new int[size + 1];

for (int i = 0; i < weights.length; i++){
    for (int j = size; j >= weights[i]; j--){
        dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
}

return dp[size];

416 分割等和子集

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
class Solution {
    public boolean canPartition(int[] nums) {
        if (nums.length == 0 || nums == null) return false;

        Arrays.sort(nums);

        int sum = 0;
        for (int i : nums){
            sum += i;
        }

        if (sum % 2 != 0) return false;

        int bagSize = sum / 2;

        int[] dp = new int[bagSize + 1];
        for (int i = 0; i < nums.length; i++){
            for (int j = bagSize; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }

            if (dp[bagSize] == bagSize) return true;
        }

        return dp[bagSize] == bagSize;
    }
}

1049 最后一块石头的重量II

动态规划五步曲：

  1. 确定dp数组以及下标的含义
    dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。
  2. 递推公式
    dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
  3. 初始化
  4. 遍历顺序
  5. 模拟过程
    把整个石头分成两堆就是，dp[size] 和 sum-dp[size];
    因为sum / 2 是向下取整，所以sum- dp[size] 一定大于 dp[size]; 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
        public int lastStoneWeightII(int[] stones) {
            if (stones.length == 0 || stones == null) return 0;
        
            int sum = 0;

            for (int i: stones){
                sum += i;
            }

            int size = sum / 2;
            int[] dp = new int[size + 1];
            for (int i = 0; i < stones.length; i++){
                for (int j = size; j >= stones[i]; j--){
                    dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
                }
            }
            return (sum - dp[size]) - dp[size];
        }
    }

494 目标和

此题转化为01背包问题
假设加法总和为x， 减法总和是sum - x
所以要求 x - （sum - x）= target
x = (target + sum) / 2

  1. 确定dp数组以及下标的含义
    dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
  2. 确定递推公式
    dp[j]，j 为5，

已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包
累加dp[j - nums[i]]

组合问题常用递推公式 

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 findTargetSumWays(int[] nums, int target) {
        if (nums == null || nums.length == 0) return 0;

        int sum = 0;
        for (int i : nums){
            sum += i;
        }
        if (target < 0 && -target > sum) return 0;
        if ((target + sum) % 2 != 0) return 0;
        int bagSize = (target + sum) / 2;

        if (bagSize < 0) bagSize = -bagSize;
        int[] dp = new int[bagSize + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++){
            for (int j = bagSize; j >= nums[i]; j--){
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[bagSize];
    }
}

474 一和零

  1. 确定dp数组（dp table）以及下标的含义
    dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
  2. 确定递推关系
    dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

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
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0) return 0;

        int[][] dp = new int[m + 1][n + 1];

        int zeroNum, oneNum;
        for (String str : strs){
            oneNum = 0;
            zeroNum = 0;

            for (char ch : str.toCharArray()){
                if (ch == '0') zeroNum++;
                else oneNum++;
            }

            for (int i = m; i >= zeroNum; i--){
                for (int j = n; j >= oneNum; j--){
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }

        return dp[m][n];
    }
}

每日一题： 451 Sort Characters By Frequency

利用priority queue， 把value排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new TreeMap<>();
        char[] chars = s.toCharArray();

        for (char i: chars){
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(
            (a, b) -> b.getValue() - a.getValue()
        );
        pq.addAll(map.entrySet());

        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()){
            Map.Entry<Character, Integer> entry = pq.poll();
            sb.append(String.valueOf(entry.getKey()).repeat(entry.getValue()));
        }

        return new String(sb);
    }
}