关于回文问题
回文问题的解法：双指针，栈，reverse
1. 409. 最长回文串[✔]
2. 125. 验证回文串[✔]
3. 5. 最长回文子串（返回子串）[✔]
4.NC17最长回文子串（返回子串长度）研发最爱考[✔]
5. 516. 最长回文子序列[✔]
6.NC96判断一个链表是否为回文结构研发最爱考[✔]
1. 409. 最长回文串[✔]
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例 1:
输入:"abccccdd"，输出:7
解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
思路：HashSet
将字符串转换为字符数组，遍历该数组，判断对应字符是否在HashSet中，如果不在，则加入；如果在，就让count++并移除该字符。这样能够找到出现次数为双数的字符个数。构成回文串有两种情况：字符出现次数为双数的组合和字符出现次数为双数的组合+一个只出现一次的字符。类似于打牌。
class Solution {
public int longestPalindrome(String s) {
if(s.length() == 0) return 0;
HashSet<Character> set = new HashSet<>();
char[] chs = s.toCharArray();
int count = 0;
for(int i = 0; i < chs.length; i++){
if(!set.contains(chs[i])){
set.add(chs[i]);
}else{
set.remove(chs[i]);
count++;
}
}
return set.isEmpty() ? count * 2 : count * 2 + 1;
}
}
2. 125. 验证回文串[✔]
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
思路：双指针
使用双指针，一个指向前，一个指向后，从头和尾开始向中间遍历，遇到空格以及特殊字符要跳过，然后判断。
class Solution {
public boolean isPalindrome(String s) {
if (s == null || s.length() == 0)
return true;
s = s.toLowerCase();
int i = 0;
int j = s.length() - 1;
while(i < j){
if(!Character.isLetterOrDigit(s.charAt(i))){
i++;
continue;
}
if(!Character.isLetterOrDigit(s.charAt(j))){
j--;
continue;
}
if (s.charAt(i) != s.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}
}
3. 5. 最长回文子串
给定一个字符串
s，找到s中最长的回文子串。你可以假设s的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
思路一：动态规划
class Solution {
public String longestPalindrome(String s) {//执行用时 :138 ms, 在所有 Java 提交中击败了33.51%的用户
int len = s.length();
if(len < 2)
return s;//此时一定是回文串
boolean[][] dp = new boolean[len][len];//定义状态dp[i][j]表示子串s[i, j]是否为回文子串
for(int i=0;i<len;i++){
dp[i][i] = true;//初始化，单个字符一定是回文串
}
int maxLen = 1;
int start = 0;
for(int i=len-2;i>=0;i--){//i要降序（因为dp[i][j] = dp[i+1][j-1]）
for(int j=i+1;j<len;j++){//j要升序（因为dp[i][j] = dp[i+1][j-1]）
if(s.charAt(i) == s.charAt(j)){
if(j-i<3){//(j-1)-(i+1)+1<2，即为[i+1, j-1]不构成区间，边界条件，dp值可以直接判断
dp[i][j] = true;
}else{
dp[i][j] = dp[i+1][j-1];//状态转移方程
}
}else{
dp[i][j] = false;
}
if(dp[i][j]){//子串s[i, j]是回文子串时，记录长度和起始位置
int currentLen = j-i+1;
if(currentLen > maxLen){
maxLen = currentLen;
start = i;
}
}
}
}
return s.substring(start, start+maxLen);//最长的回文子串
}
}
思路二：中心扩散法
class Solution {
int index = 0;
int len = 0;
public String longestPalindrome(String s) {
if(s.length() < 2) return s;
for(int i = 0; i < s.length(); i++){
// left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
// right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
PalindromeHeper(s, i, i);
PalindromeHeper(s, i, i + 1);
}
return s.substring(index, index + len);
}
public void PalindromeHeper(String s, int l, int r){
while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
l--;
r++;
}
if(len < r - l - 1){
index = l + 1;
len = r - l - 1;
}
}
}
4.NC17最长回文子串研发最爱考[✔]
题目描述:
对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
给定字符串A以及它的长度n，请返回最长回文子串的长度。
测试样例：
"abc1234321ab",12
返回：7
思路：动态规划
1.定义状态：dp[i][j]表示子串A[ i , j ] 是否为回文串
2.考虑状态转移方程：
如果s[i] == s[j] ，那么dp[i][j] = false;
如果s[i] == s[j] ，那么分两种情况
(1)表达式 [i + 1, j - 1] 不构成区间，即长度严格小于 2，即 j - i < 3时，dp[i][j] = true
(2)表达式 [i + 1, j - 1] 可以构成区间，dp[i][j] = dp[i + 1][j - 1]
3.考虑初始化：单个字符一定是回文串，因此把对角线先初始化为 true，即 dp[i][i] = true
4.考虑输出：求的是最长回文子串的长度，因此当dp[i][i] = true时，就更新子串的长度
注意填表顺序，要想求得dp[i][j]要先知道dp[i + 1][j - 1]即为左下角的值，我想到的填表顺序是题解中的这种。
import java.util.*;
public class Palindrome {
public int getLongestPalindrome(String A, int n) {
// write code here
if(n < 2) return n;
//int len = 0;
int max = 1;
boolean[][] dp = new boolean[n][n];
for(int i = 0; i < n; i++){
dp[i][i] = true;
}
for(int i = n - 2; i >= 0; i--){
for(int j = i + 1; j < n; j++){
char[] c = A.toCharArray();
if(c[i] != c[j]){
dp[i][j] = false;
}else{
if(j - i < 3){
dp[i][j] = true;
}else{
dp[i][j] = dp[i + 1][j - 1];
}
}
if(dp[i][j] && j - i + 1 > max){
max = j - i + 1;
}
}
}
return max;
}
}
5. 516. 最长回文子序列
给定一个字符串
s，找到其中最长的回文子序列，并返回该序列的长度。可以假设s的最大长度为1000。
示例 1:
输入:"bbbab"
输出:4，一个可能的最长回文子序列为 "bbbb"。
提示：
1 <= s.length <= 1000s只包含小写英文字母
思路：动态规划
已知子问题 dp[i+1][j-1] 的结果（s[i+1..j-1] 中最长回文子序列的长度）
如果s[i] = s[j]，那么它俩加上 s[i+1..j-1] 中的最长回文子序列就是 s[i..j] 的最长回文子序列：
如果s[i] != s[j]，说明它俩不可能同时出现在 s[i..j] 的最长回文子序列中，那么把它俩分别加入 s[i+1..j-1] 中，看看哪个子串产生的回文子序列更长即可：
class Solution {
public int longestPalindromeSubseq(String s) {
int len = s.length();
int [][] dp = new int[len][len];
for(int i = 0 ; i < len; i++){
dp[i][i] = 1;
}
for(int i = len - 2; i >= 0; i--){
for(int j = i + 1; j < len; j++){
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i + 1][j - 1] + 2;
}
else{
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][len - 1];
}
}
6.NC96判断一个链表是否为回文结构研发最爱考[✔]
与 234. 回文链表相同[✔]
题目描述：
给定一个链表，请判断该链表是否为回文结构。
示例1：
输入：[1,2,2,1]，输出：true
备注：1≤n≤106
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题吗？
思路:
找到前半部分链表的尾节点，反转后半部分链表，判断是否为回文，恢复链表，返回结果
反转链表有两种方法：双指针迭代和递归
206. 反转链表
双指针迭代比较容易想到：
申请两个指针，第一个指针叫 pre，最初是指向 null 的。
第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了99.70%的用户，2020/08/04
public boolean isPalindrome(ListNode head) {
if(head == null) return true;
ListNode firstHalfEnd = findMid(head);//找到前半部分链表的尾节点
ListNode secondHalfStart = reverse(firstHalfEnd.next);//反转后半部分链表
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean res = true;
while(res && p2 != null){
if(p1.val != p2.val){
res = false;
}
p1 = p1.next;
p2 = p2.next;
}
firstHalfEnd.next = reverse(secondHalfStart);//恢复链表
return res;
}
//使用快慢指针找到前半部分链表的尾节点
//如果要求「在两个中间结点的时候，返回第一个中间结点]
//此时快指针可以前进的条件是：当前快指针的下一个结点和当前快指针的下下一个结点都非空
private ListNode findMid(ListNode head){
ListNode fast = head;
ListNode slow = head;
//while(fast != null && fast.next != null){
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
//反转链表：双指针迭代
private ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode tmpNext = cur.next;
cur.next = pre;
pre = cur;
cur = tmpNext;
}
return pre;
}
}
