共计 4212 个字符,预计需要花费 11 分钟才能阅读完成。
零 题目:算法(leetode,附思维导图 + 全副解法)300 题之(5)最长回文子串
一 题目形容
二 解法总览(思维导图)
三 全副解法
1 计划 1
1) 代码:
// 计划 1 滑动窗口法(“工夫复杂度高,个别通过不了”)var longestPalindrome = function(s) {
// 是否为 回文串。(subStr = '' 略微体现下编程的严谨性)const isValid = (subStr = '') => {
const l = subStr.length;
let resFlag = true;
// 边界:i < l/2
for(let i = 0; i < l/2; i++) {
//“对称地位”上的字符不相等,那么必定就不是 回文串 了
if (subStr[i] !== subStr[(l - 1) - i]) {
resFlag = false;
break;
}
}
return resFlag;
}
const l = s.length;
// curMaxLength 以后回文子串的最大长度,范畴:[l, 1]
for (let curMaxLength = l; curMaxLength > 0; curMaxLength--) {// 在 curMaxLength 下,curStartIndex 的无效范畴为 [0, ((l + 1) - curMaxLength) )
for (let curStartIndex = 0; curStartIndex < ((l + 1) - curMaxLength); curStartIndex++) {const subStr = s.substr(curStartIndex, curMaxLength);
// 一旦合乎 回文串,那么以后子串肯定是咱们的预期答案(“之一”)// 因为咱们 curMaxLength 在一次次遍历中在递加
if (isValid(subStr)) {return subStr;}
}
}
// 边界:可能 l 为 0、而后间接到这里了,须要返回空字符串(不过题目 1 <= s.length <= 1000,故 可省略)return "";
}
2 计划 2
1) 代码:
// 计划 2 动静布局,(s[i] === s[j] && dp[i + 1][j - 1]) || (s[i] === s[j] && ((j + 1) - i) < 3)
var longestPalindrome = function(s) {
const l = s.length,
// 1)含意:s[i][j] 示意 s[i, j] 是否为回文串(双闭区间)// 初始化 1:dp,n*n 个值都初始化为 false
dp = new Array(l).fill(false).map(item => new Array(l).fill(false));
// 以后 最长回文子串 的开始下标、最大长度
let maxStartIndex = 0,
// 边界:maxLength 初始化为 1。不然会有问题、可自行思考~
maxLength = 1;
// 初始化 2:dp 对角线上值 均为 true
for (let i = 0; i < l; i++) {for(let j = 0; j < l; j++) {if (i === j) {dp[i][j] = true;
}
}
}
// 2)状态转移方程:// s[i][j] = (s[i] === s[j] && dp[i + 1][j - 1]) || (s[i] === s[j] && ((j + 1) - i) < 3)
// s[i][j] = (以后首、尾字符雷同 && 首、尾各往两头缩 1 位仍旧是回文串)
// 或 (以后首、尾字符雷同 && 以后首、尾地位距离 < 3) 如 "bb" 这种长度小于 3 时,只有保障 首、尾字符雷同即可
for (let j = 1; j < l; j++) {for(let i = 0; i < j; i++) {if ((s[i] === s[j] && dp[i + 1][j - 1]) || (s[i] === s[j] && ((j + 1) - i) < 3)) {dp[i][j] = true;
// 以后 s[i, j] 为回文串了,才看是否须要更新 maxStartIndex、maxLength 值
// 3)当 s[i, j] 为回文串 && (j + 1) - i) > maxLength 时,更新 maxStartIndex、maxLength 值
if (((j + 1) - i) > maxLength) {
maxStartIndex = i;
maxLength = ((j + 1) - i);
}
} else {dp[i][j] = false;
}
}
}
// 最初依据“咱们所保护的”maxStartIndex, maxLength 得出相应的子串
return s.substr(maxStartIndex, maxLength);
}
3 计划 3
1) 代码:
// 计划 3 核心扩散法(留神“都进行奇、偶状况的解决”)var longestPalindrome = function(s) {
// 依据传入的子串、左 右边界下标,一直“向外”挪动、试图拿到更长的回文串
const helper = (str, left, right) => {while(left >=0 && right < l) {if (str[left] === str[right]) {
// 看看是否需更新 maxStartIndex、maxLength 值
if ((right + 1 - left) > maxLength) {
maxStartIndex = left;
maxLength = (right + 1 - left);
}
// 留神:这 2 语句放以后 if 分支的最初面、别放在最后面了!!// 持续“向外”挪动、试图拿到更长的回文串
left--;
right++;
} else {// 此时 str[left] !== str[right],必定无奈拿到更长的回文串,退出循环!break;
}
}
}
const l = s.length;
// 以后“最长回文串”对应的 开始下标、最大长度。let maxStartIndex = 0,
maxLength = 0;
for (let i = 0 ; i < l; i++) {// 1)奇数:以 s[i]“向外”挪动、试图拿到更长的回文串
helper(s, i ,i);
// 2)偶数:以 s[i]、s[i + 1]“向外”挪动、试图拿到更长的回文串
helper(s, i, i + 1);
}
return s.substr(maxStartIndex, maxLength);
}
4 计划 4
1) 代码:
// 计划 4 Manacher(“马拉车”)算法
class Solution {public String longestPalindrome(String s) {
int start = 0, end = -1;
StringBuffer t = new StringBuffer("#");
for (int i = 0; i < s.length(); ++i) {t.append(s.charAt(i));
t.append('#');
}
t.append('#');
s = t.toString();
List<Integer> arm_len = new ArrayList<Integer>();
int right = -1, j = -1;
for (int i = 0; i < s.length(); ++i) {
int cur_arm_len;
if (right >= i) {
int i_sym = j * 2 - i;
int min_arm_len = Math.min(arm_len.get(i_sym), right - i);
cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
} else {cur_arm_len = expand(s, i, i);
}
arm_len.add(cur_arm_len);
if (i + cur_arm_len > right) {
j = i;
right = i + cur_arm_len;
}
if (cur_arm_len * 2 + 1 > end - start) {
start = i - cur_arm_len;
end = i + cur_arm_len;
}
}
StringBuffer ans = new StringBuffer();
for (int i = start; i <= end; ++i) {if (s.charAt(i) != '#') {ans.append(s.charAt(i));
}
}
return ans.toString();}
public int expand(String s, int left, int right) {while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
--left;
++right;
}
return (right - left - 2) / 2;
}
}
四 更多
1 刷题进度
1)LeetCode:307 / 2390。2)《剑指 offer》:66 / 66。3)相干学习材料与笔记汇总:https://github.com/CYBYOB/algorithm-leetcode/tree/master/ 材料 %26 笔记。4)注:所有题目均有 2- 5 种 左右的解法,后续还将不断更新题目 & 题解。敬请期待~
也欢送大家进群一起 学习、交换、刷题 & 拿高薪~
2 GitHub – LeetCode 我的项目仓库
0)本我的项目地址:https://github.com/CYBYOB/algorithm-leetcode。指标、愿景:让每个人都能领有肯定的算法能力、以应答面试中(会触类旁通的同学还能够将其融入本人的肌肉和血液,甚至可能赋能于公司的业务和技术)的算法。1)我的项目的根目录下的 README.md 文件,能够帮您疾速查阅每 1 道题的起源、难度、所有的题解计划等。2)而每个题解(即 index.md 文件)中,还将附带题目形容、所有的题解计划的思维导图(.xmind 文件)、思路和技巧等。3)每种题解计划都有具体的正文,通过“数字步骤”将形象的算法逻辑、清晰和有档次的展现于您的背后。能够说是,开箱即用~
4)所有的题解计划都是通过作者 1 人之手,故代码格调及其对立。一旦浏览达到一定量后,后续将大大晋升您的浏览速度 ——“正所谓、质变引起量变”。5)自己每周仍在一直的更新 —— 保障每周都有新的题目、题解计划刺激着您的神经 和 刷题欲望。欢送对算法感兴趣的同学退出咱们的社群。QQ 群:933919972;作者 QQ:1520112971;作者 VX:c13227839870(可拉您进群、一起学习与交换~)。
3 作者标签
1)“BAT 里 1 名小小的伪全栈工程师,主攻前端,偶然写点后端”。2)2019 年的微信小程序利用开发赛 - 全国三等奖;2019CODA 较量 - 前 17/211 强 且 荣获“优良团队”名称 等。3)“半自媒体人”,在校期间、集体公众号(IT 三少。新自媒体(公众号)号:码农三少)在半年内实现了 0 到 5.8K+ 的粉丝增长等。
正文完