字符串系列第二弹

一、简述

接着上一次字符串系列继续总结。上文主要讲了字符串匹配等，这次主要关注回文串。

二、验证回文串

125. 验证回文串

利用双指针

 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


class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            char c = Character.toLowerCase(s.charAt(left));
            char d = Character.toLowerCase(s.charAt(right));
            if (!valid(c)) {
                left++;
            } else if (!valid(d)) {
                right--;
            } else {
                if (c != d)
                    return false;
                left++;
                right--;
            }
        }
        return true;
    }

    public boolean valid(char c) {
        if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))
            return true;
        return false;
    }
}

409. 最长回文串

这个是从所有字符中找到可以凑成回文串的最大长度，直接利用贪心思想就可以。对于出现次数>=2的字符直接加上去。

5. 最长回文子串

暴力做法

对于每一个子串进行判断，可以进行剪枝。统计遍历过程中当前最大回文字串的长度，后续遍历以这个长度为起点

以任意两个位置作为回文串中心，不断扩展。

这里是遍历了所有中心，包括一个为中心，两个为中心，分别进行。

还有一种是修改一下字符串，每个字符见增加特殊字符，比如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


String palindrome(String s, int l, int r) {
    while (l >= 0 && r < s.length()
            && s.charAt(l) == s.charAt(r)) {
        l--;
        r++;
    }
    return s.substring(l+1, r);
}

public String longestPalindrome(String s) {
    String res = "";
    for (int i = 0; i < s.length(); i++) {
        String s1 = palindrome(s, i, i);
        String s2 = palindrome(s, i, i+1);
        res = res.length() > s1.length() ? res : s1;
        res = res.length() > s2.length() ? res : s2;
    }
    return res;
}

Manacher 马拉车算法

概念

回文右边界数组
回文直径、半径
回文中心点数组

左神的代码

 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 static char[] manacherString(String str) {
    char[] charArr = str.toCharArray();
    char[] res = new char[str.length() * 2 + 1];
    int index = 0;
    for (int i = 0; i < res.length; i++) {
        res[i] = (i & 1) == 0 ? '#' : charArr[index++];
    }
    return res;
}

public static int maxLcpsLength(String s) {
    if (s == null || s.length() == 0)
        return 0;
    char[] str = manacherString(s);
    int[] pArr = new int[str.length]; // 回文半径数组
    int C = -1;
    int R = -1;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i != str.length; i++) {
        // i 至少的回文区域，给到pArr[i]，综合了4个情况
        pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
        while (i + pArr[i] < str.length && i - pArr[i] > -1) {
            if (str[i + pArr[i]] == str[i - pArr[i]])
                pArr[i]++;
              else
                break;
        }
        if (i + pArr[i] > R) {
            R = i + pArr[i];
            C = i;
        }
        max = Math.max(max, pArr[i]);
    }
    return max - 1;
}

lc官方题解

 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
47
48


public String longestPalindrome(String s) {
    int start = 0, end = -1;
    StringBuffer t = new StringBuffer("#");
    for (int i = 0; i < s.length(); ++i) {
        t.append(s.charAt(i));
        t.append('#');
    }
    t.append('#');
    s = t.toString();
    List<Integer> arm_len = new ArrayList<>();
    int right = -1, j = -1;
    for (int i = 0; i < s.length(); i++) {
        int cur_arm_len;
        if (right >= i) {
            int i_sym = j * 2 - i;
            int min_arm_len = Math.min(arm_len.get(i_sym), right - i);
            cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
        } else {
            cur_arm_len = expand(s, i, i);
        }
        arm_len.add(cur_arm_len);
        if (i + cur_arm_len > right) {
            j = i;
            right = i + cur_arm_len;
        }
        if (cur_arm_len * 2 + 1 > end - start) {
            start = i - cur_arm_len;
            end = i + cur_arm_len;
        }
    }
    StringBuffer ans = new StringBuffer();
    for (int i = start; i <= end; ++i) {
        if (s.charAt(i) != '#') {
            ans.append(s.charAt(i));
        }
    }
    return ans.toString();
}

public int expand(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        --left;
        ++right;
    }
    return (right - left - 2) / 2;
}

三、字符串数值处理

67. 二进制求和

 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


class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1;
        int c = 0;
        while (i >= 0 || j >= 0 || c == 1) {
            int ac = i < 0 ? 0 : a.charAt(i) - '0';
            int bc = j < 0 ? 0 : b.charAt(j) - '0';
            int sum = ac + bc + c;
            // 可以利用求余、除2直接算
            if (sum == 0) {
                sb.append('0');
                c = 0;
            } else if (sum == 1) {
                sb.append('1');
                c = 0;
            } else if (sum == 2) {
                sb.append('0');
                c = 1;
            } else {
                sb.append('1');
                c = 1;
            }
            i--;
            j--;
        }
        return sb.reverse().toString();
    }
}

8. 字符串转换整数 (atoi)

这道题目跟着模拟就可以，主要有几个点：

前导空格
符号位：'+', ‘-’, ''
整数溢出

这里最简单就是用范围更大的long来替换、还可以直接进行判断。

 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


class Solution {
    public int myAtoi(String s) {
        char[] str = s.toCharArray();
        int sign = 1;
        long res = 0;
        int i = 0;
        while (i < str.length && str[i] == ' ')
            i++;
        char c = ' ';
        if (i < str.length)
            c = str[i];
        if (c == '-') {
            sign = -1;
            i++;
        }
        if (c == '+') {
            sign = 1;
            i++;
        }
        for (; i < str.length && isNum(str[i]); i++) {
            int cur = str[i] - '0';
            if ((long) ((res * 10 + cur) * sign) >= Integer.MAX_VALUE)
                return Integer.MAX_VALUE;
            if ((long) ((res * 10 + cur) * sign) <= Integer.MIN_VALUE)
                return Integer.MIN_VALUE;
            res = res * 10 + cur;
        }
        return (int)res * sign;
    }

    public boolean isNum(char c) {
        if (c >= '0' && c <= '9')
            return true;
        return false;
    }
}

class Solution {
    public int myAtoi(String s) {
        char[] str = s.toCharArray();
        int sign = 1;
        int num = 0;
        int i = 0;
        int n = str.length;
        while (i < n && str[i] == ' ') i++;
        if (i == n)
            return num;
        if (str[i] == '+') {
            i++;
        } else if (str[i] == '-') {
            sign = -1;
            i++;
        }

        for (; i < n; i++) {
            if (str[i] < '0' || str[i] > '9')
                break;
            if (num > Integer.MAX_VALUE / 10 || (num == Integer.MAX_VALUE / 10 && (str[i] - '0') > Integer.MAX_VALUE % 10)) {
                return sign == -1 ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            num = num * 10 + str[i] - '0';
        }
        return num * sign;
    }

}

65. 有效数字

12. 整数转罗马数字

就是列一个表格

还有方法是硬编码表，通过规律找到个十百千的对应关系。

 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


class Solution {

    int[] nums = new int[] {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] strs = new String[] {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            int i = binarySearch(num);
            num -= nums[i];
            sb.append(strs[i]);
        }
        return sb.toString();
    }

    public int search(int num) {
        int i;
        for (i = 0; i < nums.length; i++) {
            if (num >= nums[i])
                return i;
        }
        return i;
    }

    public int binarySearch(int num) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (num >= nums[mid])
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }
}

13. 罗马数字转整数

遍历直接加，如果遇到比前一个数字大，则再减去。

四、字符串杂项

14. 最长公共前缀

扫描，纵向、横向、二分

58. 最后一个单词的长度

这里主要是要跳过末尾空格，我的做法与151. 翻转字符串里的单词这道题一样，见字符串系列第一弹

38. 外观数列

五、总结

字符串的题目做起来看主要分为三大部分，虽然里面也有一些算法上的思想，比如双指针、分治、栈等等。这里面有的题还没完成，慢慢完善。

字符串匹配，这种类型有暴力匹配（递归或者迭代）、KMP 等其他算法，这两个都要掌握，尤其是里面的双指针思想，KMP思想。在正则匹配时，还有动态规划的运用。
回文串，这种也是双指针遍历。回文子串问题有暴力解法，但也带有编码技巧，还有就是用马拉车算法，这个算法有难度。要把回文子串的暴力解法O(n^2) 弄熟练。
模拟。其他的就是一些字符串模拟可以解决的问题，比如处理数值问题等。当然数值问题会有很多技巧和状态机的方法，其实本质还是模拟这个过程。重点是考验编码的细节，要保证逻辑的清晰。思想不难，但有时实现起来比较困难。