更新题解列表

itcharge · itcharge · commit 67d6e535d1f4 · 2024-01-04T13:38:22.000+08:00
diff --git a/Solutions/0438. 找到字符串中所有字母异位词.md b/Solutions/0438. 找到字符串中所有字母异位词.md
@@ -9,26 +9,55 @@
 
 ## 题目大意
 
-给定两个字符串 `s` 和 `p`。
+**描述**：给定两个字符串 $s$ 和 $p$。
 
-要求：找到 `s` 中所有 `p` 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
+**要求**：找到 $s$ 中所有 $p$ 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 
-- 异位词：指由相同字母重排列形成的字符串（包括相同的字符串）。
+**说明**：
+
+- **异位词**：指由相同字母重排列形成的字符串（包括相同的字符串）。
+- $1 <= s.length, p.length <= 3 * 10^4$。
+- $s$ 和 $p$ 仅包含小写字母。
+
+**示例**：
+
+- 示例 1：
+
+```python
+输入: s = "cbaebabacd", p = "abc"
+输出: [0,6]
+解释:
+起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
+起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
+```
+
+- 示例 2：
+
+```python
+输入: s = "abab", p = "ab"
+输出: [0,1,2]
+解释:
+起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
+起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
+起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
+```
 
 ## 解题思路
 
-维护一个固定长度为 `len(p)` 的滑动窗口。于是问题的难点变为了如何判断 `s` 的子串和 `p` 是异位词。可以使用两个字典来分别存储 `s` 的子串中各个字符个数和 `p` 中各个字符个数。如果两个字典对应的键值全相等，则说明 `s` 的子串和 `p` 是异位词。但是这样每一次比较的操作时间复杂度是 $O(n)$，我们可以通过在滑动数组中逐字符比较的方式来减少两个字典之间相互比较的复杂度，并用 `valid` 记录经过验证的字符个数。整个算法步骤如下：
+### 思路 1：滑动窗口
 
-- 使用哈希表 `need` 记录 `p` 中各个字符出现次数。使用字典 `window` 记录 `s` 的子串中各个字符出现的次数。使用数组 `res` 记录答案。使用 `valid` 记录 `s` 的子串中经过验证的字符个数。使用 `window_size` 表示窗口大小，值为 `len(p)`。使用两个指针 `left`、`right`。分别指向滑动窗口的左右边界。
-- 一开始，`left`、`right` 都指向 `0`。
-- 如果 `s[right]` 出现在 `need` 中，将最右侧字符 `s[right]` 加入当前窗口 `window` 中，记录该字符个数。并验证该字符是否和 `need` 中个对应字符个数相等。如果相等则验证的字符个数 +1，即 `valid += 1`。
-- 如果该窗口字符长度大于等于 `window_size` 个，即 `right - left + 1 >= window_size`。则不断右移 `left`，缩小滑动窗口长度。
-  - 如果验证字符个数 `valid` 等于窗口长度 `window_size`，则 `s[left, right + 1]` 为 `p` 的异位词，所以将 `left` 加入到答案数组中。
-  - 如果`s[left]` 在 `need` 中，则更新窗口中对应字符的个数，同时维护 `valid` 值。
-- 右移 `right`，直到 `right >= len(nums)` 结束。
-- 输出答案数组 `res`。
+维护一个固定长度为 $len(p)$ 的滑动窗口。于是问题的难点变为了如何判断 $s$ 的子串和 $p$ 是异位词。可以使用两个字典来分别存储 $s$ 的子串中各个字符个数和 $p$ 中各个字符个数。如果两个字典对应的键值全相等，则说明 $s$ 的子串和 $p$ 是异位词。但是这样每一次比较的操作时间复杂度是 $O(n)$，我们可以通过在滑动数组中逐字符比较的方式来减少两个字典之间相互比较的复杂度，并用 $valid$ 记录经过验证的字符个数。整个算法步骤如下：
 
-## 代码
+- 使用哈希表 $need$ 记录 $p$ 中各个字符出现次数。使用字典 $window$ 记录 $s$ 的子串中各个字符出现的次数。使用数组 $res$ 记录答案。使用 $valid$ 记录 $s$ 的子串中经过验证的字符个数。使用 $window\underline{}size$ 表示窗口大小，值为 $len(p)$。使用两个指针 $left$、$right$。分别指向滑动窗口的左右边界。
+- 一开始，$left$、$right$ 都指向 $0$。
+- 如果 $s[right]$ 出现在 $need$ 中，将最右侧字符 $s[right]$ 加入当前窗口 $window$ 中，记录该字符个数。并验证该字符是否和 $need$ 中个对应字符个数相等。如果相等则验证的字符个数加 $1$，即 `valid += 1`。
+- 如果该窗口字符长度大于等于 $window\underline{}size$ 个，即 $right - left + 1 \ge window\underline{}size$。则不断右移 $left$，缩小滑动窗口长度。
+  - 如果验证字符个数 $valid$ 等于窗口长度 $window\underline{}size$，则 $s[left, right + 1]$ 为 $p$ 的异位词，所以将 $left$ 加入到答案数组中。
+  - 如果$s[left]$ 在 $need$ 中，则更新窗口中对应字符的个数，同时维护 $valid$ 值。
+- 右移 $right$，直到 $right \ge len(nums)$ 结束。
+- 输出答案数组 $res$。
+
+### 思路 1：代码
 
 ```python
 class Solution:
@@ -60,3 +89,8 @@ class Solution:
         return res
 ```
 
+### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n + m + |\sum|)$，其中 $n$、$m$ 分别为字符串 $s$、$p$ 的长度，$\sum$ 为字符集，本题中 $|\sum| = 26$。
+- **空间复杂度**：$|\sum|$。
+
diff --git a/Solutions/1051. 高度检查器.md b/Solutions/1051. 高度检查器.md
@@ -9,49 +9,106 @@
 
 ## 题目大意
 
-**描述**：
+**描述**：学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。
 
-**要求**：
+排序后的高度情况用整数数组 $expected$ 表示，其中 $expected[i]$ 是预计排在这一行中第 $i$ 位的学生的高度（下标从 $0$ 开始）。
+
+给定一个整数数组 $heights$ ，表示当前学生站位的高度情况。$heights[i]$ 是这一行中第 $i$ 位学生的高度（下标从 $0$ 开始）。
+
+**要求**：返回满足 $heights[i] \ne expected[i]$ 的下标数量 。
 
 **说明**：
 
-- 
+- $1 \le heights.length \le 100$。
+- $1 \le heights[i] \le 100$。
 
 **示例**：
 
 - 示例 1：
 
 ```python
+输入：heights = [1,1,4,2,1,3]
+输出：3 
+解释：
+高度：[1,1,4,2,1,3]
+预期：[1,1,1,2,3,4]
+下标 2 、4 、5 处的学生高度不匹配。
 ```
 
 - 示例 2：
 
 ```python
+输入：heights = [5,1,2,3,4]
+输出：5
+解释：
+高度：[5,1,2,3,4]
+预期：[1,2,3,4,5]
+所有下标的对应学生高度都不匹配。
 ```
 
 ## 解题思路
 
-### 思路 1：
+### 思路 1：排序算法
+
+1. 将数组 $heights$ 复制一份，记为 $expected$。
+2. 对数组 $expected$ 进行排序。
+3. 排序之后，对比并统计 $heights[i] \ne expected[i]$ 的下标数量，记为 $ans$。
+4. 返回 $ans$。
 
 ### 思路 1：代码
 
 ```Python
+class Solution:
+    def heightChecker(self, heights: List[int]) -> int:
+        expected = sorted(heights)
+
+        ans = 0
+        for i in range(len(heights)):
+            if expected[i] != heights[i]:
+                ans += 1
+        return ans
 ```
 
 ### 思路 1：复杂度分析
 
-- **时间复杂度**：
-- **空间复杂度**：
+- **时间复杂度**：$O(n \times \log n)$，其中 $n$ 为数组 $heights$ 的长度。
+- **空间复杂度**：$O(n)$。
+
+### 思路 2：计数排序
 
-### 思路 2：
+题目中 $heights[i]$ 的数据范围为 $[1, 100]$，所以我们可以使用计数排序。
 
 ### 思路 2：代码
 
 ```python
+class Solution:
+    def heightChecker(self, heights: List[int]) -> int:
+        # 待排序数组中最大值元素 heights_max = 100 和最小值元素 heights_min = 1
+        heights_min, heights_max = 1, 100
+        # 定义计数数组 counts，大小为 最大值元素 - 最小值元素 + 1
+        size = heights_max - heights_min + 1
+        counts = [0 for _ in range(size)]
+		
+        # 统计值为 height 的元素出现的次数
+        for height in heights:
+            counts[height - heights_min] += 1
+
+        ans = 0
+        idx = 0
+        # 从小到大遍历 counts 的元素值范围
+        for height in range(heights_min, heights_max + 1):
+            while counts[height - heights_min]:
+                # 对于每个元素值，判断是否与对应位置上的 heights[idx] 相等
+                if heights[idx] != height:
+                    ans += 1
+                idx += 1
+                counts[height - heights_min] -= 1
+        
+        return ans
 ```
 
 ### 思路 2：复杂度分析
 
-- **时间复杂度**：
-- **空间复杂度**：
+- **时间复杂度**：$O(n + k)$，其中 $n$ 为数组 $heights$ 的长度，$k$ 为数组 $heights$ 的值域范围。
+- **空间复杂度**：$O(k)$。
 
diff --git a/Solutions/1151. 最少交换次数来组合所有的 1.md b/Solutions/1151. 最少交换次数来组合所有的 1.md
@@ -9,25 +9,56 @@
 
 ## 题目大意
 
-给定一个二进制数组 `data`。
+**描述**：给定一个二进制数组 $data$。
 
-要求：通过交换位置，将数组中任何位置上的 `1` 组合到一起，并返回所有可能中所需的最少交换次数。
+**要求**：通过交换位置，将数组中任何位置上的 $1$ 组合到一起，并返回所有可能中所需的最少交换次数。c 
+
+**说明**：
+
+- $1 \le data.length \le 10^5$。
+- $data[i] == 0 \text{ or } 1$。
+
+**示例**：
+
+- 示例 1：
+
+```python
+输入: data = [1,0,1,0,1]
+输出: 1
+解释: 
+有三种可能的方法可以把所有的 1 组合在一起：
+[1,1,1,0,0]，交换 1 次；
+[0,1,1,1,0]，交换 2 次；
+[0,0,1,1,1]，交换 1 次。
+所以最少的交换次数为 1。
+```
+
+- 示例 2：
+
+```python
+输入：data = [0,0,0,1,0]
+输出：0
+解释： 
+由于数组中只有一个 1，所以不需要交换。
+```
 
 ## 解题思路
 
-将数组中任何位置上的 `1` 组合到一起，并要求最少的交换次数。也就是说交换之后，某个连续子数组中全是 `1`，数组其他位置全是 `0`。为此，我们可以维护一个固定长度为 `1` 的个数的滑动窗口，找到滑动窗口中 `0` 最少的个数，这样最终交换出去的 `0` 最少，交换次数也最少。
+### 思路 1：滑动窗口
 
-求最少交换次数，也就是求滑动窗口中最少的 `0` 的个数。具体做法如下：
+将数组中任何位置上的 $1$ 组合到一起，并要求最少的交换次数。也就是说交换之后，某个连续子数组中全是 $1$，数组其他位置全是 $0$。为此，我们可以维护一个固定长度为 $1$ 的个数的滑动窗口，找到滑动窗口中 $0$ 最少的个数，这样最终交换出去的 $0$ 最少，交换次数也最少。
 
-1. 统计 `1` 的个数，并设置为窗口长度 `window_size`。使用 `window_count` 维护窗口中 `0` 的个数。使用 `ans` 维护窗口中最少的 `0` 的个数，也可以叫做最少交换次数。
-2. 如果 `window_size` 为 `0`，则说明不用交换，直接返回 `0`。
-3. 使用两个指针 `left`、`right`。`left` 、`right` 都指向数组的第一个元素，即：`left = 0`，`right = 0`。
-4. 如果 `data[right] == 0`，则更新窗口中 `0` 的个数，即 `window_count += 1`。然后向右移动 `right`。
-5. 当窗口元素个数为 `window_size` 时，即：`right - left + 1 >= window_size` 时，更新窗口中最少的 `0` 的个数。
-6. 然后如果左侧 `data[left] == 0`，则更新窗口中 `0` 的个数，即 `window_count -= 1`。然后向右移动 `left`，从而缩小窗口长度，即 `left += 1`，使得窗口大小始终保持为 `window_size`。
-7. 重复 4 ~ 6 步，直到 `right` 到达数组末尾。返回答案 `ans`。
+求最少交换次数，也就是求滑动窗口中最少的 $0$ 的个数。具体做法如下：
 
-## 代码
+1. 统计 $1$ 的个数，并设置为窗口长度 $window\underline{}size$。使用 $window\underline{}count$ 维护窗口中 $0$ 的个数。使用 $ans$ 维护窗口中最少的 $0$ 的个数，也可以叫做最少交换次数。
+2. 如果 $window\underline{}size$ 为 $0$，则说明不用交换，直接返回 $0$。
+3. 使用两个指针 $left$、$right$。$left$、$right$ 都指向数组的第一个元素，即：`left = 0`，`right = 0`。
+4. 如果 $data[right] == 0$，则更新窗口中 $0$ 的个数，即 `window_count += 1`。然后向右移动 $right$。
+5. 当窗口元素个数为 $window\underline{}size$ 时，即：$right - left + 1 \ge window\underline{}size$ 时，更新窗口中最少的 $0$ 的个数。
+6. 然后如果左侧 $data[left] == 0$，则更新窗口中 $0$ 的个数，即 `window_count -= 1`。然后向右移动 $left$，从而缩小窗口长度，即 `left += 1`，使得窗口大小始终保持为 $window\underline{}size$。
+7. 重复 4 ~ 6 步，直到 $right$ 到达数组末尾。返回答案 $ans$。
+
+### 思路 1：代码
 
 ```python
 class Solution:
@@ -55,3 +86,8 @@ class Solution:
         return ans if ans != float('inf') else 0
 ```
 
+### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n)$，其中 $n$ 为数组 $data$ 的长度。
+- **空间复杂度**：$O(1)$。
+
diff --git a/Solutions/1176. 健身计划评估.md b/Solutions/1176. 健身计划评估.md
@@ -9,30 +9,56 @@
 
 ## 题目大意
 
-好友给自己制定了一份健身计划。想请你帮他评估一下这份计划是否合理。
+**描述**：好友给自己制定了一份健身计划。想请你帮他评估一下这份计划是否合理。
 
-给定一个数组 `calories`，其中 `calories[i]` 代表好友第 `i` 天需要消耗的卡路里总量。再给定 `lower` 代表较低消耗的卡路里，`upper` 代表较高消耗的卡路里。再给定一个整数 `k`，代表连续 `k` 天。
+给定一个数组 $calories$，其中 $calories[i]$ 代表好友第 $i$ 天需要消耗的卡路里总量。再给定 $lower$ 代表较低消耗的卡路里，$upper$ 代表较高消耗的卡路里。再给定一个整数 $k$，代表连续 $k$ 天。
 
-- 如果你的好友在这一天以及之后连续 `k` 天内消耗的总卡路里 `T` 小于 `lower`，则这一天的计划相对糟糕，并失去 `1` 分。
-- 如果你的好友在这一天以及之后连续 `k` 天内消耗的总卡路里 `T` 高于 `upper`，则这一天的计划相对优秀，并得到 `1` 分。
-- 如果你的好友在这一天以及之后连续 `k` 天内消耗的总卡路里 `T` 大于等于 `lower`，并且小于等于 `upper`，则这份计划普普通通，分值不做变动。
+- 如果你的好友在这一天以及之后连续 $k$ 天内消耗的总卡路里 $T$ 小于 $lower$，则这一天的计划相对糟糕，并失去 $1$ 分。
+- 如果你的好友在这一天以及之后连续 $k$ 天内消耗的总卡路里 $T$ 高于 $upper$，则这一天的计划相对优秀，并得到 $1$ 分。
+- 如果你的好友在这一天以及之后连续 $k$ 天内消耗的总卡路里 $T$ 大于等于 $lower$，并且小于等于 $upper$，则这份计划普普通通，分值不做变动。
 
-输出最后评估的得分情况。
+**要求**：输出最后评估的得分情况。
+
+**说明**：
+
+- $1 \le k \le calories.length \le 10^5$。
+- $0 \le calories[i] \le 20000$。
+- $0 \le lower \le upper$。 
+
+**示例**：
+
+- 示例 1：
+
+```python
+输入：calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
+输出：0
+解释：calories[0], calories[1] < lower 而 calories[3], calories[4] > upper, 总分 = 0.
+```
+
+- 示例 2：
+
+```python
+输入：calories = [3,2], k = 2, lower = 0, upper = 1
+输出：1
+解释：calories[0] + calories[1] > upper, 总分 = 1.
+```
 
 ## 解题思路
 
-固定长度为 `k` 的滑动窗口题目。具体做法如下：
+### 思路 1：滑动窗口
 
-1. `score` 用来维护得分情况，初始值为 `0`。`window_sum` 用来维护窗口中卡路里总量。
-2. `left` 、`right` 都指向数组的第一个元素，即：`left = 0`，`right = 0`。
-3. 向右移动 `right`，先将 `k` 个元素填入窗口中。
-4. 当窗口元素个数为 `k` 时，即：`right - left + 1 >= k` 时，计算窗口内的卡路里总量，并判断和 `upper`、`lower` 的关系。同时维护得分情况。
-5. 然后向右移动 `left`，从而缩小窗口长度，即 `left += 1`，使得窗口大小始终保持为 `k`。
-6. 重复 4 ~ 5 步，直到 `right` 到达数组末尾。
+固定长度为 $k$ 的滑动窗口题目。具体做法如下：
 
-最后输出得分情况 `score`。
+1. $score$ 用来维护得分情况，初始值为 $0$。$window\underline{}sum$ 用来维护窗口中卡路里总量。
+2. $left$ 、$right$ 都指向数组的第一个元素，即：`left = 0`，`right = 0`。
+3. 向右移动 $right$，先将 $k$ 个元素填入窗口中。
+4. 当窗口元素个数为 $k$ 时，即：$right - left + 1 \ge k$ 时，计算窗口内的卡路里总量，并判断和 $upper$、$lower$ 的关系。同时维护得分情况。
+5. 然后向右移动 $left$，从而缩小窗口长度，即 `left += 1`，使得窗口大小始终保持为 $k$。
+6. 重复 $4 \sim 5$ 步，直到 $right$ 到达数组末尾。
 
-## 代码
+最后输出得分情况 $score$。
+
+### 思路 1：代码
 
 ```python
 class Solution:
@@ -55,3 +81,8 @@ class Solution:
         return score
 ```
 
+### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n)$，其中 $n$ 为数组 $calories$ 的长度。
+- **空间复杂度**：$O(1)$。
+
