风在路上
zdk
2022-03-04
目录

字符串

Table of Contents generated with DocToc (opens new window)

# 滑动窗口代码框架

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}
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

其中两处 ... 表示的更新窗口数据的地方，到时候你直接往里面填就行了。

而且，这两个 ... 处的操作分别是右移和左移窗口更新操作，等会你会发现它们操作是完全对称的。

因为滑动窗口很多时候都是在处理字符串相关的问题，Java 处理字符串不方便，所以本文代码为 C++ 实现。不会用到什么编程方面的奇技淫巧，但是还是简单介绍一下一些用到的数据结构，以免有的读者因为语言的细节问题阻碍对算法思想的理解：

unordered_map 就是哈希表（字典），它的一个方法 count(key) 相当于 Java 的 containsKey(key) 可以判断键 key 是否存在。

可以使用方括号访问键对应的值 map[key]。需要注意的是，如果该 key 不存在，C++ 会自动创建这个 key，并把 map[key] 赋值为 0。

所以代码中多次出现的 map[key]++ 相当于 Java 的 map.put(key, map.getOrDefault(key, 0) + 1)。

# 字符串相关题

# 1.(medium)无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2:

输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3:

输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

思路1 暴力：

容易想到使用暴力，枚举所有子串，使用双指针i(左)j(右)。ij初始均指向同一字符，使用一个HashMap来储存走过的各个字符出现的次数。

如果s.charAt(j)放入map后，value大于了2，证明出现重复字符了，所以将原来的map清空，然后将i移动到后一位，因为ij初始要保持位置一致，所以j=i。

如果s.charAt(j)放入map后，value不大于2，证明无重复，更新max长度，取与当前子串长度 j-i+1的大值。

代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0){
            return 0;
        }
        int i = 0;
        int j = 0;
        int max = 1;
        HashMap<Character,Integer> map = new HashMap<>();
        while(j<s.length()){
            char right = s.charAt(j);
            map.put(right,map.getOrDefault(right,0)+1);
            if(map.get(right)>1){
                i++;
                j = i;
                map.clear();
            }else{
                max = Math.max(max,j-i+1);
                j++;
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

思路2 滑动窗口+另一种利用hash表的优化方式：

1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；

2、如果当前字符 ch 包含在 map中，此时有2类情况： 1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca； 2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0；随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时 应该不变，left始终为2，子段变成 ba才对。

为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1)

另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！

代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0){
            return 0;
        }
        int i = 0;
        int j = 0;
        int max = 0;
        HashMap<Character,Integer> map = new HashMap<>();
        while(j<s.length()){
            char ch = s.charAt(j);
            if(map.containsKey(ch)){
                i = Math.max(map.get(ch)+1,i);
            }
            max = Math.max(max,j-i+1);
            map.put(ch,j);
            j++;
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

或：

public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0){
            return 0;
        }
        int maxLen = 0;
        HashMap<Character,Integer> map = new HashMap<>();
        for(int i=0,j=0;j<s.length();j++){
            char ch = s.charAt(j);
            if(map.containsKey(ch)){
                i = Math.max(map.get(ch)+1,i);
            }
            maxLen =  Math.max(maxLen,j-i+1);
            map.put(ch,j);
        }
        return maxLen;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

思路3：纯滑动窗口

一样先动右指针，扩大窗口，让每个字符window[ch]++，如果窗口进入一个字符后发现这个字符在窗口中的数量大于1了，证明出现了重复，然后就循环移动左指针收缩窗口，直到字符不重复，退出while时即窗口中所有元素都不重复了，此时更新一下最长子串即可

代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0){
            return 0;
        }
        int[] window = new int[256];
        int left = 0,right = 0;
        int max = 0;
        while(right<s.length()){
            char ch = s.charAt(right);
            right++;
            //字符进入窗口
            window[ch]++;
            //当进入窗口后这个字符数量如果大于了1，证明重复了
            //此时移动左指针收缩窗口，直到不重复
            while(window[ch]>1){
                char leftValue = s.charAt(left);
                left++;
                window[leftValue]--;
            }
            max = Math.max(max,right-left);
        }
        return max;
    }
}
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

# 2.(hard)最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 示例 2：

输入：s = "a", t = "a" 输出："a" 示例 3:

输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。

提示：

1 <= s.length, t.length <= 105 s 和 t 由英文字母组成

思路：

滑动窗口的思想： 用i,j表示滑动窗口的左边界和右边界，通过改变i,j来扩展和收缩滑动窗口，可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串T的所有元素，记录下这个滑动窗口的长度j-i+1，这些长度中的最小值就是要求的结果。

步骤一：不断增加j使滑动窗口增大，直到窗口包含了T的所有元素

步骤二：不断增加i使滑动窗口缩小，因为是要求最小字串，所以将不必要的元素排除在外，使长度减小，直到碰到一个必须包含的元素，这个时候不能再扔了，再扔就不满足条件了，记录此时滑动窗口的长度，并保存最小值

步骤三：让i再增加一个位置，这个时候滑动窗口肯定不满足条件了，那么继续从步骤一开始执行，寻找新的满足条件的滑动窗口，如此反复，直到j超出了字符串S范围。

如何判断滑动窗口包含了T的所有元素？

我们用一个数组need来表示当前滑动窗口中需要的各元素的数量，一开始滑动窗口为空，用T中各元素来初始化这个need，当滑动窗口扩展或者收缩的时候，去维护这个need数组，例如当滑动窗口包含某个元素，我们就让need中这个元素的数量减1，代表所需元素减少了1个；当滑动窗口移除某个元素，就让need中这个元素的数量加1。

记住一点：need始终记录着当前滑动窗口下，我们还需要的元素数量，我们在改变i,j时，需同步维护need。

值得注意的是，只要某个元素包含在滑动窗口中，我们就会在need中存储这个元素的数量，如果某个元素存储的是负数代表这个元素是多余的。比如当need等于{'A':-2,'C':1}时，表示当前滑动窗口中，我们有2个A是多余的，同时还需要1个C。这么做的目的就是为了步骤二中，排除不必要的元素，数量为负的就是不必要的元素，而数量为0表示刚刚好。

回到问题中来，那么如何判断滑动窗口包含了T的所有元素？ 结论就是当need中所有元素的数量都小于等于0时，表示当前滑动窗口不再需要任何元素。

如果每次判断滑动窗口是否包含了T的所有元素，都去遍历need看是否所有元素数量都小于等于0，这个会耗费O(k)O(k)的时间复杂度，k代表字典长度，最坏情况下，k可能等于len(S)。

其实这个是可以避免的，我们可以维护一个额外的变量needCnt来记录所需元素的总数量，当我们碰到一个所需元素c，不仅need[c]的数量减少1，同时needCnt也要减少1，这样我们通过needCnt就可以知道是否满足条件，而无需遍历字典了。

前面也提到过，need记录了遍历到的所有元素，而只有need[c]>0大于0时，代表c就是所需元素

代码：

class Solution {
    public String minWindow(String s, String t) {
        //A的ASCII码65 z的ASCII码122，所以数组是123
        int[] words = new int[123];
        for(int i=0;i<t.length();i++){
            words[t.charAt(i)]++; 
        }
        int left = 0;
        int right = 0;
        int size = 100001;
        int start = 0;
        int count = t.length();
        while(right<s.length()){
            char ch = s.charAt(right);
            if(words[ch]>0){
                count--;
            }
            words[ch]--;
            if(count==0){
                while(left<right&&words[s.charAt(left)]<0){
                    words[s.charAt(left)]++;
                    left++;
                }
                if(size > right-left+1){
                    size = right - left+1;
                    start = left;
                }
                words[s.charAt(left)]++;
                left++;
                count++;
            }
            right++;
        }
        return size==100001?"":s.substring(start,start+size);
    }
}
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

# 3.(medium)字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo" 输出：true 解释：s2 包含 s1 的排列之一 ("ba"). 示例 2：

输入：s1= "ab" s2 = "eidboaoo" 输出：false

提示：

1 <= s1.length, s2.length <= 104 s1 和 s2 仅包含小写字母

思路：

滑动窗口。使用两个int[123]数组need和window来分别记录需要的字符及其个数以及当前窗口中的字符及其个数。

使用count来记录满足了个数的字符的个数(比如aab，如果window中的a==2了，那么就满足了一个字符，count++)。

如果count等于了s1中字符的种类，即返回true。

具体的代码思路：

  1. 用need数组记录s1中字符及其个数，用一个map来统计不同字符的数量，用count记录已满足了的字符的数量
  2. 开始循环，右指针先移动，如果当前字符ch在need中的数量need[ch]仍然大于0，证明仍需要这个字符，所以将字符移入window：window[ch]++。如果移入以后，window中ch的数量与need中ch的数量相等了，证明这个字符已经找完
  3. 右指针继续移动，当移动到左右指针的区间长度(窗口大小right-left+1)大于了目标s1的长度时，就要移动左指针直到窗口大小继续等于s1的长度
  4. 移动左指针的过程中，如果判断到已满足了的字符的数量与map记录的字符种类数相等了，证明已经找到了，直接返回true，如果没有，继续左移指针判断
  5. 如果这个字符是need中需要的(数量>0)，就需要减去，并且，如果当前窗口这个字符的数量和need中字符数量相等，我们又要将它移出窗口，那么count--，最后将window[leftChar]--即可
  6. 如果右指针走到s2末尾还没找到，证明不存在，返回false

代码：

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int count = 0;
        int left = 0,right = 0;
        //z的ASCII码是122
        //need是记录需要的字符及其个数
        int[] need = new int[123];
        //window是记录当前窗口中的字符及其个数
        int[] window = new int[123];
        Map<Character,Integer> map = new HashMap<>();
        for(int i=0;i<s1.length();i++){
            need[s1.charAt(i)]++;
            map.put(s1.charAt(i),map.getOrDefault(s1.charAt(i),0)+1);
        }
        while(right<s2.length()){
            char ch = s2.charAt(right);
            right++;
            if(need[ch]>0){
                window[ch]++;
                if(window[ch] == need[ch]){
                    count++;
                }
            }
            while(right-left+1>s1.length()){
                if(count==map.size()){
                    return true;
                }
                char leftChar = s2.charAt(left);
                left++;
                if(need[leftChar]>0){
                    if(window[leftChar] == need[leftChar]){
                        count--;
                    }
                    window[leftChar]--;
                }
            }
        }
        return 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

# 4.(medium)找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。 示例 2:

输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

1 <= s.length, p.length <= 3 * 104 s 和 p 仅包含小写字母

思路：

思路和上题一样，只是判断到满足条件时，把当前left下标加入到结果List中即可

代码：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] need = new int[123];
        int[] window = new int[123];
        Set<Character> needCount = new HashSet<>();
        int count = 0;
        for(int i=0;i<p.length();i++){
            char ch = p.charAt(i);
            need[ch]++;
            needCount.add(ch);
        }
        int left = 0,right = 0;
        List<Integer> ans = new ArrayList<>();
        while(right<s.length()){
            char ch = s.charAt(right);
            right++;
            //如果字符需要 进入窗口
            if(need[ch]>0){
                window[ch]++;
                //如果进入后需要的数量也满足 count计数器++
                if(window[ch] == need[ch]){
                    count++;
                }
            }
            //当窗口长度大于p时，移动左指针缩小窗口到等于p.length()
            while(right-left+1>p.length()){
                if(count == needCount.size()){
                    ans.add(left);
                }
                char leftValue = s.charAt(left);
                left++;
                if(need[leftValue]>0){
                    if(window[leftValue] == need[leftValue]){
                        count--;
                    }
                    window[leftValue]--;
                }
            }
        }
        return ans;
    }
}
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

# 5.(medium)最长回文子串

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

示例 1：

输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 示例 2：

输入：s = "cbbd" 输出："bb"

思路1：双指针

一般我们都使用双指针去判断回文串，而要去找回文子串，我们只需要找以每个字符为最中心的字符的回文串即可。

既然要这样做，那么必然涉及到一个问题，如果回文串是偶数的情况下，它就应该有两个中心字符，且这两个中心字符相等，所以这里要特殊处理。

我们每次去寻找的时候，寻找两次，第一次假设为奇数，左右指针都是i；第二次假设为偶数左指针i，右指针i+1即可

代码：

class Solution {
    public String longestPalindrome(String s) {
        String res = "";
        for(int i=0;i<s.length();i++){
            //回文串为奇数的情况
            //此时如果是回文串，i就是中间的那个字符
            String one = getPalindrome(s,i,i);
            //为偶数的情况
            //此时如果是回文串，刚好的中间的两个
            String two = getPalindrome(s,i,i+1);
            res = one.length()>res.length()?one:res;
            res = two.length()>res.length()?two:res;
        }
        return res;
    }

    public String getPalindrome(String s,int left,int right){
        //如果满足回文 则左指针左移 右指针右移
        while(left>=0&&right<s.length() && s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
        return s.substring(left+1,right);
    }
}
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
在 GitHub 上编辑此页 (opens new window)
#字符串
最后更新: 2022/10/04, 16:10:00
数组
动态规划

← 动态规划→

Theme by Vdoing | Copyright © 2022-2024 zdk | notes
湘ICP备2022001117号-1
川公网安备 51142102511562号
提供加速服务