字符串

# 剑指 Offer 48. 最长不含重复字符的子字符串

题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

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

1
2
3

示例 2:

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

1
2
3

示例 3:

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

1
2
3
4

提示:

s.length <= 40000s.length<=40000

**思路**

标签：滑动窗口
整体思路：
- 暴力解法时间复杂度较高，会达到 O(n^2), 故而采取滑动窗口的方法降低时间复杂度
复杂度：
- 时间复杂度：O(n)。

算法流程

定义一个 map 数据结构存储 (k, v)，其中 key 值为字符，value 值为字符位置 +1，加 1 表示从字符位置后一个才开始不重复
我们定义不重复子串的开始位置为 start，结束位置为 end
随着 end 不断遍历向后，会遇到与 [start, end] 区间内字符相同的情况，此时将字符作为 key 值，获取其 value 值，并更新 start，此时 [start, end] 区间内不存在重复字符
无论是否更新 start，都会更新其 map 数据结构和结果 ans。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        
        Map<Character, Integer> map = new HashMap<>();
        
        // 不重复子串的开始位置为 start，结束位置为 end
        for (int end = 0, start = 0; end < n; end++) {
            char alpha = s.charAt(end);
            
            if (map.containsKey(alpha)) {
                // 随着 end 不断遍历向后，会遇到与 [start, end] 区间内字符相同的情况，
                // 此时将字符作为 key 值，获取其 value 值，并更新 start，此时 [start, end] 区间内不存在重复字符
                start = Math.max(map.get(alpha), start);
            }
            map.put(s.charAt(end), end + 1);
            
            // value 值为字符位置 +1，加 1 表示从字符位置后一个才开始不重复
            ans = Math.max(ans, end - start + 1);
            
        }
        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

或：

动态规划 + 哈希表

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();

        int res = 0, currentLongest = 0, len = s.length();

        for(int left = 0, right = 0; right < len; right++) { 
            left = dic.containsKey(s.charAt(right)) ? dic.get(s.charAt(right)) : -1; // 如果不在 dic 里，j 需要加 1 才是真正长度
            dic.put(s.charAt(right), right); // 更新哈希表
            int noRepeatLength = right - left; 
            currentLongest = currentLongest < noRepeatLength ? currentLongest + 1 : noRepeatLength; // dp[j - 1] -> dp[j]
            res = Math.max(res, currentLongest); // max(dp[j - 1], dp[j])
        }
        return res;
    }
}

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

# 剑指 Offer 58 - I. 翻转单词顺序

题目描述 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串 "I am a student. "，则输出 "student. a am I"。

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

1
2

示例 2：

输入: "  hello world!  "
输出: "world! hello"

1
2

解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good   example"
输出: "example good a"

1
2

解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路

标签：双指针
整体思路：先将开头和结尾处多余的空格去掉，从后向前遍历，通过前后指针锁定单词，跳过中间空格，最终将整个句子中的单词反转
时间复杂度：O(n)，空间复杂度：O(n)

算法流程

首先将原始字符串去掉开头和结尾的空格得到 tmp，便于之后直接从单词处理开始
初始化单词起始位置 start 和单词结束位置 end 指针，位置在字符串结尾处
初始化结果字符串 res 为空字符串
当 start >= 0 时，说明字符串未遍历结束，作为循环条件
在 tmp[start] 位置如果不为空格，说明还没有获取到完整的单词，则 start--
获取到完整单词之后，截取 [start+1, end+1] 这一段字符串加入结果字符串中，反转单词
在 tmp[start] 位置如果为空格，说明还没有到下一个单词的结尾位置，则 start--
到单词结尾位置之后，end = start，往复进行上述流程，将单词全部反转
将结果字符串 res 去掉开头和结尾多余的空格

class Solution {
    public String reverseWords(String s) {
        String tmp = s.trim();
        int start = tmp.length() - 1;
        int end = tmp.length() - 1;
        String res = "";
        while(start >= 0) {
            while(start >= 0 && tmp.charAt(start) != ' ') {
                start--;
            }
            res += tmp.substring(start + 1, end + 1) + " ";
            // get rid of empty spaces 
            while(start >= 0 && tmp.charAt(start) == ' ') {
                start--;
            }
            end = start;
        }
        return res.trim();
    }
}

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

或：

用 StringBuilder

class Solution {
    public String reverseWords(String s) {
        if(s.length() == 0) return "";

        String[] tmp = s.trim().split(" ");
        StringBuilder res = new StringBuilder();

        for(int i = tmp.length - 1;i >= 0; i--){
            if(tmp[i].equals("")) 
                continue;
                
            res.append(tmp[i]);
            res.append(" ");
        }
        return res.toString().trim();
    }
}

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

# 剑指 Offer 58 - II. 左旋转字符串

题目描述 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：

输入: s = "abcdefg", k = 2
输出: "cdefgab"

1
2

示例 2：

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

1
2

限制：

1 <= k < s.length <= 10000

思路

标签：字符串遍历
整体思路：在原字符串处从需要反转的位置 n 开始向后遍历，并保存到结果字符串中，然后再从原字符串的初始位置遍历到位置 n，继续添加到结果字符串
时间复杂度：O(n)，空间复杂度：O(n)

算法流程

初始化结果字符串 res = ""，获取字符串长度 len
从下标 n 开始遍历，遍历到字符串 s 结尾，将区间 [n, len] 的字符添加到 res 中
从下标 0 开始遍历，遍历到下标 n 位置，将区间 [0, n] 的字符添加到 res 中

class Solution {
    public String reverseLeftWords(String s, int n) {
        String res = "";
        int len = s.length();
        for(int i = n; i < len; i++) {
            res += s.charAt(i);
        }
        for(int i = 0; i < n; i++) {
            res += s.charAt(i);
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

或：

更简单的

class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n, s.length()).concat(s.substring(0, n));
    }
}

1
2
3
4
5

# 剑指 Offer 67. 把字符串转换成整数

题目描述

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: "42"
输出: 42

1
2

示例 2:

输入: "   -42"
输出: -42

解释：第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

1
2
3
4
5

示例 3:

输入: "4193 with words"
输出: 4193

解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

1
2
3
4

示例 4:

输入: "4193 with words"
输出: 4193

解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

1
2
3
4

示例 5:

输入: "-91283472332"
输出: -2147483648

解释：数字 "-91283472332" 超过 32 位有符号整数范围。
     因此返回 INT_MIN (−231) 。

1
2
3
4
5

**思路**

标签：处理数字越界
整体思路：
- 前端空格
- “+”，“-”正负号
- 首个字符为非数字
- 数字字符处理
复杂度：
- 时间复杂度：O(n)O(n) ：其中 n 为字符串长度，线性遍历字符串占用 O(n)O(n) 时间
- 空间复杂度：O(n)O(n) ：删除首尾空格后需建立新字符串，最差情况下占用 O(n)O(n) 额外空间。

算法流程

删除首位空格
声明一个变量保存符号位
首位字符非数字直接返回
若为数字字符，从左向右遍历字符集，若当前数字为 x，数字结果为 res，则遍历中 res 结果为 res = res * 10 + x
获得下一次遍历结果前判断是否越界，如果超过 2147483647，直接返回
返回结果

class Solution {
    public int strToInt(String str) {
        char[] c = str.trim().toCharArray();
        if(c.length == 0) return 0;
        int res = 0, boundry = Integer.MAX_VALUE / 10;
        
        // 判断 起始位 和 正负性
        int start = 1, sign = 1;
        if(c[0] == '-') sign = -1;
        else if(c[0] != '+') start = 0;
        
        for(int i = start; i < c.length; i++) {
            
            if(c[i] < '0' || c[i] > '9') break;
            
            if(res > boundry || res == boundry && c[i] > '7') return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            
            res = res * 10 + (c[i] - '0');
        }
        return sign * res;
    }
}

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

# 实现 strStr()

实现 strStr() (opens new window) 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() (opens new window) 以及 Java 的 indexOf() (opens new window) 定义相符。

示例 1：

**输入：**haystack = "hello", needle = "ll" **输出：**2

示例 2：

**输入：**haystack = "aaaaa", needle = "bba" 输出：-1

示例 3：

**输入：**haystack = "", needle = "" **输出：**0

提示：

0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 仅由小写英文字符组成

思路：

一行代码搞定

    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

1
2
3

如果要这样写就没意思了，算法题能自己写的还是要自己写，尽量少用官方的api

逐个判断

一般字符串匹配的时候，最简单的一种方式，就是子串从头开始和主串匹配。

如果匹配失败，子串再次从头开始，而主串从上次匹配的下一个字符开始，代码如下

    public int strStr(String haystack, String needle) {
        if (needle.length() == 0)
            return 0;
        int i = 0;
        int j = 0;
        while (i < haystack.length() && j < needle.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                
                i = i - j + 1;
                j = 0;
            }
            if (j == needle.length())
                return i - j;
        }
        return -1;
    }

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

效率很差

还一种方式就是不断截取主串然后在比较，看下代码

    public int strStr(String haystack, String needle) {
        int length = needle.length();
        int total = haystack.length() - length + 1;
        for (int start = 0; start < total; ++start) {
            if (haystack.substring(start, start + length).equals(needle)) {
                return start;
            }
        }
        return -1;
    }

1
2
3
4
5
6
7
8
9
10

KMP算法

其实这题是一道典型的KMP算法题，KMP算法的本质就是减少重复计算，我们举个例子，比如下面的图中，在最后一步比较失败的时候，然后子串又要从头开始，主串要从上一次比较的下一个字符开始，实际上前面的一些比较成功的数据我们是可以利用的。如下图所示，如果匹配失败的话，下一步主串还从失败的地方比较就可以了。

来看下代码

public int strStr(String haystack, String needle) {
    if (needle.length() == 0)
        return 0;
    int i = 0;
    int j = 0;
    /**
        数组next表示pattern指定的下标前具有相同的字符串数量
            比如ABCABA，数组next[0]是-1，这个是固定的，因为第一个A前面是没有字符的，
            next[1]是0，因为B的前面就一个A，没有重复的，所以是0,
            同理next[2]也是,
            next[3]也是0,
            而next[4]是1，
            因为next[4]所指向的是第二个B，第二个B前面有一个A和第一个A相同，所以是1,
            next[5]是2，因为next[5]所指向的是最后一个Ａ，因为前面的Ａ对比成功，并且Ｂ也对比成功，所以是２，
            也就是ＡＢ两个字符串匹配成功,
    	再举个例子，比如WABCABA，
    		数组除了第一个为-1，其他的都是为0，因为只有第一个匹配成功之后才能匹配后面的，
    		虽然后面的AB和前面的AB匹配成功，但是后面AB的前面是C和前面AB的前面一个W不匹配，所以后面的匹配都是0.
    		要记住只有指定字符前面的字符和第一个字符匹配成功的时候才能往后匹配，否则后面的永远都是先和第一个匹配。
            */
    int[] next = new int[needle.length()];
    getNext(needle, next);
    while (i < haystack.length() && j < needle.length()) {
        /**
        这里j等于-1的时候也只有在下面next数组赋值的时候才会出现，并且只有在数组next[0]的时候才会等于-1，
        其他时候是没有的，这一点要谨记，待会下面求next数组的时候就会用到。
        这里可以这样来理解，如果j不等于-1，并且下标i和j所指向的字符相等，那么i和j分别往后移一位继续比较，这个很好理解，
        那么如果j==-1的时候，就表示前面没有匹配成功的，同时i往后移一位，j置为0（j==-1的时候，j++为0），再从0开始比较。
        */
        if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
            i++;
            j++;
        } else {
        /**
        i = i - j + 1;
        j = 0;
        返回到指定的位置，不是返回到匹配失败的下一个位置，这里都好理解，重点是求数组next。
        这里只要 j 等于0，在next[j]赋值的之后，j就会等于-1；因为 next[0] 等于 -1
                 */
            j = next[j]; // j 回到指定位置
        }
        if (j == needle.length())
            return i - j;
    }
    return -1;
}

private void getNext(String p, int next[]) {
    int len = p.length();
    int i = 0;
    int j = -1;
    next[0] = -1;//这个默认的，
    // 匹配的时候是当前字符的前一个和前面的匹配，所以最后一个是不参与匹配的，可以看strStr方法的注释，
    while (i < len - 1) {
        if (j == -1 || p.charAt(i) == p.charAt(j)) {
            /**
            如果j不等于-1，指定的字符相等，那么i和j要往后移一位，这点很好理解，
            如果j为-1的时候，i往后移移位，j置为0
            */
            i++;
            j++;
            // 重新开始匹配。next[i]是匹配成功的数量
            next[i] = j;
        } else
            /**
            关键是这里不好理解，为什么匹配失败要让 j 等于 next[j]，
            要记住这里的next[j]是指匹配成功的数量，有可能为0，也有可能是其他数.
            比如字符串            A   B	 C   A   B   X   Y   A   B   C   A   B   A   T   D  
            对应的next数组为{-1	0	0	0	1	2	0	0	1	2	3	4	5	1	0	0	}
            										这里，j = next[2] = 0		  |
            										之后  j = next[0] = -1,      |
            										     j = -1,                 |
            										     所以 next[i] = j++ = 0   |
            																	这里，j = next[5] = 2
            																		 j = next[2] = 0
            																		 next[12] == next[0]
            																		 j = 1
             */
            j = next[j];
    }
}

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

代码量不是很多，但理解起来稍微有点难度，上面都有详细的注释，关注我，以后有时间在专门写一篇关于KMP算法的文章

我自己的：

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.equals(""))
            return 0;
        else if (haystack.equals(needle))
            return 0; 
        char[] charArray1 = haystack.toCharArray();
        char[] charArray2 = needle.toCharArray();
        int length1 = charArray1.length;
        int length2 = charArray2.length;

        if (haystack != "" && length1 < length2)
            return -1;

        int tmp = 0; 
        for (int i = 0; i < length1; i++) {
            if (charArray1[i] == charArray2[tmp]) {
                if (tmp == 0 && length1 - i < length2)
                    break;
                if (tmp == 0 && charArray1[i + length2 - 1] != charArray2[length2 - 1])
                    continue;
                tmp++;
                if (tmp == length2)
                    return i - tmp + 1;
            }
            else if (tmp != 0) {
                i = i - tmp; 
                tmp = 0;
            }
        }

        return -1;
    }
}

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

上次更新: 2022/01/13, 15:19:16

← 数组栈与列堆→