网站页面太多怎么做网站地图,西地那非片的功能,北京市建设工程交易中心网站,wordpress侧边栏html【问题描述】[中等] 【解答思路】
1. 暴力
首先明确如何判断一个字符串是否为回文字符串。第一个字符与最后一个字符相同#xff0c;第二个字符与倒数第二个字符相同…关于中心位置轴对称。 本题要求一共有多少个回文子串#xff0c;那么就需要判断#xff0c;索引[i, j]的…【问题描述】[中等] 【解答思路】
1. 暴力
首先明确如何判断一个字符串是否为回文字符串。第一个字符与最后一个字符相同第二个字符与倒数第二个字符相同…关于中心位置轴对称。 本题要求一共有多少个回文子串那么就需要判断索引[i, j]的子串是不是回文子串遍历所有这样[i, j]进行判断就可以找到回文子串的总数。这是暴力的做法。 首先如何判断[i, j]的子串是回文串根据定义来判断即可。 定义boolean isPalindrome(char[] chars, int start, int end)第一个参数为原字符串的字符数组表示第二第三个参数分别是字串的开始与结束索引。 在区间[start, end]上进行双指针的扫描将关于中心位置对应的字符进行比较如果发现有不相等说明不是回文子串。 循环结束没有发现对应位置不相等的字符说明是回文串。 主函数中 外循环的i表示子串的长度子串最长为s.length()所以循环的条件为i s.length()。从长度2开始是因为长度为1的子串都是回文子串一共有s.length()个最后加上即可。 内循环j表示子串的开始索引那么其结束索引为j i - 1。调用函数isPalindrome进行判断。 最后返回result s.length()将长度为1的子串都是回文子串的计数也算进行。
时间复杂度O(N3) 空间复杂度O(1)
public int countSubstrings(String s) {char[] chars s.toCharArray();int result 0;for (int i 2; i s.length(); i) {for (int j 0; j i - 1 s.length(); j)if (isPalindrome(chars, j, j i - 1))result;}return result s.length();}private boolean isPalindrome(char[] chars, int start, int end) {for (int i start, j end; j i; i, j--) {if (chars[i] ! chars[j])return false;}return true;}
2. 中心扩展
回文字符串关于中心对称这个中心既可以是一个字符比如子串的长度为奇数时也可以是两个字符的中间比如子串的长度为偶数时。那么对于长度为n的字符串其子串的中心一共有**nn-1**个n个是字母n-1个是两个字母的间歇。 我们需要找到每一个可能的对称中心有能向外扩展出多少个回文子串。要想办法表示每一个回文中心外扩的方式都一样。 回文中心与子串的奇偶性有关想必要分情况讨论。 如果子串的长度为奇数那么第一个子串只有一个字符其左边界left与右边界right相等。 如果子串的长度为偶数那么第一个子串有两个字符其左边界left与右边界right的关系为right left 1。 所以可以通过奇偶性来控制初始时left与right的关系。 循环 for (int i 0; i chars.length * 2 - 1; i)i表示每一个可能的回文中心通过i的奇偶性来设置初始的left, right。内循环进行外扩首先保证索引不超过数组边界其次当前判断的两个字符相等。否则当前[left, right]不是回文子串向外扩的也不可能是。外扩的方式就是使left–, right。 时间复杂度O(N2) 空间复杂度O(1)
public int countSubstrings3(String s) {char[] chars s.toCharArray();int result 0;for (int i 0; i chars.length * 2 - 1; i) { // 对每个可能的回文中心进行循环int left i / 2; // 当中心是两个字母的间歇时i%2 1当中心是字母时 leftright都落在该字母的位置int right left i % 2;while(left 0 right chars.length chars[left] chars[right]){left--;right;result;}}return result;}
3. 动态规划
动态规划流程 第 1 步设计状态 dp[i][j] i开始j结尾的是否为回文字符串 第 2 步状态转移方程
for(int i s.length()-1; i0; i--){for(int j i1; js.length(); j){if(s.charAt(i) s.charAt(j)){//i和j相邻的时候if(j - i 1){dp[i][j] true;}else{dp[i][j] dp[i1][j-1]}}else{dp[i][j] false;}}
}
第 3 步考虑初始化
第 4 步考虑输出 统计 dp[i][j] T 的个数 时间复杂度O(N) 空间复杂度O(1)
class Solution {public int countSubstrings(String s) {if(s null || s.equals()){return 0;}int n s.length();boolean[][] dp new boolean[n][n];int result s.length();for(int i 0; in; i) dp[i][i] true;for(int i n-1; i0; i--){for(int j i1; jn; j){if(s.charAt(i) s.charAt(j)) {//i和j相邻的时候if(j-i 1){dp[i][j] true;}else{dp[i][j] dp[i1][j-1]; }}else{dp[i][j] false;}if(dp[i][j]){result;}}}return result;}
}
2. Manacher 算法 时间复杂度O(N) 空间复杂度O(1)
class Solution {public int countSubstrings(String s) {int n s.length();StringBuffer t new StringBuffer($#);for (int i 0; i n; i) {t.append(s.charAt(i));t.append(#);}n t.length();t.append(!);int[] f new int[n];int iMax 0, rMax 0, ans 0;for (int i 1; i n; i) {// 初始化 f[i]f[i] i rMax ? Math.min(rMax - i 1, f[2 * iMax - i]) : 1;// 中心拓展while (t.charAt(i f[i]) t.charAt(i - f[i])) {f[i];}// 动态维护 iMax 和 rMaxif (i f[i] - 1 rMax) {iMax i;rMax i f[i] - 1;}// 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整ans f[i] / 2;}return ans;}
}
【总结】
1. 动态规划流程
第 1 步设计状态 第 2 步状态转移方程 第 3 步考虑初始化 第 4 步考虑输出 第 5 步考虑是否可以状态压缩
2.暂时没有掌握 Manacher 算法马拉车
2.1 加# 变奇数长度 收尾加标识 2.2 初始化 中心扩展
3. 想好再下手 思考得多敲得少 边敲边想反而会耗费更多的时间
参考链接https://leetcode-cn.com/problems/palindromic-substrings/solution/647java-bao-li-dpzhong-xin-kuo-zhan-xiang-jie-by-u/ 参考链接链接https://leetcode-cn.com/problems/palindromic-substrings/solution/647-hui-wen-zi-chuan-dong-tai-gui-hua-fang-shi-qiu/ 参考链接https://leetcode-cn.com/problems/palindromic-substrings/solution/hui-wen-zi-chuan-by-leetcode-solution/
