潍坊网站建设策划,做app网站的软件有哪些,微信网页,软件技术专科有出路吗目录 647. 回文子串
看到题目的第一想法
看到代码随想录之后的想法
自己实现过程中遇到的困难(看代码)
516.最长回文子序列
看到题目的第一想法
看到代码随想录之后的想法
自己实现过程中遇到的困难(看代码) 647. 回文子串
力扣题目链接…目录 647. 回文子串
看到题目的第一想法
看到代码随想录之后的想法
自己实现过程中遇到的困难(看代码)
516.最长回文子序列
看到题目的第一想法
看到代码随想录之后的想法
自己实现过程中遇到的困难(看代码) 647. 回文子串
力扣题目链接(opens new window)
给定一个字符串你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
示例 1
输入abc输出3解释三个回文子串: a, b, c
示例 2
输入aaa输出6解释6个回文子串: a, a, a, aa, aa, aaa
提示输入的字符串长度不会超过 1000 。
看到题目的第一想法 按照回溯来做没做出来没法用回溯来写 使用暴力可以解 使用dp 将数目记录但是递推公式不好计算 看到代码随想录之后的想法 用动态规划若ij 则看i和j之间是否是回文串如果是回文则dp[i][j]也是回文 (选中两个单词的字符若相同看中间是否是回文) 确定dp数组和每个下标的含义 dp[i][j],看i和j之间是否是回文串 确定递推公式 若s[i]s[j] 则有三种情况 若ij 则dp[i][j]true 若ij-1 则dp[i][j]true 若ij-1则dp[i][j] dp[i1][j-1]看ij中间的是否是回文串 dp数组初始化 初始化都为false相当于遍历时若为回文则改为true 确定遍历顺序 dp[i][j] 依赖于 dp[i1][j-1] 则可以从下往上从左往右进行遍历 举例推导dp数组 打印dp数组 遍历时记录true的个数返回总数就是回文子串的个数了 自己实现过程中遇到的困难(看代码) 回溯没写出来 第一时间想一下暴力 回文串记得通过[i,j]中间的来进行判断 class Solution {public int countSubstrings(String s) {//我的思路是记录回文子串数目其中dp数组是不太好推测的//卡哥的思路是利用dp[i][j]二维数组看[ij] 是否是回文子串//若为回文子串则为true 若不为则为false//若 s[i] s[j]相等那么我们可以看[i1][j-1] 是否为回文子串,若为回文则dp[i][j]也为回文(相当于包在里面)//确定dp数组和下标的含义// dp[i][j] 看[i,j]是否为回文子串若是则为true否则为false//确定递推公式// 若s[i]s[j] 有三种情况 1 ij 则直接为true// 2 ij-1 则直接为true// 3 ij-1 则需要判断 若dp[i1][j-1]true 则dp[i][j]为true//dp数组初始化//全都为false 先默认都不为回文子串然后再一个个改成回文子串//确定遍历顺序//dp[i][j]依赖于dp[i1][j-1]则从下往上从前往后//举例推导dp数组int result 0;boolean[][] dp new boolean[s.length()][s.length()];for(int is.length()-1;i0;i--){for(int ji;js.length();j){if(s.charAt(i)s.charAt(j)){if(ij||ij-1||dp[i1][j-1]true){dp[i][j] true;result;}}}}return result;}
}//我的想法用回溯判断是否回文是则加入result中//回溯算法三要素//回溯函数的参数和返回值//字符串以及startIndex//回溯函数的终止条件//若字符串到最后则返回//回溯函数的执行逻辑//若startIndex到i为回文串则加入到结果集中//正着读和倒着读一样的字符串//dp[i][j] 遍历到[i-1,j-1]里面回文子串的数目// 确定递推公式// 若[i-1,j-1]为回文子串则dp[i][j] Math.max(dp[i-1][j]1,dp[i][j-1]1)// 若[i-1,j-1]不为回文子串,dp[i][j] Math.max(dp[i-1][j],dp[i][j-1]);// dp数组初始化// 都为0// 确定遍历顺序// 从上往下从左至右/*int[][] dp new int[s.length()1][s.length()1];for(int i1;is.length();i){for(int ji;js.length();j){if(isValid(s,i-1,j-1)){dp[i][j] Math.max(dp[i-1][j]1,dp[i][j-1]1);}else{dp[i][j] Math.max(dp[i-1][j],dp[i][j-1]);}}}/return dp[s.length()][s.length()];//backTracking(s,0);//return resultPath.size();}boolean isValid(String s,int i,int j){//判断是否是回文while(ij){if(s.charAt(i)!s.charAt(j)){return false;}i;j--;}return true;}/*void backTracking(String s,int startIndex){if(startIndexs.length()){return ;}for(int istartIndex;is.length();i){if(isValid(s,startIndex,i)){String sub s.substring(startIndex,i1);if(isValid(sub)){resultPath.add(sub);}}else{continue;}backTracking(s,startIndex1); }}boolean isValid(String s){//判断是否是回文int i0;int js.length()-1;while(ij){if(s.charAt(i)!s.charAt(j)){return false;}i;j--;}return true;}*/
//} 516.最长回文子序列
力扣题目链接(opens new window)给定一个字符串 s 找到其中最长的回文子序列并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例 1: 输入: bbbab 输出: 4 一个可能的最长回文子序列为 bbbb。
示例 2: 输入:cbbd 输出: 2 一个可能的最长回文子序列为 bb。
看到题目的第一想法 dp[i][j]记录所有和i相等的j 的个数当成回文串 写出来发现不符合题意比如说aabaa也是回文串但是a的个数为4 串长度为5 求的是串的长度 看到代码随想录之后的想法 用动态规划若ij 则看i和j之间回文串的最大长度 (选中两个单词看中间回文串的最大长度) 确定dp数组和每个下标的含义 dp[i][j],看i和j之间回文串的最大长度 确定递推公式 若s[i]s[j] 则dp[i][j] dp[i1][j-1]2 若s[i]!s[j] 看选中其中一个字符的最长回文是多少则 dp[i][j] Math.max(dp[i1][j],dp[i][j-1]); dp数组初始化 当ij时一定时回文全都初始化为1 确定遍历顺序 dp[i][j] 依赖于 dp[i1][j-1] 则可以从下往上从左往右进行遍历 举例推导dp数组 打印dp数组 遍历时记录true的个数返回总数就是回文子串的个数了 自己实现过程中遇到的困难(看代码) 理解一下回文的含义 回文串记得通过[i,j]中间的来进行判断相等时不要忘了dp[i1][j-1] 2 做的时候忘了2了 class Solution {public int longestPalindromeSubseq(String s) {//卡哥的思路//dp[i][j] 记录[i~j]的最长的回文子序列//确定递推公式//若s[i]s[j] 则看两者间最长的回文子序列是多少 dp[i][j] dp[i1][j-1]2 加了两个字符所以加2//若s[i]!s[j] 则看选中s[i] 于选中s[j]的两个序列中最长的回文子序列是多少(两者的最大值)// dp[i][j] max(dp[i1][j],dp[i][j-1])//确定遍历顺序//由于dp依赖于dp[i1][j-1]则dp[i][j]遍历顺序为由下往上从左往右//dp数组初始化//当ij时一定是回文所以dp[i][i]1int[][] dp new int[s.length()][s.length()];for(int i0;is.length();i){dp[i][i]1;}for(int is.length()-2;i0;i--){for(int ji1;js.length();j){if(s.charAt(i)s.charAt(j)){dp[i][j] dp[i1][j-1]2;}else{dp[i][j] Math.max(dp[i1][j],dp[i][j-1]);}}}//返回0~length-1的最大值return dp[0][s.length()-1];/*//我的思路和之前那道题思路一样 想着所有和i相等的都是回文其实是错误的比如bbabb 回文长度为5 我为4//若ij dp[i][j] dp[i][j-1]1 //若i!j dp[i][j] dp[i][j-1]//确定dp的参数和下标的含义//i-1~j-1之间以i开头最长的子序列的长度//确定递推公式//若s[i-1]s[j-1] dp[i][j] dp[i][j-1]1//若s[i-1]!s[j-1] dp[i][j] dp[i][j-1]//dp数组初始化//默认为0//确定遍历顺序//从上往下从左至右//举例推导dp数组int[][] dp new int[s.length()1][s.length()1];int max 0;for(int i1;is.length()1;i){for(int ji;js.length()1;j){if(s.charAt(i-1)s.charAt(j-1)){dp[i][j] dp[i][j-1]1;if(dp[i][j]max){max dp[i][j];}}else{dp[i][j] dp[i][j-1];}}}return max;*/}
}
