LeetCode刷题笔记——HOT100面试题（8）

算法
,

一维数组的动态规划

53. 最大子序和

参见《剑指Offer》连续子数组的最大和。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length==0) return 0;
        int res = nums[0], sum = nums[0];
        for (int i=1; i<nums.length; i++) {
            if (sum<0) sum = nums[i];
            else sum += nums[i];
            res = Math.max(res, sum);
        }
        return res;
    }
}

70. 爬楼梯

斐波那契数列。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int climbStairs(int n) {
        int a=1, b=2;
        for (int i=3; i<=n+1; i++) {
            int t = a+b;
            a = b;
            b = t;
        }
        return a;
    }
}

96. 不同的二叉搜索树

卡特兰数：设以i为根节点的二叉搜索树数量为$g(i)$，以1~n为节点组成的二叉搜索树共有$f(n)$个，$f(n)=g(1)+g(2)+……+g(n)$；

以i为根节点时，左子树的二叉搜索树有$f(i-1)$个，右子树的二叉搜索树有$f(n-i)$个，因此$g(i)=f(i-1)*f(n-i)$；

综上，

$$f(n)=f(0)*f(n-1)+f(1)*f(n-2)+……+f(n-1)*f(0)$$

1
2
3
4
5
6
7
8
9
10
11
12
13
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; i++) {
            for (int j=1; j<=i; j++) {
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
}

152. 乘积最大子数组

状态转移方程：dp[i] = max(dp[i-1]*nums[i], nums[i])。由于存在负数，负数乘以最小值就变成了最大值，因此需要同时维护最小和最大值，当遍历到负数时交换两数进行计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProduct(int[] nums) {
        int res = Integer.MIN_VALUE;
        int max = 1, min = 1;
        for (int num: nums) {
            if (num<0) {
                int t = min;
                min = max;
                max = t;
            }
            max = Math.max(max*num, num);
            min = Math.min(min*num, num);
            res = Math.max(res, max);
        }
        return res;
    }
}

300. 最长上升子序列

用dp[i]来表示以第i个元素为结尾的最长递增子序列长度。遍历nums[i]，再遍历其之前的元素nums[j]，若nums[j]<nums[i]，dp[i]可能的取值是dp[j]+1。时间复杂度$O(n^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length==0) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i=1; i<nums.length; i++) {
            for (int j=i-1; j>=0; j--) {
                if (nums[j]<nums[i]) {
                    dp[i] = Math.max(dp[j]+1, dp[i]);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

二维数组的动态规划

62. 不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 j=1; j<n; j++) {
            dp[0][j] = 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];
    }
}

64. 最小路径和

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

221. 最大正方形

用dp[i][j]来表示以(i,j)为右下角的正方形的最大边长。当格点为1时，它能形成正方形的最大边长取决于最短的一条边，即与左上、上和左格点的和的最小值，即1 + min(dp[i-1][j-1]、dp[i][j-1]、dp[i-1][j])。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        int res = 0;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (matrix[i][j]=='0') continue;
                if (i==0 || j==0) dp[i][j] = 1;
                else dp[i][j] = 1 + min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]);
                res = Math.max(res, dp[i][j] * dp[i][j]);
            }
        }
        return res;
    }

    public int min(int i, int j, int k) {
        return Math.min(Math.min(i, j), k);
    }
}

312. 戳气球

设在区间[start, end]中戳破的最后一个气球是第k个，那么这个区间的结果为dp[start][k] + nums[start]*nums[k]*nums[end] + dp[k][end]（不戳破两边的气球，如果start+1==end，则视为0）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] nums_ = new int[n+2];
        for (int i=1; i<n+1; i++) {
            nums_[i] = nums[i-1];
        }
        nums_[0] = 1;
        nums_[n+1] = 1;
        int[][] dp = new int[n+2][n+2];
        for (int i=n-1; i>=0; i--) {
            for (int j=i+2; j<n+2; j++) {
                for (int k=i+1; k<j; k++) {
                    int tmp = dp[i][k] + dp[k][j] + nums_[i]*nums_[k]*nums_[j];
                    dp[i][j] = Math.max(dp[i][j], tmp);
                }
            }
        }
        return dp[0][n+1];
    }
}

字符串相关问题

10. 正则表达式匹配

参考《剑指offer》正则表达式匹配。

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 isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        for (int i=0; i<=m; i++) {
            for (int j=0; j<=n; j++) {
                if (j==0) dp[i][j] = (i==0);
                else {
                    if (p.charAt(j-1)!='*') {
                        if (i>0 && (s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.')) {
                            dp[i][j] = dp[i-1][j-1];
                        }
                    } else {
                        if (j>1) {
                            dp[i][j] |= dp[i][j-2];
                        }
                        if (i>0 && j>1 && (s.charAt(i-1)==p.charAt(j-2) || p.charAt(j-2)=='.')) {
                            dp[i][j] |= dp[i-1][j];
                        }
                    }
                    
                }
            }
        }
        return dp[m][n];
    }
}

32. 最长有效括号

dp[i]表示以s[i]结尾的子串的最长有效括号长度。如果s[i]=='('，是无法构成有效括号的，因此dp[i]=0。如果s[i]==')'，且s[i-1]=='('，则它们构成一组有效括号，有效括号长度+2；如果s[i-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
27
class Solution {
    public int longestValidParentheses(String s) {
        //dp[i]表示以s[i]结尾的子串的最长有效括号长度
        int[] dp = new int[s.length()];
        int res = 0;
        for (int i=0; i<s.length(); i++) {
            //如果末位是'('，不存在有效括号子串
            if (i>0 && s.charAt(i)==')') {
                if (s.charAt(i-1)=='(') {
                    //与前一位构成有效括号，长度+2
                    dp[i] = 2;
                    if (i>=2) dp[i] += dp[i-2];
                } else if (s.charAt(i-1)==')') {
                    //找到已构成有效括号对之前的最后一个单括号
                    int lastSingleBracket = i-dp[i-1]-1;
                    if (lastSingleBracket>=0 && s.charAt(lastSingleBracket)=='(') {
                        dp[i] = 2+dp[i-1];
                        //如果该括号之前还存在有效括号子串，需要加上这段长度
                        if (lastSingleBracket>=1) dp[i] += dp[lastSingleBracket-1];
                    }
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

72. 编辑距离

dp[i][j]表示到A[i]和B[j]为止所需的最小操作次数。如果A[i]和B[j]相同，则无需操作，dp[i][j] = dp[i-1][j-1]。否则，有三种可能的操作方式：

  1. 删除当前字符，相当于用A[i-1]继续与B[j]比较，同时操作数+1；
  2. 添加一个字符，相当于用A[i]与B[j-1]比较，同时操作数+1；
  3. 修改当前字符，A和B继续比较前面一个字符，同时操作数+1。

从以上三种操作中找到使操作数最小的方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i=1; i<=m; i++) {
            dp[i][0] = i;
        }
        for (int j=1; j<=n; j++) {
            dp[0][j] = j;
        }
        for (int i=1; i<=m; i++) {
            for (int j=1; j<=n; j++) {
                if (word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
            }
        }
        return dp[m][n];
    }
}

139. 单词拆分

dp[i]表示字符串s[:i]是否能够拆分成单词表中的词。如果dp[i]能够拆分，并且s[i:j]是单词表中的单词，那么dp[i+j]也能够拆分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        HashSet<String> set = new HashSet<>();
        for (String word: wordDict) {
            set.add(word);
        }
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        for (int i=1; i<=n; i++) {
            for (int j=i-1; j>=0; j--) {
                if (!dp[j]) continue;
                String w = s.substring(j, i);
                dp[i] = set.contains(w);
                if (dp[i]) break;//已经可以拆分，略过其它情况
            }
        }
        return dp[n];
    }
}