LC-字符串专题(一)

发表于 | 分类于
字数统计: 2,798

3 无重复字符的最长子串【中】


思路：感觉有点难的亚子..因为重复出现的位置无法预料，那么下一次寻找的开始位置如何确定，难道用暴力解法依次遍历？首次，如何判断和记录重复，每次用一个哈希表？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0, start = 0; end < n; end++) {
            char alpha = s.charAt(end);
            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }
            ans = Math.max(ans, end - start + 1);
            map.put(s.charAt(end), end + 1);
        }
        return ans;
    }
}
  • 用滑动窗口替代复杂度为$O(n^2)$的暴力解法，核心是要记录下重复位置用于窗口滑动
  • 定义一个 map 数据结构存储 (k, v)，Map<Character, Integer> map = new HashMap<>();其中 key 值为字符，value 值为字符位置 +1，加 1 表示从字符位置后一个才开始不重 复, 同时存位置的方法可以从始至终只用一个哈希表即可
  • start = Math.max(map.get(alpha), start);start取更大的值，一方面start保证不会后退；另一方面value 值为重复字符上一次的位置 +1，下一次的最长必不包含本次重复的这一段，故直接跳到本次重复第一个字符的下一位置
    +无论是否更新 start，都会更新其 map 数据结构和结果 ans ans = Math.max(ans, end - start + 1);
  • 字符串方法:string.length() string.charAt(pos)
  • hashmap方法:hashmap.containsKey(key) hashmap.put(key,value)
  • Math.max(value1,…)
  • 哈希表还可以直接用int[26] 来代替

时间复杂度：$O(n)$
空间复杂度：$O(min(n,m))$ m为字符集大小

5 最长回文子串【中】

思路:一般来说回文可以用栈判断，但这是一个动态问题。如果用栈的话，什么时候弹出其实感觉比较难判断。不如用双指针?

暴力解法

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
public boolean isPalindromic(String s) {
		int len = s.length();
		for (int i = 0; i < len / 2; i++) {
			if (s.charAt(i) != s.charAt(len - i - 1)) {
				return false;
			}
		}
		return true;
	}

public String longestPalindrome(String s) {
    String ans = "";
    int max = 0;
    int len = s.length();
    for (int i = 0; i < len; i++)
        for (int j = i + 1; j <= len; j++) {
            String test = s.substring(i, j);
            if (test.length() > max && isPalindromic(test)) {
                max = test.length();
                ans = test;
                
            }
        }
    return ans;
}
  • 用双指针判断回文

时间复杂度：$O(n^3)$
空间复杂度：$O(1)$

暴力破解优化1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public String longestPalindrome(String s) {
    int length = s.length();
    boolean[][] P = new boolean[length][length];
    int maxLen = 0;
    String maxPal = "";
    for (int len = 1; len <= length; len++) //遍历所有的长度
        for (int start = 0; start < length; start++) {
            int end = start + len - 1;
            if (end >= length) //下标已经越界，结束本次循环
                break;
            P[start][end] = (len == 1 || len == 2 || P[start + 1][end - 1]) && s.charAt(start) == s.charAt(end); //长度为 1 和 2 的单独判断下
            if (P[start][end] && len > maxLen) {
                maxPal = s.substring(start, end + 1);
            }
        }
    return maxPal;
}

  • boolean[][] P = new boolean[length][length] 存储判断结果矩阵
  • 最外层按长度来遍历
  • 长度为 1 和 2 的单独判断，然后基于其向两边拓展

时间复杂度：$O(n^2)$ 空间换时间
空间复杂度：$O(n^2)$ — 可以优化

暴力破解优化2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public String longestPalindrome7(String s) {
		int n = s.length();
		String res = "";
		boolean[] P = new boolean[n];
		for (int i = n - 1; i >= 0; i--) {
			for (int j = n - 1; j >= i; j--) {
				P[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || P[j - 1]);
				if (P[j] && j - i + 1 > res.length()) {
					res = s.substring(i, j + 1);
				}
			}
		}
		return res;
	}
  • 下一对角线的遍历只用到了相邻的更长对角线的结果，那么用长度为n的数组，结果不断覆盖
  • 根据递推公式，采用倒序遍历
  • j-i+1为字符串长度len，len为1或者2,所以len<3即j-i<2,而用一维数组存储结果时len=1都为ture，所以长度为3只需要判断两端字符是否相等

时间复杂度：$O(n^2)$ 空间换时间
空间复杂度：$O(n)$

动态规化

再用一个逆序字符串，转化为最长公共子串问题，但是效率并不太高

中心扩展法

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() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}
  • 从一个字符开始扩展，或者从两个字符之间开始扩展，所以总共有 n+n-1 个中心
  • start = i - (len - 1) / 2;end = i + len / 2; 确定回文字符串的起止位置

时间复杂度：$O(n^2)$
空间复杂度：$O(1)$ — 充分利用了回文对称的特点

Manacher’s 算法

一个讲解的不错的视频

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
public String preProcess(String s) {
    int n = s.length();
    if (n == 0) {
        return "^$";
    }
    String ret = "^";
    for (int i = 0; i < n; i++)
        ret += "#" + s.charAt(i);
    ret += "#$";
    return ret;
}

// 马拉车算法
public String longestPalindrome2(String s) {
    String T = preProcess(s);
    int n = T.length();
    int[] P = new int[n];
    int C = 0, R = 0;
    for (int i = 1; i < n - 1; i++) {
        int i_mirror = 2 * C - i;
        if (R > i) {
            P[i] = Math.min(R - i, P[i_mirror]);// 防止超出 R
        } else {
            P[i] = 0;// 等于 R 的情况
        }

        // 碰到之前讲的三种情况时候，需要利用中心扩展法
        while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
            P[i]++;
        }

        // 判断是否需要更新 R
        if (i + P[i] > R) {
            C = i;
            R = i + P[i];
        }

    }

    // 找出 P 的最大值
    int maxLen = 0;
    int centerIndex = 0;
    for (int i = 1; i < n - 1; i++) {
        if (P[i] > maxLen) {
            maxLen = P[i];
            centerIndex = i;
        }
    }
    int start = (centerIndex - maxLen) / 2; //最开始讲的求原字符串下标
    return s.substring(start, start + maxLen);
}
  • 加特殊字符 “#” 使字符串统一为奇数长度
  • 用一个数组 P 保存从中心扩展的最大个数，而它刚好也是去掉 “#” 的原字符串的总长度;用 P 的下标 i 减去 P [ i ]，再除以 2，就是原字符串的开头下标了
  • 相比于中心拓展法，利用了前半部分的对称信息; 对称时分三种情况来讨论

时间复杂度：$O(n)$
空间复杂度：$O(n)$

6 Z字形变换【中】


思路：竖向和斜向的字符数相等，如何建立输出顺序与排列方式的联系?每 n+n-2 个数视为一组，这组元素以除最高和最低点外，每行有两个数。可以建立规律,后面的情况+模即2n-2

找规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public String convert(String s, int numRows) {

        if (numRows == 1) return s;

        StringBuilder ret = new StringBuilder();
        int n = s.length();
        int cycleLen = 2 * numRows - 2;

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < n; j += cycleLen) {
                ret.append(s.charAt(j + i));
                if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                    ret.append(s.charAt(j + cycleLen - i));
            }
        }
        return ret.toString();
    }
}
  • StringBuilder 是一个可变对象，可以预分配缓冲区，这样，往StringBuilder中新增字符时，不会创建新的临时对象，支持链式操作。有.append(s) .insert(pos,s) .toString() 方法

时间复杂度：$O(n)$
空间复杂度：$O(n)$

按行排序

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
class Solution {
    public String convert(String s, int numRows) {
        if(numRows == 1)
            return s;
        
        int len = Math.min(s.length(), numRows);
        String []rows = new String[len];
        for(int i = 0; i< len; i++) rows[i] = "";
        int loc = 0;
        boolean down = false;

        for(int i=0;i<s.length();i++) {
            rows[loc] += s.substring(i,i+1);
            if(loc == 0 || loc == numRows - 1)
                down = !down;
            loc += down ? 1 : -1;
        }
        
        String ans = "";
        for(String row : rows) {
            ans += row;
        }
        return ans;
    }
}
  • 用字符串数组来存储，+号直接拼接在后面
  • 用向下或向右来控制row是增还是减
  • loc == 0 || loc == numRows - 1 每到顶点时变换方向

时间复杂度：$O(n)$
空间复杂度：$O(n)$

8 字符串转换整数(atoi)【 中】


思路：寻找第一个非空格字符，没找到不转换。找到后若不是正负号也不是数字，不转换。若是正负号，记录符号，接着计算数值，计算数值：可以用栈？ 连续数值之后的字符可以忽略。计算出整数值之后还要判断是否在有效区间内，溢出返回最大或最小值。

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
class Solution {
    public int myAtoi(String str) {
        int i = 0, j = 0, len = str.length();
        boolean negative = false;
        for (i = 0; i < len; i++) {
            if ('0' <= str.charAt(i) && str.charAt(i) <= '9') {
                break;
            } else if (str.charAt(i) == '-' || str.charAt(i) == '+') {
                negative = str.charAt(i) == '-';
                i++;
                break;
            } else if (str.charAt(i) != ' ') {
                return 0;
            }
        }
        for (j = i; j < len; j++) {
            if (str.charAt(j) < '0' || '9' < str.charAt(j)) {
                break;
            }
        }
        int ret = 0;
        String num = str.substring(i, j);
        for (int x = 0; x < num.length(); x++) {
            int cur = num.charAt(x) - '0';
            if (negative) {
                if (ret < Integer.MIN_VALUE / 10|| ret == Integer.MIN_VALUE / 10 && cur > 8) {
                    return Integer.MIN_VALUE;
                }
                ret = ret * 10 - cur;
            } else {
                if (ret > Integer.MAX_VALUE / 10 || ret == Integer.MAX_VALUE / 10 && cur > 7) {
                    return Integer.MAX_VALUE;
                }
                ret = ret * 10 + cur;
            }
        }
        return ret;
    }
}
  • 注意判断条件，哪些是可以并列的，以及先后顺序
  • 直接用ret迭代，不用栈
  • 32 位有符号整数范围 -2147483648 ～ +2147483647
  • 如果没有+号这个溢出判断是不是有什么问题?范围缩小位?

时间复杂度：$O(n)$
空间复杂度：$O(1)$

10 正则表达式匹配【难】


思路：首先这是一个匹配问题，由于正则的存在使得模式串有极多的可能性，如何确定一某合理的比较顺序?若是字母，判断对应位是否相等？不等为false。为．继续匹配下一位。为*时，若前面无字符，继续；有字符，先移动继续移动目标串直至不为该字符，特别的若该字符为．，若已处于模式串末尾返回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
class Solution {
    public boolean isMatch(String s, String p) {
        if(s==null || p==null) return false;
        int sIndex=0,pIndex=0;
        return matchCore(s,sIndex,p,pIndex); 
    }
    public boolean matchCore(String s,int sIndex,String p,int pIndex){
        if(sIndex==s.length() && pIndex==p.length()) return true;
        if(sIndex <s.length() &&  pIndex==p.length()) return false;
        if(pIndex+1<p.length() && p.charAt(pIndex+1)=='*'){
            //① sIndex+1：继续用*匹配下一个 ②pIndex+2：当*前面的字符没有出现过
            if((sIndex < s.length() && p.charAt(pIndex)==s.charAt(sIndex))||(sIndex <s.length() && p.charAt(pIndex)=='.')){
                return matchCore(s,sIndex+1,p,pIndex)  || matchCore(s,sIndex,p,pIndex+2);
            }else{//第一个匹配不上，认为其没出现过，判断下面的
                return matchCore(s,sIndex,p,pIndex+2);
            }
        }else{//模式的第二个不是*，匹配上就下一个，匹配不上就结束
             if((sIndex < s.length() && p.charAt(pIndex)==s.charAt(sIndex))||(sIndex < s.length() && p.charAt(pIndex)=='.')){
                 return matchCore(s,sIndex+1,p,pIndex+1);
             }else{
                 return false;
             }
        }
    }
}

+return matchCore(s,sIndex+1,p,pIndex) || matchCore(s,sIndex,p,pIndex+2);精髓

一个较好的视频讲解