首页 LeetCode刷题

# 回文串

回文的概念就是一个序列正着来倒着来是一样的，比如回文数字 12321 ，回文字符串 abbccdccbba ，诸如此类。

# 判断是否是回文串

一般就是两头对比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean isPalindrome(String s) {
    int len = s.length();
    for (int i = 0; i < len; i++) {
        if (s.charAt(i) != s.charAt(len - i - 1)){
            return false;
        }
    }
    return true;
}
// 或者
public boolean isPalindrome(String s) {
    int len = s.length();
    int i = 0;
    int j = len -1;
    while(i < j){
        if(s.charAt(i) != s.charAt(j)){
            return false;     
        }
        i++;
        j--;
    }
    return true;
}

使用 StringBuffer 反转后比较

1
2
3
public boolean isPalindrome(String s) {
    return new StringBuffer(str).reverse().toString().equals(str);
}

# 题目

# 简单难度

# 验证回文串

[125. 验证回文串][https://leetcode.cn/problems/valid-palindrome/]

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s ，如果它是 回文串 ，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean isPalindrome(String s) {
        // 去除非字母数字的字符
        s = s.replaceAll("[^a-zA-Z0-9]", "");
        // 全部转换为小写
        s = s.toLowerCase();
        // 字符串翻转比较
       return new StringBuffer(s).reverse().toString().equals(s);
    }
}

# 验证回文串 II

680. 验证回文串 II

给你一个字符串 s ，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

思路： 双指针

  • 考虑到只能删除一个，查找到第一对不相等的字符的时候会有两种情况。
    • 删除左侧的字符，删除右侧的字符。
    • 所以会有两个分支判断
  • 如果这个字符串符合题目的要求，那么删除后的字符串一定是回文的。
  • 当比较到第一对不相等的字符位置时，只需要考虑删除后的子串是否是回文的就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean validPalindrome(String s) {
        int len = s.length();
        boolean flag = true;
        int i = 0;
        int j = len -1;
        while(i < j){
            if(s.charAt(i) != s.charAt(j)){
                return jud(s.substring(i+1, j+1)) || jud(s.substring(i, j));     
            }else {
                i++;
                j--;
            }
        }
        return true;
    }
    boolean jud(String str){
        return new StringBuffer(str).reverse().toString().equals(str);
    }
}

注意： subString 方法在取字符串时左闭右开， [a,b)

# 回文数

9. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

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

  • 例如， 121 是回文，而 123 不是。
  • -121 ， 从右向左读，为 121- 。因此它不是一个回文数。

思路：

  • 首先排除负数
  • 以若干连续 0 结尾的数也不是回文的

# 直接数转化字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isPalindrome(int x) {
        // 负数直接拜拜
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        String str = x + "";
        int len = str.length();
        // return new StringBuffer(str).reverse().toString().equals(str);
        for (int i = 0; i < len; i++) {
            if (str.charAt(i) != str.charAt(len - i - 1)){
                    return false;
            }
        }
        return true;
    }
}

# 使用数字解决，可以使用折半思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isPalindrome(int x) {
        //思考：这里大家可以思考一下，为什么末尾为 0 就可以直接返回 false
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int revertedNumber = 0;
        // 翻转到一般就行
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        // 考虑数字的位数是奇数和偶数
        return x == revertedNumber || x == revertedNumber / 10;
    }
}

# 最长回文串 - 简单

给一个包含大写字母和小写字母的字符串 s ，返回 这些字母构造成的 最长的回文串 。

在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

思路：

  • 题目问的是这些字母拼成的字符串，只需要考虑各个字母的数量即可
  • 根据各个字母的数量的奇偶，有两种情况
    • 回文串字符数量为奇数，用了一个奇数数量的字母
    • 回文串字符数量为偶数，所有字母的数量都为偶数
  • 开一个数组存各个字符数量
  • 第一个奇数数量的字符可以全部加到回文串中
  • 之后的字符数量只能为偶数加入回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int longestPalindrome(String s) {
        int[] count = new int[60];
        for (char ch : s.toCharArray()) {
            count[ch - 'A']++;
        }
        int res = 0;
        boolean flag = true;
        for (int i = 0; i < 60; i++) {
            if((count[i] & 1) == 1 && flag){
                res++;
                flag = false;
            }
            res += ((count[i] >> 1) << 1);
        }
        return res;
    }
}

使用 Java 的流进行优化一下

1
2
3
4
5
6
7
public int longestPalindrome(String s) {
    Map<Integer, Integer> count = s.chars().boxed()
        .collect(Collectors.toMap(k -> k, v -> 1, Integer::sum));

    int ans = count.values().stream().mapToInt(i -> i - (i & 1)).sum();
    return ans < s.length() ? ans + 1 : ans;
}

# 回文链表

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

折半思想，使用快慢指针找到中间节点，之后的链表翻转，最后比较就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode mid = midNode(head);
        ListNode cmp = reverseList(mid);
        while (head != null && cmp != null) {
            if(head.val != cmp.val){
                return false;
            }
            head = head.next;
            cmp = cmp.next;
        }
        return true;
    }

    private ListNode midNode(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode reverseList(ListNode mid) {
        ListNode pre = null;
        ListNode cur = mid;
        while(cur !=null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

# 中等难度

# 最长回文子串

5. 最长回文子串

给你一个字符串 s ，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

暴力的话会超时，可以用中心扩散法或动态规划

# 中心扩散法

思路：

  • 遍历，选择一个元素 i
  • 两个指针，从元素左 left = i-1 右 right = i+1 开始比较
    • 如果左指针元素与 i 位置元素相等，左指针左移，否则不变
    • 右指针同理，右移
    • 之后比较两指针所指元素
    • 上述过程的好处是泛化了回文串的字符奇数偶数问题，使得该方法适用
  • 每次选择中间元素 i 记录最大长度和起始位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public String longestPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return "";
    }
    int strLen = s.length();
    int left = 0;
    int right;
    int len;
    int maxStart = 0;
    int maxLen = 0;

    for (int i = 0; i < strLen; i++) {
        left = i - 1;
        right = i + 1;
        len = 1;
        while (left >= 0 && s.charAt(left) == s.charAt(i)) {
            len++;
            left--;
        }
        while (right < strLen && s.charAt(right) == s.charAt(i)) {
            len++;
            right++;
        }
        while (left >= 0 && right < strLen &&s.charAt(right) == s.charAt(left)) {
            len = len + 2;
            left--;
            right++;
        }
        if (len > maxLen) {
            maxLen = len;
            maxStart = left;
        }
    }
    return s.substring(maxStart + 1, maxStart + maxLen + 1);
}

# 动态规划

适用动态规划，首先要想状态转移，对于回文串，我们可以认为回文串的状态转移是从头尾向中间走。

  1. 定义状态，使用 dp[i][j] 记录子串 [i,j] 是否回文

  2. 状态转移方程：首先要 s[i] == s[j] ，其次是 dp[i-1][j+1] == true

    注意 i - 1 != j + 1 ，所以要求子串长度大于等于 2

    1
    dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public String longestPalindrome(String s) {
    if (s == null || s.length() < 2) {
        return s;
    }
    int strLen = s.length();
    int maxStart = 0;  //最长回文串的起点
    int maxLen = 1;  //最长回文串的长度

    boolean[][] dp = new boolean[strLen][strLen];

    for (int r = 1; r < strLen; r++) {
        for (int l = 0; l < r; l++) {
            if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                dp[l][r] = true;
                if (r - l + 1 > maxLen) {
                    maxLen = r - l + 1;
                    maxStart = l;
                }
            }
        }
    }
    return s.substring(maxStart, maxStart + maxLen);
}

更新于 阅读次数 次 本文阅读量:

请我喝[茶]~(￣▽￣)~*

Windlinxy 微信支付

微信支付

Windlinxy 支付宝

支付宝