婚纱网站html模板,互动平台表示公司帮助国内客户进行新冠药物研发,app设计公司,马尾福州网站建设这两题看了自己写的笔记还不懂的话#xff0c;看看这个up的思路就行#xff1a; https://space.bilibili.com/111062940/search/video?keyword%E5%9B%9E%E6%96%87
647. 回文子串
中等 提示 给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。
回…这两题看了自己写的笔记还不懂的话看看这个up的思路就行 https://space.bilibili.com/111062940/search/video?keyword%E5%9B%9E%E6%96%87
647. 回文子串
中等 提示 给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
网友1
回文子串需要是数组内部连续的。
dp数组含义 以i为起始以j为结尾的子串是否为回文。递推公式 当遍历到s【i】s【j】时就可以判断回文有三种情况
a 此时ij 一定是回文串aa 此时 j-i1 一定是回文串 j-i1 : dp【i】【j】Trueaba 此时j-i1 需要判断内部【 i1j-1】是否为回文串如果是那么合起来就是回文串。 If dp【i1】【j-1】True; dp【i】【j】True
初始化 由于上面提及了 ij的情况所以将所有位置初始化为false即可遍历顺序 dp【i】【j】 需要依赖 dp【i1】【j-1】,所以i从大到小j从小到大并且j为i后面所以j从i开始遍历。
布尔类型的dp[i][j]表示区间范围[i,j] 注意是左闭右闭的子串是否是回文子串如果是dp[i][j]为true否则为false。dp[i][j]要把i理解为左指针leftj要理解为右指针right如上图所示。所以遍历顺序一点也不奇怪了先把right指向第二个元素下标为1然后left一直从0开始始终小于右指针。初始化呢一开始开辟空间全都是0所以也不用初始化了。这题建议也可以看看代码随想录的解题思路它的遍历顺序需要注意。
// dp[i 1][j - 1] 从递推公式可以看出dp[i][j] 依赖于dp[i 1][j - 1]所以要先算比较大的i,i要从末尾开始算i--j要从小的开始算j
class Solution {public int countSubstrings(String s) {char[] chars s.toCharArray();int len chars.length;boolean[][] dp new boolean[len][len];int result 0;for (int i len - 1; i 0; i--) { // i 是 leftfor (int j i; j len; j) { // j 是 rightif (chars[i] chars[j]) { // 当这俩相等时if (j - i 1) { // 说明是同一个字符或者两个挨着的字符 result;dp[i][j] true;} else if (dp[i 1][j - 1]) { // 相隔超过两个字符result;dp[i][j] true;}// 其他情况都是false初始化就为false不用管了}}}return result;}
}516. 最长回文子序列
中等 给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。
子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。
class Solution {public int longestPalindromeSubseq(String s) {// dp[i][j]字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]// 递推公式如果s[i]与s[j]相同那么dp[i][j] dp[i 1][j - 1] 2// 根据递推公式可以看出i要从后往前遍历i要先计算大的j要从前往后遍历j要先计算小的int len s.length();int [][] dp new int[len][len];// 递推公式决定了left不可能访问到len - 1 right不可能访问到 0for (int i 0; i len; i) dp[i][i] 1;for (int l len - 2; l 0; l--) {for (int r l 1; r len; r) {if (s.charAt(r) s.charAt(l)) {dp[l][r] dp[l 1][r - 1] 2;} else {dp[l][r] Math.max(dp[l 1][r], dp[l][r - 1]); // 也就是说删掉首部字符或者尾部字符取最大那种情况// 比如说 acbac 取前4个acba或者后4个cbac}}}return dp[0][len - 1];}
}
