这篇文章主要介绍“C++如何解决最长回文子串问题”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“C++如何解决最长回文子串问题”文章能帮助大家解决问题。Example 1:Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.Example 2:Input: “cbbd”
Output: “bb”这道题让我们求最长回文子串，首先说下什么是回文串，就是正读反读都一样的字符串，比如 “bob”, “level”, “noon” 等等。那么最长回文子串就是在一个字符串中的那个最长的回文免费云主机域名子串。LeetCode 中关于回文串的题共有五道，除了这道，其他的四道为Palindrome Number，Validate Palindrome，Palindrome Partitioning，Palindrome Partitioning II，我们知道传统的验证回文串的方法就是两个两个的对称验证是否相等，那么对于找回文字串的问题，就要以每一个字符为中心，像两边扩散来寻找回文串，这个算法的时间复杂度是 O(n*n)，可以通过 OJ，就是要注意奇偶情况，由于回文串的长度可奇可偶，比如 “bob” 是奇数形式的回文，”noon” 就是偶数形式的回文，两种形式的回文都要搜索，对于奇数形式的，我们就从遍历到的位置为中心，向两边进行扩散，对于偶数情况，我们就把当前位置和下一个位置当作偶数行回文的最中间两个字符，然后向两边进行搜索，参见代码如下：解法一：我们也可以不使用子函数，直接在一个函数中搞定，我们还是要定义两个变量 start 和 maxLen，分别表示最长回文子串的起点跟长度，在遍历s中的字符的时候，我们首先判断剩余的字符数是否小于等于 maxLen 的一半，是的话表明就算从当前到末尾到子串是半个回文串，那么整个回文串长度最多也就是 maxLen，既然maxLen 无法再变长了，计算这些就没有意义，直接在当前位置 break 掉就行了。否则就要继续判断，我们用两个变量 left 和 right 分别指向当前位置，然后我们先要做的是向右遍历跳过重复项，这个操作很必要，比如对于 noon，i在第一个o的位置，如果我们以o为最中心往两边扩散，是无法得到长度为4的回文串的，只有先跳过重复，此时left指向第一个o，right指向第二个o，然后再向两边扩散。而对于 bob，i在第一个o的位置时，无法向右跳过重复，此时 left 和 right 同时指向o，再向两边扩散也是正确的，所以可以同时处理奇数和偶数的回文串，之后的操作就是更新 maxLen 和 start 了，跟上面的操作一样，参见代码如下：解法二：此题还可以用动态规划 Dynamic Programming 来解，根Palindrome Partitioning II的解法很类似，我们维护一个二维数组 dp，其中 dp[i][j] 表示字符串区间 [i, j] 是否为回文串，当 i = j 时，只有一个字符，肯定是回文串，如果 i = j + 1，说明是相邻字符，此时需要判断 s[i] 是否等于 s[j]，如果i和j不相邻，即 i – j >= 2 时，除了判断 s[i] 和 s[j] 相等之外，dp[i + 1][j – 1] 若为真，就是回文串，通过以上分析，可以写出递推式如下：dp[i, j] = 1 if i == j = s[i] == s[j] if j = i + 1 = s[i] == s[j] && dp[i + 1][j – 1] if j > i + 1 这里有个有趣的现象就是如果我把下面的代码中的二维数组由 int 改为 vector
相关推荐: ConcurrentHashMap是怎么实现线程安全的
这篇文章主要介绍“ConcurrentHashMap是怎么实现线程安全的”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“ConcurrentHashMap是怎么实现线程安全的”文章能帮助大家解决问题。我们知道，在日常开发…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
