力扣爆刷第101天之hot100五连刷91-95

力扣爆刷第101天之hot100五连刷91-95

一、62. 不同路径

题目链接：https://leetcode.cn/problems/unique-paths/description/?envType=study-plan-v2&envId=top-100-liked
思路：求不同路径，任意一个位置都可以从它的上方和左方推出，也就是dp[i][j] = dp[i][j-1] + dp[i-1][j]，压缩数组为dp[j] = dp[j] + dp[j-1];

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

二、64. 最小路径和

题目链接：https://leetcode.cn/problems/minimum-path-sum/description/?envType=study-plan-v2&envId=top-100-liked
思路：求最小路径和，每一个位置可以从当前位置的上方和左方推出，但是只需要这两者中的最小值加上当前值，即可得到结构。
dp[j] = Math.min(dp[j], dp[j-1]) + nums[i][j]。

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        
        for(int i = 0; i < m; i++) {
            for(int j = 1; j <= n; j++) {
                int t = Math.min(dp[j], dp[j-1]);
                t = t == Integer.MAX_VALUE ? 0 : t;
                dp[j] = t + grid[i][j-1];
            }
        }
        return dp[n];
    }
}

三、5. 最长回文子串

题目链接：https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-100-liked
思路：求最长回文子串需要遍历所有的位置，从每一个位置开始，向两边扩散，可以是单点中心扩散，可以是双点中心扩散，然后遍历判断记录即可。

class Solution {
    public String longestPalindrome(String s) {
        String max = "";
        for(int i = 0; i < s.length(); i++) {
            String s1 = find(s, i, i);
            String s2 = find(s, i, i+1);
            max = s1.length() > max.length() ? s1 : max;
            max = s2.length() > max.length() ? s2 : max;
        }
        return max;
    }

    String find(String s, int left, int right) {
        while(left >= 0 && right < s.length()) {
            if(s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }else{
                break;
            }
        }
        return s.substring(left+1, right);
    }
}

四、1143. 最长公共子序列

题目链接：https://leetcode.cn/problems/longest-common-subsequence/description/?envType=study-plan-v2&envId=top-100-liked
思路：求最长公共子序列，如text1 = “abcde”, text2 = “ace” ，定义dp[i][j]表示区间[0, i] 和区间[0, j]中以text1[i]和text2[j]字符为结尾，如果二者相等则 dp[i+1][j+1] = dp[i][j] + 1;如果二者不等则 dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
1 1 1
1 1 1
1 2 2
1 2 2
1 2 3

class Solution {
     public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(text1.charAt(i) == text2.charAt(j)) {
                    dp[i+1][j+1] = dp[i][j] + 1;
                }else{
                    dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
        return dp[m][n];
    }
}

五、72. 编辑距离

题目链接：https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-100-liked
思路：求最少操作步骤，定义dp[i][j]表text1以索引 i 结尾，text2以索引 j 结尾的最长相等子序列，当结尾相等，自然操作数延续上一个位置，dp[i+1][j+1] = dp[i][j];，如果不等，可以考虑从左边，上边，左上角。
0 1 2 3
1 1 2 3
2 2 2 2
3 2 2
4
0

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 = 0; i < dp.length; i++) dp[i][0] = i;
        for(int i = 0; i < dp[0].length; i++) dp[0][i] = i;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(word1.charAt(i) == word2.charAt(j)) {
                    dp[i+1][j+1] = dp[i][j];
                }else{
                    dp[i+1][j+1] = Math.min(Math.min(dp[i+1][j], dp[i][j+1]), dp[i][j]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}