力扣爆刷第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];}
}