回文_回文游戏

9.回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121
输出: true
示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

思想：

• 反转 是否等于自己

public boolean isPalindrome(int x) {
 
    if (x < 0 || x % 10 == 0 && x != 0) { // 负数 各位是零的
      return false;
    }
    // 反转 是否等于自己
    int revert = 0;
    int temp = x;
    while (temp > 0) {
      revert = revert * 10 + temp % 10;
      temp = temp / 10;
    }
    return revert == x;
  }

 

5.最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

思想：

• 动态规划  空间换时间，初始值，方程

• boolean dp[ l ][ r ] 表示字符串从 i 到 j 这段是否为回文。试想如果 dp[ l ][ r ]=true，我们要判断 dp[ l-1 ][ r+1 ] 是否为回文。只需要判断字符串在( l-1 )和（ r+1 )两个位置是否为相同的字符。

• 当 l = r 时 ，为true；

• dp[ l ][ r ]=true 并且(l-1)和（r+1) 位置的字符相同 -> 此时 dp[l-1][r+1]=true

 // 动态规划
  public String longestPalindrome(String s) {
    if (s == null || s.length() < 2) {
      return s;
    }
    int len = s.length();
    boolean dp[][] = new boolean[len][len];
    int maxLen = 1;
    int start = 0, end = 0;
 
    for (int right = 1; right < len; right++) {
      for (int left = 0; left < right; left++) {
        if (s.charAt(left) == s.charAt(right)
            && (right - left <= 2 || dp[left + 1][right - 1])) { // 满足回文条件
          dp[left][right] = true;
 
          if (right - left + 1 > maxLen) { // 比较长度
            maxLen = right - left;
            start = left;
            end = right;
          }
        }
      }
    }
    return s.substring(start, end + 1);
  }

214. 最短回文串

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1:

输入: "aacecaaa"
输出: "aaacecaaa"
示例 2:

输入: "abcd"
输出: "dcbabcd"

思想：

• KMP算法 （***）O(n)
• 找到最长的回文子串，将剩余部分反转  O(n^2) 会超时

 /**
   回文子串是从s.charAt(0)开始的，找到最长的回文子串，然后把剩余的部分反转后添加到头部
   **/
  public String shortestPalindrome(String s) {
 
    if(s==null || s.length()<=1){
      return s;
    }
 
    int len=s.length();
    int i = len-1;
 
    while(i>=0){
      // 回文子串总是从0 开始验证, i 是从后往前找，所以第一次找到回文串一定是最长的
      if(isPalindrome(s,0,i)){
        break;
      }
      i--;
    }
 
    if(i== len-1){ // s 是回文串
      return s;
    }
 
    // 原串的回文 从0~i，截取i之后的 反转加入头部
    StringBuilder sb=new StringBuilder();
    sb.append(new StringBuilder(s.substring(i+1,len)).reverse()).append(s);
    return sb.toString();
  }
 
  private boolean isPalindrome(String s,int i,int j){
    while(i<=j){
      if(s.charAt(i)!=s.charAt(j)){
        return false;
      }
      i++;
      j--;
    }
    return true;
  }

234.回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思想：

• 快慢指针+翻转
• 注意节点是奇数个和偶数个

 public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
      return true;
    }
    ListNode fast = head, slow = head;
    ListNode reverse = head;
    ListNode pre = null;
    while (fast != null && fast.next != null) {
      fast = fast.next.next; // 快指针
      reverse = slow;
      slow = slow.next;
 
      reverse.next = pre; // 反转前半段
      pre = reverse;
    }
    if (fast != null) { // 奇数个节点  slow 是中间节点
      slow = slow.next;
    }
 
    while (reverse != null && slow != null) {
      if (reverse.val != slow.val) {
        return false;
      }
      reverse = reverse.next;
      slow = slow.next;
    }
    return true;
  }