力扣
中心扩展法
对于奇数个: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];}
}
HTML CSS JS Vue3 Ajax
HTML常见标签
CSS常见语法
类选择器
元素选择器