游戏网站规划方案,保康县城乡建设路网站,wordpress 金融主题,oa办公系统有哪些【问题描述】[第5题][最长回文子串][中等]
给定一个字符串 s#xff0c;找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1#xff1a;输入: babad
输出: bab
注意: aba 也是一个有效答案。【解答思路】
1. 中心扩展法…【问题描述】[第5题][最长回文子串][中等]
给定一个字符串 s找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1输入: babad
输出: bab
注意: aba 也是一个有效答案。
【解答思路】
1. 中心扩展法 时间复杂度O(N^2) 空间复杂度O(1)
public class Solution {public String longestPalindrome(String s) {int len s.length();if (len 2) {return s;}int maxLen 1;String res s.substring(0, 1);// 中心位置枚举到 len - 2 即可for (int i 0; i len - 1; i) {String oddStr centerSpread(s, i, i);String evenStr centerSpread(s, i, i 1);String maxLenStr oddStr.length() evenStr.length() ? oddStr : evenStr;if (maxLenStr.length() maxLen) {maxLen maxLenStr.length();res maxLenStr;}}return res;}private String centerSpread(String s, int left, int right) {// left right 的时候此时回文中心是一个字符回文串的长度是奇数// right left 1 的时候此时回文中心是一个空隙回文串的长度是偶数int len s.length();int i left;int j right;while (i 0 j len) {if (s.charAt(i) s.charAt(j)) {i--;j;} else {break;}}// 这里要小心跳出 while 循环时恰好满足 s.charAt(i) ! s.charAt(j)因此不能取 i不能取 jreturn s.substring(i 1, j);}
}
2.暴力
根据回文子串的定义枚举所有长度大于等于 22 的子串依次判断它们是否是回文在具体实现时可以只针对大于“当前得到的最长回文子串长度”的子串进行“回文验证”在记录最长回文子串的时候可以只记录“当前子串的起始位置”和“子串长度”
时间复杂度O(N^3) 空间复杂度O(1)
public class Solution {public String longestPalindrome(String s) {int len s.length();if (len 2) {return s;}int maxLen 1;int begin 0;// s.charAt(i) 每次都会检查数组下标越界因此先转换成字符数组char[] charArray s.toCharArray();// 枚举所有长度大于 1 的子串 charArray[i..j]for (int i 0; i len - 1; i) {for (int j i 1; j len; j) {if (j - i 1 maxLen validPalindromic(charArray, i, j)) {maxLen j - i 1;begin i;}}}return s.substring(begin, begin maxLen);}/*** 验证子串 s[left..right] 是否为回文串*/private boolean validPalindromic(char[] charArray, int left, int right) {while (left right) {if (charArray[left] ! charArray[right]) {return false;}left;right--;}return true;}
}
3. 动态规划 时间复杂度O(N^2) 空间复杂度O(N)
public class Solution {public String longestPalindrome(String s) {// 特判int len s.length();if (len 2) {return s;}int maxLen 1;int begin 0;// dp[i][j] 表示 s[i, j] 是否是回文串boolean[][] dp new boolean[len][len];char[] charArray s.toCharArray();for (int i 0; i len; i) {dp[i][i] true;}for (int j 1; j len; j) {for (int i 0; i j; i) {if (charArray[i] ! charArray[j]) {dp[i][j] false;} else {if (j - i 3) {dp[i][j] true;} else {dp[i][j] dp[i 1][j - 1];}}// 只要 dp[i][j] true 成立就表示子串 s[i..j] 是回文此时记录回文长度和起始位置if (dp[i][j] j - i 1 maxLen) {maxLen j - i 1;begin i;}}}return s.substring(begin, begin maxLen);}
}
【总结】
1. 想法优先暴力 逐渐优化 不要东想西想
2.动态规划
1、思考状态重点
状态的定义先尝试「题目问什么就把什么设置为状态」 然后思考「状态如何转移」如果「状态转移方程」不容易得到尝试修改定义目的依然是为了方便得到「状态转移方程」。 「状态转移方程」是原始问题的不同规模的子问题的联系。即大问题的最优解如何由小问题的最优解得到。
2、思考状态转移方程核心、难点
状态转移方程是非常重要的是动态规划的核心也是难点
常见的推导技巧是分类讨论。即对状态空间进行分类
归纳「状态转移方程」是一个很灵活的事情通常是具体问题具体分析
除了掌握经典的动态规划问题以外还需要多做题
如果是针对面试请自行把握难度。掌握常见问题的动态规划解法理解动态规划解决问题是从一个小规模问题出发逐步得到大问题的解并记录中间过程
「动态规划」方法依然是「空间换时间」思想的体现常见的解决问题的过程很像在「填表」。
3、思考初始化
初始化是非常重要的一步错步步错。初始化状态一定要设置对才可能得到正确的结果。
角度 1直接从状态的语义出发
角度 2如果状态的语义不好思考就考虑「状态转移方程」的边界需要什么样初始化的条件
角度 3从「状态转移方程」方程的下标看是否需要多设置一行、一列表示「哨兵」sentinel这样可以避免一些特殊情况的讨论。
4、思考输出
有些时候是最后一个状态有些时候可能会综合之前所有计算过的状态。
5、思考优化空间也可以叫做表格复用
「优化空间」会使得代码难于理解且是的「状态」丢失原来的语义初学的时候可以不一步到位。先把代码写正确是更重要 「优化空间」在有一种情况下是很有必要的那就是状态空间非常庞大的时候处理海量数据此时空间不够用就必须「优化空间」 非常经典的「优化空间」的典型问题是「0-1 背包」问题和「完全背包」问题。
3. 动态规划思考
边界问题考虑清楚第二第三步动态就是做表格 想清楚方向自底向上 子问题 学基础 再解决问题 通识教育自顶向下 一般解决问题思路
转载链接https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/
