扬州建设局网站,电商网站建设论文参考文献,公司开办流程,建设摩托车官方旗舰店本周继续做一道动态规划类型的题目#xff0c;该题是阿里一面的一道算法题。【动图算法】(动态规划篇)#xff1a;最长回文子串leetcode 5 题#xff1a;最长回文子串https://leetcode-cn.com/problems/longest-palindromic-substring/给定一个字符串 s#xff0c;找到 s 中… 本周继续做一道动态规划类型的题目该题是阿里一面的一道算法题。【动图算法】(动态规划篇)最长回文子串leetcode 5 题最长回文子串https://leetcode-cn.com/problems/longest-palindromic-substring/给定一个字符串 s找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。?输入: babad输出: bab注意: aba 也是一个有效答案。??输入: cbbd输出: bb解答过程动态规划-数组维护var longestPalindrome function(s) { let n s.length let res // 初始化一个n*n的二维数组 let dp Array.from(new Array(n),() new Array(n).fill(0)) for(let i n-1;i 0;i--){ for(let j i;j dp[i][j] s[i] s[j] (j - i 2 || dp[i1][j-1]) if(dp[i][j] j - i 1 res.length) res s.substring(i,j1) } } return res};由动图可以很清楚的看到首先初始化了一个n*n的二维数组而后在循环中进行判断这里着重看 dp[i][j] s[i] s[j] (j - i 2 || dp[i1][j-1])这里。dp[i][j] s[i] s[j]判断为当前项是否为回文。j - i 2 判断其是否为最小奇偶字符串即长度小于2若前一条不满足则判断dp[i1][j-1] 即其前一项是否依然为回文。动态规划-中心扩展var longestPalindrome function(s) { if(!s || s.length 2) return s let start 0,end 0; let n s.length // 中心扩展法 let centerExpend (left,right) { while(left 0 right left-- right } return right - left - 1 } for(let i 0;i let len1 centerExpend(i,i) let len2 centerExpend(i,i1) let maxLen Math.max(len1,len2) if(maxLen end - start){ // 这里的(maxLen - 1) 1即为对(maxLen-1)/2而后向下取整 start i - ((maxLen - 1) 1) end i (maxLen 1) } } return s.substring(start,end1)};这里以i作为中心点在for循环中len1与len2分别判断了奇偶字符串是否为回文。而后判断长度截取字符串相较于前一种方法该方法则更为简单直观通过中心点向数组的两端发散计算出回文的长度。最终得到正确的结果。
