本文最后更新于2021年10月4日,已超过 2 个月没更新!

三、前缀和

3.1 实现前缀和问题

区域和检索-数组不可变

检索时间复杂度O(1)

class NumArray {
    int[] sums;

    public NumArray(int[] nums) {
        int n = nums.length;
        //sums[i]表示nums前i-1项的和
        sums = new int[n + 1];
        sums[0] = 0;
        for (int i = 0; i < n; ++i) {
            sums[i + 1] = nums[i] + sums[i];
        }
    }

    public int sumRange(int left, int right) {
        return sums[right + 1] - sums[left];
    }
}

二维区域和检索-矩阵不可变

检索时间复杂度O(1)

class NumMatrix {
    int[][] sumMatrix;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        sumMatrix = new int[m][n];

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 && j == 0) {
                    sumMatrix[i][j] = matrix[i][j];
                }
                else if (i == 0) {
                    sumMatrix[i][j] = sumMatrix[i][j - 1] + matrix[i][j];
                }
                else if (j == 0) {
                    sumMatrix[i][j] = sumMatrix[i - 1][j] + matrix[i][j];
                }
                else {
                    int sumII = 0, sumJJ = 0;
                    for (int ii = 0; ii < i; ++ii) {
                        sumII += matrix[ii][j];
                    }
                    for (int jj = 0; jj < j; ++jj) {
                        sumJJ += matrix[i][jj];
                    }
                    sumMatrix[i][j] = sumMatrix[i - 1][j - 1] + sumII + sumJJ + matrix[i][j];
                }
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = sumMatrix[row2][col2];

        if (row1 > 0) {
                sum -= sumMatrix[row1 - 1][col2];
            }
        if (col1 > 0) {
                sum -= sumMatrix[row2][col1 - 1];
        }
        if (row1 > 0 && col1 > 0) {
            sum += sumMatrix[row1 - 1][col1 - 1];
        }
        return sum;

    }
}

代码优化

class NumMatrix {
    int[][] sums;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        if (m > 0) {
            int n = matrix[0].length;
            sums = new int[m + 1][n + 1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
                }
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
    }
}

3.2 维护前缀和问题

和为K的子数组

暴力

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int count = 0;

        for (int i = 0; i < n; ++i) {
            int sum = 0;
            for (int j = i; j < n; ++j) {
                sum += nums[j];
                if (sum == k) ++count;
            }
        }
        return count;
    }
}

动态规划 & 哈希表

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int count = 0;
        int pre = 0;

        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, 1);

        for (int i = 0; i < n; ++i) {
            pre += nums[i];
            //仔细体会这里为什么是pre - k ⭐
            if (hashMap.containsKey(pre - k)) {
                count += hashMap.get(pre - k);
            }
            hashMap.put(pre, hashMap.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

和等于k的最长子数组长度

动态规划 & 哈希表

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        int n = nums.length;
        int max = 0, pre = 0;

        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, -1);

        for (int i = 0; i < n; ++i) {
            pre += nums[i];
            max = Math.max(max, i - hashMap.getOrDefault(pre - k, i));
            //只记录第一次的位置
            if (!hashMap.containsKey(pre)) {
                hashMap.put(pre, i);
            }
        }
        return max;
    }
}

连续数组

动态规划 & 哈希表

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int ans = 0;
        int count = 0; //奇数和偶数之差

        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, -1); //key为奇数和偶数的差

        for (int i = 0; i < n; ++i) {
            if (nums[i] % 2 == 0) --count;
            else ++count;

            if (hashMap.containsKey(count)){
                ans = Math.max(ans, i - hashMap.get(count));
            }
            else hashMap.put(count, i); 
        }
        return ans;
    }
}
func findMaxLength(nums []int) int {
    map_variable := map[int]int{
        0: -1,
    }

    count, maxLen := 0, 0
    for i := 0; i < len(nums); i++ {
        if nums[i] == 0 {
            count += -1
        } else {
            count += 1
        }
        if v, ok := map_variable[count]; ok {
            maxLen = max(maxLen, i - v)
        } else {
            map_variable[count] = i
        }
    }
    return maxLen
}

func max(a, b int) int {
    if a < b {
        return b
    }
    return a
}

统计「优美子数组」

动态规划 & 哈希表

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        //Key为奇数数量,Value为前缀和为Key数量
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, 1);
        int ans = 0, sum = 0;

        for (int num : nums) {
            sum += num & 1;
            ans += hashMap.getOrDefault(sum - k, 0);
            hashMap.put(sum, hashMap.getOrDefault(sum, 0) + 1);
        }
        return ans;
    }
}

连续的子数组和

动态规划 & 哈希表

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        //理解初始化的含义
        hashMap.put(0, -1);
        int sum = 0;

        for (int i = 0; i < nums.length; ++i) {
            sum += nums[i];
            int modulus = sum % k;
            if (hashMap.containsKey(modulus)) {
                if (i - hashMap.get(modulus) > 1) return true;
            }
            else hashMap.put(modulus, i);
        }
        return false;
    }
}

和可被K整除的子数组

动态规划 & 哈希表

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        int n = A.length;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        //体会初始化含义
        hashMap.put(0, 1);

        int sum = 0, ans = 0;
        for (int num : A) {
            sum += num;
            int modulus = (sum % K + K) % K; //当被除数为负数时取模结果为负数,需要纠正
            int same = hashMap.getOrDefault(modulus, 0);
            ans += same;
            hashMap.put(modulus, same + 1);
        }
        return ans;
    }
}

数组代替哈希表

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int[] map = new int[k];
        map[0] = 1;
        int sum = 0, ans = 0;
        for (int num : nums) {
            sum += num;
            int idx = (sum % k + k) % k;
            ans += map[idx] ++;
        }
        return ans;
    }
}

四、区间动态规划

LeetCode题库–May 5.24 - 奇怪的打印机

五、背包动态规划

  • 分析步骤
    1. 分析是否为背包问题。
    2. 是背包问题三种问法中的哪一种。
    3. 是 0-1 背包问题还是完全背包问题。也就是题目给的 nums 数组中的元素是否可以重复使用。
    4. 如果是组合问题,即求方案数,是否需要考虑元素之间的顺序。需要考虑顺序有顺序的解法,不需要考虑顺序又有对应的解法,需要注意。

5.1 最值问题

零钱兑换

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        int n = coins.length;
        f[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            f[i] = Integer.MAX_VALUE;

            for (int j = 0; j < n; ++j) {
                if (i >= coins[j] && f[i - coins[j]] != Integer.MAX_VALUE) {//边界情况
                    f[i] = Math.min(f[i - coins[j]] + 1, f[i]); //转移方程
                }
            }
        }
        if (f[amount] == Integer.MAX_VALUE) {
            f[amount] = -1;
        }
        return f[amount];
    }
}

5.2 组合问题(求方案数)

零钱兑换II

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int x = coin; x <= amount; ++x) {
                dp[x] += dp[x - coin];
            }
        }
        return dp[amount];
    }
}

组合总和Ⅳ

动态规划

class Solution {
    public int combinationSum4(int[] nums, int target) {
        //dp[i]表示组合为i的方案数
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int i = 1; i <= target; ++i) {
            for (int num : nums) {
                if (num <= i) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
}

六、状态压缩动态规划

七、计数问题

7.1 路径问题

不同路径

动态规划

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || j == 0) dp[i][j] = 1;
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m-1][n-1];
    }
}

不同路径 II

动态规划

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if(obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    if (i == 0 && j == 0) continue;
                    if (i == 0) {
                        dp[i][j] = dp[i][j - 1];
                    } else if (j == 0) {
                        dp[i][j] = dp[i - 1][j];
                    } else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

滚动数组优化

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[] dp = new int[n];
        dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if(obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                } else if (j >= 1) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[n - 1];
    }
}

7.2 斐波那契

青蛙跳台阶问题

动态规划

class Solution {
    public int numWays(int n) {
        if(n <= 1) return 1;
        int[] dp = new int[n+1];
        dp[0] = 1; dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }
}

上面方法优化空间复杂度

class Solution {
    public int numWays(int n) {
        int a = 1, b = 1;
        int sum = 1;
        for (int i = 2; i <= n; ++i) {
            sum = (a + b) % 1000000007;
            b = a;
            a = sum;
        }
        return sum;
    }
}

八、矩阵快速幂

九、数位动态规划


Try and fail, but don't fail to try.