Skip to content

Commit 298eb25

Browse files
itchargeitcharge
committed
更新题解列表
1 parent 5317114 commit 298eb25

7 files changed

Lines changed: 310 additions & 94 deletions

‎Solutions/0567. 字符串的排列.md‎

Lines changed: 42 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -9,26 +9,50 @@
99

1010
## 题目大意
1111

12-
给定两个字符串 `s1` 和 `s2` 。
12+
**描述**：给定两个字符串 $s1$ 和 $s2$ 。
1313

14-
要求：判断 `s2` 是否包含 `s1` 的排列。如果包含，返回 `True`；否则，返回 `False`。
14+
**要求**：判断 $s2$ 是否包含 $s1$ 的排列。如果包含，返回 $True$；否则，返回 $False$。
15+
16+
**说明**：
17+
18+
- $1 \le s1.length, s2.length \le 10^4$。
19+
- $s1$ 和 $s2$ 仅包含小写字母。
20+
21+
**示例**：
22+
23+
- 示例 1：
24+
25+
```python
26+
输入：s1 = "ab" s2 = "eidbaooo"
27+
输出：true
28+
解释：s2 包含 s1 的排列之一 ("ba").
29+
```
30+
31+
- 示例 2：
32+
33+
```python
34+
输入：s1= "ab" s2 = "eidboaoo"
35+
输出：False
36+
```
1537

1638
## 解题思路
1739

18-
题目要求判断 `s2` 是否包含 `s1` 的排列，则 `s2` 的子串长度等于 `s1` 的长度。我们可以维护一个长度为字符串 `s1` 长度的固定长度的滑动窗口。
40+
### 思路 1：滑动窗口
1941

20-
先统计出字符串 `s1` 中各个字符的数量，我们用 `s1_count` 来表示。这个过程可以用字典、数组来实现，也可以直接用 `collections.Counter()` 实现。再统计 `s2` 对应窗口内的字符数量 `window_count`，然后不断向右滑动，然后进行比较。如果对应字符数量相同，则返回 `True`，否则继续滑动。直到末尾时，返回 `False`。整个解题步骤具体如下：
42+
题目要求判断 $s2$ 是否包含 $s1$ 的排列，则 $s2$ 的子串长度等于 $s1$ 的长度。我们可以维护一个长度为字符串 $s1$ 长度的固定长度的滑动窗口。
2143

22-
1. `s1_count` 用来统计 `s1` 中各个字符数量。`window_count` 用来维护窗口中 `s2` 对应子串的各个字符数量。`window_size` 表示固定窗口的长度，值为 `len(s1)`。
23-
2. 先统计出 `s1` 中各个字符数量。
24-
3. `left` 、`right` 都指向序列的第一个元素，即：`left = 0`，`right = 0`。
25-
4. 向右移动 `right`，先将 `len(s1)` 个元素填入窗口中。
26-
5. 当窗口元素个数为 `window_size` 时，即：`right - left + 1 >= window_size` 时，判断窗口内各个字符数量 `window_count` 是否等于 `s1 ` 中各个字符数量 `s1_count`。
27-
1. 如果等于，直接返回 `True`。
28-
2. 如果不等于，则向右移动 `left`，从而缩小窗口长度，即 `left += 1`，使得窗口大小始终保持为 `window_size`。
29-
6. 重复 4 ~ 5 步，直到 `right` 到达数组末尾。返回 `False`。
44+
先统计出字符串 $s1$ 中各个字符的数量，我们用 $s1\underline{}count$ 来表示。这个过程可以用字典、数组来实现，也可以直接用 `collections.Counter()` 实现。再统计 $s2$ 对应窗口内的字符数量 $window\underline{}count$，然后不断向右滑动，然后进行比较。如果对应字符数量相同，则返回 $True$，否则继续滑动。直到末尾时，返回 $False$。整个解题步骤具体如下：
3045

31-
## 代码
46+
1. $s1\underline{}count$ 用来统计 $s1$ 中各个字符数量。$window\underline{}count$ 用来维护窗口中 $s2$ 对应子串的各个字符数量。$window\underline{}size$ 表示固定窗口的长度，值为 $len(s1)$。
47+
2. 先统计出 $s1$ 中各个字符数量。
48+
3. $left$ 、$right$ 都指向序列的第一个元素，即：`left = 0`，`right = 0`。
49+
4. 向右移动 $right$，先将 $len(s1)$ 个元素填入窗口中。
50+
5. 当窗口元素个数为 $window\underline{}size$ 时，即：$right - left + 1 \ge window\underline{}size$ 时，判断窗口内各个字符数量 $window\underline{}count$ 是否等于 $s1 $ 中各个字符数量 $s1\underline{}count$。
51+
1. 如果等于，直接返回 $True$。
52+
2. 如果不等于，则向右移动 $left$，从而缩小窗口长度，即 `left += 1`，使得窗口大小始终保持为 $window\underline{}size$。
53+
6. 重复 $4 \sim 5$ 步，直到 $right$ 到达数组末尾。返回 $False$。
54+
55+
### 思路 1：代码
3256

3357
```python
3458
import collections
@@ -54,3 +78,8 @@ class Solution:
5478
return False
5579
```
5680

81+
### 思路 1：复杂度分析
82+
83+
- **时间复杂度**：$O(n + m + |\sum|)$，其中 $n$、$m$ 分别是字符串 $s1$、$s2$ 的长度，$\sum$ 是字符集，本题中 $|\sum| = 26$。
84+
- **空间复杂度**：$O(|\sum|)$。
85+

‎Solutions/0844. 比较含退格的字符串.md‎

Lines changed: 58 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -9,46 +9,47 @@
99

1010
## 题目大意
1111

12-
给定 `s` 和 `t` 两个字符串。字符串中的 `#` 代表退格字符。
12+
**描述**：给定 $s$ 和 $t$ 两个字符串。字符串中的 `#` 代表退格字符。
1313

14-
要求：当它们分别被输入到空白的文本编辑器后，判断二者是否相等。如果相等，返回 `True`；否则，返回 `False`。
14+
**要求**：当它们分别被输入到空白的文本编辑器后，判断二者是否相等。如果相等，返回 $True$；否则，返回 $False$。
1515

16-
注意：如果对空文本输入退格字符，文本继续为空。
16+
**说明**：
17+
18+
- 如果对空文本输入退格字符，文本继续为空。
19+
- $1 \le s.length, t.length \le 200$。
20+
- $s$ 和 $t$ 只含有小写字母以及字符 `#`。
21+
22+
**示例**：
23+
24+
- 示例 1：
25+
26+
```python
27+
输入：s = "ab#c", t = "ad#c"
28+
输出：true
29+
解释：s 和 t 都会变成 "ac"。
30+
```
31+
32+
- 示例 2：
33+
34+
```python
35+
输入：s = "ab##", t = "c#d#"
36+
输出：true
37+
解释：s 和 t 都会变成 ""。
38+
```
1739

1840
## 解题思路
1941

2042
这道题的第一个思路是用栈，第二个思路是使用分离双指针。
2143

22-
思路一：栈。
44+
### 思路 1：栈
2345

2446
- 定义一个构建方法，用来将含有退格字符串构建为删除退格的字符串。构建方法如下。
2547
- 使用一个栈存放删除退格的字符串。
2648
- 遍历字符串，如果遇到的字符不是 `#`，则将其插入到栈中。
2749
- 如果遇到的字符是 `#`，且当前栈不为空，则将当前栈顶元素弹出。
28-
- 分别使用构建方法处理字符串 `s` 和 `t`，如果处理完的字符串 `s` 和 `t` 相等，则返回 `True`，否则返回 `False`。
29-
30-
思路二：分离双指针。
50+
- 分别使用构建方法处理字符串 $s$ 和 $t$，如果处理完的字符串 $s$ 和 $t$ 相等，则返回 $True$，否则返回 $False$。
3151

32-
由于 `#` 会消除左侧字符，而不会影响右侧字符，所以我们选择从字符串尾端遍历 `s`、`t` 字符串。具体做法如下：
33-
34-
- 使用分离双指针 `left_1`、`left_2`。`left_1` 指向字符串 `s` 末尾，`left_2` 指向字符串 `t` 末尾。使用 `sign_1`、`sign_2` 标记字符串 `s`、`t` 中当前退格字符个数。
35-
- 从后到前遍历字符串 `s`、`t`。
36-
- 先来循环处理字符串 `s` 尾端 `#` 的影响，具体如下：
37-
- 如果当前字符是 `#`，则更新 `s` 当前退格字符个数，即 `sign_1 += 1`。同时将 `left_1` 左移。
38-
- 如果 `s` 当前退格字符个数大于 `0`，则退格数减一，即 `sign_1 -= 1`。同时将 `left_1` 左移。
39-
- 如果 `s` 当前为普通字符，则跳出循环。
40-
- 同理再来处理字符串 `t` 尾端 `#` 的影响，具体如下：
41-
- 如果当前字符是 `#`，则更新 `t` 当前退格字符个数，即 `sign_2 += 1`。同时将 `left_2` 左移。
42-
- 如果 `t` 当前退格字符个数大于 `0`，则退格数减一，即 `sign_2 -= 1`。同时将 `left_2` 左移。
43-
- 如果 `t` 当前为普通字符，则跳出循环。
44-
- 处理完，如果两个字符串为空，则说明匹配，直接返回 `True`。
45-
- 再先排除长度不匹配的情况，直接返回 `False`。
46-
- 最后判断 `s[left_1]` 是否等于 `s[left_2]`。不等于则直接返回 `False`，等于则令 `left_1`、`left_2` 左移，继续遍历。
47-
- 遍历完没有出现不匹配的情况，则返回 `True`。
48-
49-
## 代码
50-
51-
- 思路一：
52+
### 思路 1：代码
5253

5354
```python
5455
class Solution:
@@ -65,7 +66,31 @@ class Solution:
6566
return self.build(s) == self.build(t)
6667
```
6768

68-
- 思路二：
69+
### 思路 1：复杂度分析
70+
71+
- **时间复杂度**：$O(n + m)$，其中 $n$ 和 $m$ 分别为字符串 $s$、$t$ 的长度。
72+
- **空间复杂度**：$O(n + m)$。
73+
74+
### 思路 2：分离双指针
75+
76+
由于 `#` 会消除左侧字符，而不会影响右侧字符，所以我们选择从字符串尾端遍历 $s$、$t$ 字符串。具体做法如下：
77+
78+
- 使用分离双指针 $left\underline{}1$、$left\underline{}2$。$left\underline{}1$ 指向字符串 $s$ 末尾，$left\underline{}2$ 指向字符串 $t$ 末尾。使用 $sign\underline{}1$、$sign\underline{}2$ 标记字符串 $s$、$t$ 中当前退格字符个数。
79+
- 从后到前遍历字符串 $s$、$t$。
80+
- 先来循环处理字符串 $s$ 尾端 `#` 的影响，具体如下：
81+
- 如果当前字符是 `#`，则更新 $s$ 当前退格字符个数，即 `sign_1 += 1`。同时将 $left\underline{}1$ 左移。
82+
- 如果 $s$ 当前退格字符个数大于 $0$，则退格数减一，即 `sign_1 -= 1`。同时将 $left\underline{}1$ 左移。
83+
- 如果 $s$ 当前为普通字符，则跳出循环。
84+
- 同理再来处理字符串 $t$ 尾端 `#` 的影响，具体如下：
85+
- 如果当前字符是 `#`，则更新 $t$ 当前退格字符个数，即 `sign_2 += 1`。同时将 $left\underline{}2$ 左移。
86+
- 如果 $t$ 当前退格字符个数大于 $0$，则退格数减一，即 `sign_2 -= 1`。同时将 $left\underline{}2$ 左移。
87+
- 如果 $t$ 当前为普通字符，则跳出循环。
88+
- 处理完，如果两个字符串为空，则说明匹配，直接返回 $True$。
89+
- 再先排除长度不匹配的情况，直接返回 $False$。
90+
- 最后判断 $s[left\underline{}1]$ 是否等于 $s[left\underline{}2]$。不等于则直接返回 $False$，等于则令 $left\underline{}1$、$left\underline{}2$ 左移，继续遍历。
91+
- 遍历完没有出现不匹配的情况，则返回 $True$。
92+
93+
### 思路 2：代码
6994

7095
```python
7196
class Solution:
@@ -108,3 +133,8 @@ class Solution:
108133
return True
109134
```
110135

136+
### 思路 2：复杂度分析
137+
138+
- **时间复杂度**：$O(n + m)$，其中 $n$ 和 $m$ 分别为字符串 $s$、$t$ 的长度。
139+
- **空间复杂度**：$O(1)$。
140+

‎Solutions/1052. 爱生气的书店老板.md‎

Lines changed: 44 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -9,28 +9,55 @@
99

1010
## 题目大意
1111

12-
书店老板有一家店打算试营业 `len(customers)` 分钟。每一分钟都有一些顾客 `customers[i]` 会进入书店，这些顾客会在这一分钟结束后离开。
12+
**描述**：书店老板有一家店打算试营业 $len(customers)$ 分钟。每一分钟都有一些顾客 $customers[i]$ 会进入书店，这些顾客会在这一分钟结束后离开。
1313

14-
在某些时候，书店老板会生气。如果书店老板在第 `i` 分钟生气，则 `grumpy[i] = 1`，如果第 `i` 分钟不生气，则 `grumpy[i] = 0`。当书店老板生气时，这一分钟的顾客会不满意。当书店老板不生气时，这一分钟的顾客是满意的。
14+
在某些时候，书店老板会生气。如果书店老板在第 $i$ 分钟生气，则 `grumpy[i] = 1`，如果第 $i$ 分钟不生气，则 `grumpy[i] = 0`。当书店老板生气时，这一分钟的顾客会不满意。当书店老板不生气时，这一分钟的顾客是满意的。
1515

16-
假设老板知道一个秘密技巧，能保证自己连续 `minutes` 分钟不生气，但只能使用一次。
16+
假设老板知道一个秘密技巧，能保证自己连续 $minutes$ 分钟不生气，但只能使用一次。
1717

18-
现在给定代表每分钟进入书店的顾客数量的数组 `customes`，和代表老板生气状态的数组 `grumpy`，以及老板保证连续不生气的分钟数 `minutes`。
18+
现在给定代表每分钟进入书店的顾客数量的数组 $customes$，和代表老板生气状态的数组 $grumpy$，以及老板保证连续不生气的分钟数 $minutes$。
1919

20-
要求：计算出试营业下来，最多有多少客户能够感到满意。
20+
**要求**：计算出试营业下来，最多有多少客户能够感到满意。
21+
22+
**说明**：
23+
24+
- $n == customers.length == grumpy.length$。
25+
- $1 \le minutes \le n \le 2 \times 10^4$。
26+
- $0 \le customers[i] \le 1000$。
27+
- $grumpy[i] == 0 \text{ or } 1$。
28+
29+
**示例**：
30+
31+
- 示例 1：
32+
33+
```python
34+
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
35+
输出：16
36+
解释：书店老板在最后 3 分钟保持冷静。
37+
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
38+
```
39+
40+
- 示例 2：
41+
42+
```python
43+
输入：customers = [1], grumpy = [0], minutes = 1
44+
输出：1
45+
```
2146

2247
## 解题思路
2348

24-
固定长度的滑动窗口题目。我们可以维护一个窗口大小为 `minutes` 的滑动窗口。使用 `window_count` 记录当前窗口内生气的顾客人数。然后滑动求出窗口中最大顾客数，然后累加上老板未生气时的顾客数，就是答案。具体做法如下：
49+
### 思路 1：滑动窗口
2550

26-
1. `ans` 用来维护答案数目。`window_count` 用来维护窗口中生气的顾客人数。
27-
2. `left` 、`right` 都指向序列的第一个元素，即：`left = 0`，`right = 0`。
28-
3. 如果书店老板生气，则将这一分钟的顾客数量加入到 `window_count` 中，然后向右移动 `right`。
29-
4. 当窗口元素个数大于 `minutes` 时，即：`right - left + 1 > count` 时，如果最左侧边界老板处于生气状态，则向右移动 `left`，从而缩小窗口长度，即 `left += 1`，使得窗口大小始终保持为小于 `minutes`。
30-
5. 重复 3 ~ 4 步，直到 `right` 到达数组末尾。
51+
固定长度的滑动窗口题目。我们可以维护一个窗口大小为 $minutes$ 的滑动窗口。使用 $window_count$ 记录当前窗口内生气的顾客人数。然后滑动求出窗口中最大顾客数，然后累加上老板未生气时的顾客数，就是答案。具体做法如下：
52+
53+
1. $ans$ 用来维护答案数目。$window\underline{}count$ 用来维护窗口中生气的顾客人数。
54+
2. $left$ 、$right$ 都指向序列的第一个元素，即：`left = 0`，`right = 0`。
55+
3. 如果书店老板生气，则将这一分钟的顾客数量加入到 $window\underline{}count$ 中，然后向右移动 $right$。
56+
4. 当窗口元素个数大于 $minutes$ 时，即：$right - left + 1 > count$ 时，如果最左侧边界老板处于生气状态，则向右移动 $left$，从而缩小窗口长度，即 `left += 1`，使得窗口大小始终保持为小于 $minutes$。
57+
5. 重复 $3 \sim 4$ 步，直到 $right$ 到达数组末尾。
3158
6. 然后累加上老板未生气时的顾客数，最后输出答案。
3259

33-
## 代码
60+
### 思路 1：代码
3461

3562
```python
3663
class Solution:
@@ -58,3 +85,8 @@ class Solution:
5885
return ans
5986
```
6087

88+
### 思路 1：复杂度分析
89+
90+
- **时间复杂度**：$O(n)$，其中 $n$ 为数组 $coustomer$、$grumpy$ 的长度。
91+
- **空间复杂度**：$O(1)$。
92+

‎Solutions/1100. 长度为 K 的无重复字符子串.md‎

Lines changed: 36 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -9,12 +9,40 @@
99

1010
## 题目大意
1111

12-
给定一个字符串 `s`。
12+
**描述**：给定一个字符串 `s`。
1313

14-
要求：找出所有长度为 `k` 且不含重复字符的子串，返回全部满足要求的子串的数目。
14+
**要求**：找出所有长度为 `k` 且不含重复字符的子串，返回全部满足要求的子串的数目。
15+
16+
**说明**：
17+
18+
- $1 \le s.length \le 10^4$。
19+
- $s$ 中的所有字符均为小写英文字母。
20+
- $1 <= k <= 10^4$。
21+
22+
**示例**：
23+
24+
- 示例 1：
25+
26+
```python
27+
输入：s = "havefunonleetcode", k = 5
28+
输出：6
29+
解释：
30+
这里有 6 个满足题意的子串，分别是：'havef','avefu','vefun','efuno','etcod','tcode'。
31+
```
32+
33+
- 示例 2：
34+
35+
```python
36+
输入：s = "home", K = 5
37+
输出：0
38+
解释：
39+
注意：k 可能会大于 s 的长度。在这种情况下，就无法找到任何长度为 k 的子串。
40+
```
1541

1642
## 解题思路
1743

44+
### 思路 1：滑动窗口
45+
1846
固定长度滑动窗口的题目。维护一个长度为 `k` 的滑动窗口。用 `window_count` 来表示窗口内所有字符个数。可以用字典、数组来实现，也可以直接用 `collections.Counter()` 实现。然后不断向右滑动，然后进行比较。如果窗口内字符无重复，则答案数目 + 1。然后继续滑动。直到末尾时。整个解题步骤具体如下：
1947

2048
1. `window_count` 用来维护窗口中 `2` 对应子串的各个字符数量。
@@ -25,7 +53,7 @@
2553
2. 如果不等于，则向右移动 `left`，从而缩小窗口长度，即 `left += 1`，使得窗口大小始终保持为 `k`。
2654
5. 重复 3 ~ 4 步，直到 `right` 到达数组末尾。返回答案。
2755

28-
## 代码
56+
### 思路 1：代码
2957

3058
```python
3159
import collections
@@ -52,3 +80,8 @@ class Solution:
5280
return ans
5381
```
5482

83+
### 思路 1：复杂度分析
84+
85+
- **时间复杂度**：$O(n)$，其中 $n$ 为字符串 $s$ 的长度。
86+
- **空间复杂度**：$O(|\sum|)$，其中 $\sum$ 是字符集。
87+

0 commit comments

Comments
 (0)