palindrome.java

9. Palindrome Number  (easy)

实质：回文数字

Determine whether an integer is a palindrome.

121-> true ; -121 -> false; 10 -> false 

解法：

1. 取出每个位上的数字，算出翻转数，与原数比较
   O(n)
       public boolean isPalindrome(int x) {
       		if(x < 0) return false;
               int re = 0, xx = x; //需要新变量xx记录原始值
               while(x > 0){
                   re *= 10;
                   re += x % 10;
                   x /= 10;
               }
               return re == xx;
           }
   
2. 【√】小改进：只需比较一半
   O(n/2)
       public boolean isPalindrome(int x) {
           if (x<0 || (x!=0 && x%10==0)) return false; //判断条件增加(10，20)的情况
           int rev = 0;
           while (x>rev){ 	//循环条件
           	rev = rev*10 + x%10;
           	x = x/10;
           }
           return (x==rev || x==rev/10); //返回也是2种情况
       }
3. tricky处：要不要考虑int溢出
   
   125. Valid Palindrome  (easy)
   实质：回文字符串
   Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
   Note: For the purpose of this problem, we define empty string as valid palindrome.
   Example 1:
       Input: "A man, a plan, a canal: Panama"
       Output: true
   Example 2:
       Input: "race a car"
       Output: false
   解法：
   1. 【√】使用Character函数，跳过非法字符( ! isLetterOrdigit)，注意大小写(toLowerCase)
          public boolean isPalindrome(String s) {
                  if(s.length()==0) return true; //空字符true
                  int start=0, end=s.length()-1;
                  while(start<end){
                      char cs = s.charAt(start);
                      char ce = s.charAt(end);
                      if(!Character.isLetterOrDigit(cs)) start++; //跳过非数字字母
                      else if(!Character.isLetterOrDigit(ce)) end--; //跳过非数字字母
                      else{
                          if(Character.toLowerCase(cs)!=Character.toLowerCase(ce)) //转小写比较
                              return false;
                          start++; //勿忘指针移动
                          end--;
                      }
                  }
                  return true;
              }
      
   2. 使用regex和自带函数（不推荐）
          //String：toLowerCase()函数
          //StringBuffer：reverse()函数
          public boolean isPalindrome(String s) {
                  String actual = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
                  String rev = new StringBuffer(actual).reverse().toString(); 
                  return actual.equals(rev);
              }



234. Palindrome Linked List  (easy)

实质：回文链表

Given a singly linked list, determine if it is a palindrome.

Example 1:

    Input: 1->2
    Output: false

Example 2:

    Input: 1->2->2->1
    Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

知识点：

对于快慢指针找中点：

- 如果从dummy出发，slow在中点偏左(偶数偏左); 
- 如果从head出发，slow在中点偏右(偶数偏右)；
- 奇数没影响，都是中点

解法：

【√】快慢指针： 

快慢指针找中点；

后半段reverse，和前半段比较    

    class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head == null || head.next == null) return true;
            
            ListNode fast = head;
            ListNode slow = head;
            while(fast != null && fast.next != null){ //注意判断条件是2个，有.next的都得判断非空
                fast = fast.next.next;
                slow = slow.next;
            }
         //停下时，如果是偶数个，slow在后一半第一个，fast在结尾null；如果是奇数个，slow在最中间，fast在结尾
            
            ListNode newHead = reverse(slow);
            while(head.next != null){  //newHead可能比head链多一个元素，所以判断head链
                if(newHead.val != head.val){
                    return false;
                }
                newHead = newHead.next;
                head = head.next;
            }
            return true;
        }
        
        public ListNode reverse(ListNode head){
            ListNode pre = null;
            ListNode cur = head;
            while(cur != null){
                ListNode temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            return pre;
        }
    }

409. Longest Palindrome  (easy)

实质：原字母重新组合成最长回文

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Example:

    Input:
    "abccccdd"
    
    Output:
    7
    
    Explanation:
    One longest palindrome that can be built is "dccaccd", whose length is 7.

思路：数出这些字符一共多少对 (HashMap/HashSet思想相同，同一种解法)

解法：

    ##### 1. HashMap 

如果map的某元素v个数为2，就从map中删除，count++

    public int longestPalindrome(String s) {
            if(s == null || s.length() == 0) return 0;
            HashMap<Character, Integer> map = new HashMap<>();
            int pair = 0;
            for(int i = 0; i < s.length(); i++){
                char c = s.charAt(i);
                map.put(c, map.getOrDefault(c, 0) + 1);
                if(map.get(c) == 2){
                    pair++;
                    map.remove(c);
                } 
            }
            int res = 0;
            res = map.size() == 0 ? pair * 2 : pair * 2 + 1;
            return res;
        }



2.【√】HashSet

如果元素已存在，就从set中删除，count++

    public int longestPalindrome(String s) {
            if(s==null || s.length()==0) return 0;
            HashSet<Character> hs = new HashSet<Character>();
            int count = 0;
            for(int i=0; i<s.length(); i++){
                char c = s.charAt(i);
                if(hs.contains(c)){
                    hs.remove(c);
                    count++;
                }else{
                    hs.add(c);
                }
            }
            if(!hs.isEmpty()) return count*2+1;
            return count*2;



3. 【√】int[128]

int[128] 数组统计字母出现频率。pairs*2(+1)

    // 自己写。速度最快，beat 99.7%
    public int longestPalindrome(String s) {
            if(s == null || s.length() == 0) return 0;
            int[] count = new int[128];
            for(char c : s.toCharArray()){
                count[c]++;
            }
            int pairs = 0;
            boolean hasSingle = false;
            for(int ct : count){
                if(ct % 2 != 0){
                    hasSingle = true;
                }
                pairs += ct / 2;
            }
            return hasSingle? pairs *2 + 1 : pairs * 2;
        }

别人解法，分别建2个int[26]存大小写字母

    //以下为别人优解，省了空间，但个人认为可以不用这么细，直接int[128]即可
    public int longestPalindrome(String s) {
        int[] lowercase = new int[26];
        int[] uppercase = new int[26];
        int res = 0;
        for (int i = 0; i < s.length(); i++){
            char temp = s.charAt(i);
            if (temp >= 97) lowercase[temp-'a']++; //小写
            else uppercase[temp-'A']++; //大写
        }
        for (int i = 0; i < 26; i++){
            res+=(lowercase[i]/2)*2;
            res+=(uppercase[i]/2)*2;
        }
        return res == s.length() ? res : res + 1; //需要判断：计算出配对总数 == 实际总数 ？      
    }



补充知识（ASCII码）：

48-57：0~9

65-90：A~Z

97-122：a~z

0~127这128位已经包含了所有大小写字母及数字；

扩展ASCII码则为256位（均为不常用字符：如制表符，上标字母等，一般用不到）。

479. Largest Palindrome Product  (easy)

Find the largest palindrome made from the product of two n-digit numbers.

Since the result could be very large, you should return the largest palindrome mod 1337.

Example: Input: 2, Output: 987, Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Note: The range of n is [1,8].

略。偏数学，题目不好。

大概思路：找到10^n范围最大数（上限）最小数（下限），找到maxNumber（最大数*最大数），再找它的first half。 while当没有找到时（!palinFound），根据first half生成理想化最大回文乘积palindrome， 从上限到下限往下找某个数i，能被palindrome整除。找不到就first half减1，继续找。

举例：n=3， upperBound = 999,  lowerBound = 99， maxNumber=999*999=998001, firstHalf=998,  palindrome=998899



680. Valid Palindrome II  (easy)

实质：最多删一个字符，能否组成回文串

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

    Input: "aba"
    Output: True

Example 2：

    Input: "abca"
    Output: True
    Explanation: You could delete the character 'c'.

Note:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

解法：【√】双指针，遇到不相同字符时不能立即false，需要再判断子串(i+1, j)和(i, j+1)是否回文    

    class Solution {
        public boolean validPalindrome(String s){
            int i = 0, j = s.length() - 1;
            while(i < j && s.charAt(i) == s.charAt(j)){
                i++;
                j--;
            }
            if(s.charAt(i) != s.charAt(j)){
                return isPalindrome(i + 1, j, s) || isPalindrome(i, j - 1, s); //注意不能i++,j--
            }
            return true;
        }
        public boolean isPalindrome(int i, int j, String s){
            while(i < j){
                if(s.charAt(i++) != s.charAt(j--)){
                    return false;
                }
            }
            return true;
        }
    }

函数用for另一种写法：

    public boolean validPalindrome(String s){
            for(int i = 0, j = s.length() - 1; i < j; i++, j--){
                if(s.charAt(i) != s.charAt(j)){
                    return isPalindrome(i + 1, j, s) || isPalindrome(i, j - 1, s);
                }
            }
            return true;
        }



5. Longest Palindromic Substring (medium)

实质：最长回文子串

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

    Input: "babad"
    Output: "bab"
    Note: "aba" is also a valid answer.

Example 2:

    Input: "cbbd"
    Output: "bb"

解法：

1. 【√】从中(两)点向两边扩散，Expand around center

思路：对每一个字符进行扩散（2种情况：中间一点，中间两点），更新最大长度和最长子串

时间：O(n^2)   空间：O(1)

     class Solution {
        int maxLen = 0;
        String longest = "";
        public String longestPalindrome(String s) {
            if(s == null || s.length() == 0) return longest;
            for(int i = 0; i < s.length(); i++){ //注意包括0和n-1
                expand(i, i, s); //情况1
                expand(i, i + 1, s); //情况2
            }
            return longest;
        }
        public void expand(int i, int j, String s){
            while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)){ //注意包括0和n-1
                i--;
                j++；
            }
            String sub = s.substring(i + 1, j);
            if(sub.length() > maxLen){
                maxLen = sub.length();
                longest = sub;
            }
        }
    }

1. DP
   时间：O(n^2)   空间：O(n^2)
   思路：
   P(i,j)=( P(i+1,j−1) and Si==Sj )
   - P(i, i) = true
   - P(i, i+1) = (Si==Si+1)
       public String longestPalindrome(String s) {
         int n = s.length();
         String res = null; 
         boolean[][] dp = new boolean[n][n]; 
         for (int i = n - 1; i >= 0; i--) {
           for (int j = i; j < n; j++) {
             dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);      
             if (dp[i][j] && (res == null || j - i + 1 > res.length())) {
               res = s.substring(i, j + 1);
             }
           }
         }  
         return res;
       }