当前位置：首页 > news >正文

日志|动态规划|最长回文子串|最长公共子序列|HTML CSS

news 2025/9/24 22:06:14

力扣

中心扩展法

对于奇数个：l和r初始位置都在中心字符，不断向前向后找到相同的位置
对于偶数个：l和r在中心字符差一，不断向前向后找相同位置
迭代每个字符，分开找奇数偶数。

点击查看代码

class Solution {public String longestPalindrome(String s) {if (s == null || s.length() < 1) return "";int res_start = 0;int res_len = 0;for(int i = 0;i < s.length();i++){//找奇数：babint left = i;int right = i;while(left>0 && right<s.length()&&s.charAt(left)==s.charAt(right)){if(right-left+1 > res_len){res_len = right - left + 1;res_start = left;}left--;right++;}//找偶数：bbint l = i;int r = i+1;while(l>0 && r < s.length() && s.charAt(l) == s.charAt(r)){if(r-l+1 > res_len){res_len = r - l + 1;res_start = l;}}}return s.substring(res_start,res_start + res_len);}
}

动态规划法

不太懂，死记硬背把，两个字符串A和B，数量化为二维数组，dp二维数组。行是A，列是B。
多造一行一列，把第0行第0列初试化为0，会有答案使得字符串为空。
开始迭代，从第一行第一列开始。
如果字符相等，dp.cur = 左上角 + 1
反之，dp.cur = 上面 + 左面其一的最大值

点击查看代码

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

####Javaweb

HTML CSS JS Vue3 Ajax