网站开发在无形资产中,面向网站开发的相关知识,屏蔽右键网站,网站怎么做多级菜单力扣爆刷第101天之hot100五连刷91-95 文章目录 力扣爆刷第101天之hot100五连刷91-95一、62. 不同路径二、64. 最小路径和三、5. 最长回文子串四、1143. 最长公共子序列五、72. 编辑距离 一、62. 不同路径
题目链接#xff1a;https://leetcode.cn/problems/unique-paths/desc…力扣爆刷第101天之hot100五连刷91-95 文章目录 力扣爆刷第101天之hot100五连刷91-95一、62. 不同路径二、64. 最小路径和三、5. 最长回文子串四、1143. 最长公共子序列五、72. 编辑距离 一、62. 不同路径
题目链接https://leetcode.cn/problems/unique-paths/description/?envTypestudy-plan-v2envIdtop-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/?envTypestudy-plan-v2envIdtop-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[n1];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/?envTypestudy-plan-v2envIdtop-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, i1);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(left1, right);}
}四、1143. 最长公共子序列
题目链接https://leetcode.cn/problems/longest-common-subsequence/description/?envTypestudy-plan-v2envIdtop-100-liked 思路求最长公共子序列如text1 “abcde”, text2 “ace” 定义dp[i][j]表示区间[0, i] 和区间[0, j]中以text1[i]和text2[j]字符为结尾如果二者相等则 dp[i1][j1] dp[i][j] 1;如果二者不等则 dp[i1][j1] Math.max(dp[i1][j], dp[i][j1]); 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[m1][n1];for(int i 0; i m; i) {for(int j 0; j n; j) {if(text1.charAt(i) text2.charAt(j)) {dp[i1][j1] dp[i][j] 1;}else{dp[i1][j1] Math.max(dp[i1][j], dp[i][j1]);}}}return dp[m][n];}
}
五、72. 编辑距离
题目链接https://leetcode.cn/problems/edit-distance/description/?envTypestudy-plan-v2envIdtop-100-liked 思路求最少操作步骤定义dp[i][j]表text1以索引 i 结尾text2以索引 j 结尾的最长相等子序列当结尾相等自然操作数延续上一个位置dp[i1][j1] 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[m1][n1];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[i1][j1] dp[i][j];}else{dp[i1][j1] Math.min(Math.min(dp[i1][j], dp[i][j1]), dp[i][j]) 1;}}}return dp[m][n];}
}
