Skip to content

Commit f819b24

Browse files
itchargeitcharge
committed
更新题解列表
1 parent 2b2eaf9 commit f819b24

9 files changed

+396
-4
lines changed

‎Contents/00.Introduction/04.Solutions-List.md‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
# LeetCode 题解（已完成 827 道）
1+
# LeetCode 题解（已完成 832 道）
22

33
| 题号 | 标题 | 题解 | 标签 | 难度 |
44
| :------ | :------ | :------ | :------ | :------ |
@@ -425,6 +425,7 @@
425425
| 0801 | [使序列递增的最小交换次数](https://leetcode.cn/problems/minimum-swaps-to-make-sequences-increasing/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0801.%20%E4%BD%BF%E5%BA%8F%E5%88%97%E9%80%92%E5%A2%9E%E7%9A%84%E6%9C%80%E5%B0%8F%E4%BA%A4%E6%8D%A2%E6%AC%A1%E6%95%B0.md) | 数组、动态规划 | 困难 |
426426
| 0802 | [找到最终的安全状态](https://leetcode.cn/problems/find-eventual-safe-states/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0802.%20%E6%89%BE%E5%88%B0%E6%9C%80%E7%BB%88%E7%9A%84%E5%AE%89%E5%85%A8%E7%8A%B6%E6%80%81.md) | 深度优先搜索、广度优先搜索、图、拓扑排序 | 中等 |
427427
| 0803 | [打砖块](https://leetcode.cn/problems/bricks-falling-when-hit/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0803.%20%E6%89%93%E7%A0%96%E5%9D%97.md) | 并查集、数组、矩阵 | 困难 |
428+
| 0804 | [唯一摩尔斯密码词](https://leetcode.cn/problems/unique-morse-code-words/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0804.%20%E5%94%AF%E4%B8%80%E6%91%A9%E5%B0%94%E6%96%AF%E5%AF%86%E7%A0%81%E8%AF%8D.md) | 数组、哈希表、字符串 | 简单 |
428429
| 0806 | [写字符串需要的行数](https://leetcode.cn/problems/number-of-lines-to-write-string/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0806.%20%E5%86%99%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%9C%80%E8%A6%81%E7%9A%84%E8%A1%8C%E6%95%B0.md) | 数组、字符串 | 简单 |
429430
| 0811 | [子域名访问计数](https://leetcode.cn/problems/subdomain-visit-count/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0811.%20%E5%AD%90%E5%9F%9F%E5%90%8D%E8%AE%BF%E9%97%AE%E8%AE%A1%E6%95%B0.md) | 数组、哈希表、字符串、计数 | 中等 |
430431
| 0814 | [二叉树剪枝](https://leetcode.cn/problems/binary-tree-pruning/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0814.%20%E4%BA%8C%E5%8F%89%E6%A0%91%E5%89%AA%E6%9E%9D.md) | 树、深度优先搜索、二叉树 | 中等 |
@@ -447,6 +448,7 @@
447448
| 0860 | [柠檬水找零](https://leetcode.cn/problems/lemonade-change/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0860.%20%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.md) | 贪心、数组 | 简单 |
448449
| 0861 | [翻转矩阵后的得分](https://leetcode.cn/problems/score-after-flipping-matrix/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0861.%20%E7%BF%BB%E8%BD%AC%E7%9F%A9%E9%98%B5%E5%90%8E%E7%9A%84%E5%BE%97%E5%88%86.md) | 贪心、位运算、数组、矩阵 | 中等 |
449450
| 0867 | [转置矩阵](https://leetcode.cn/problems/transpose-matrix/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0867.%20%E8%BD%AC%E7%BD%AE%E7%9F%A9%E9%98%B5.md) | 数组、矩阵、模拟 | 简单 |
451+
| 0868 | [二进制间距](https://leetcode.cn/problems/binary-gap/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0868.%20%E4%BA%8C%E8%BF%9B%E5%88%B6%E9%97%B4%E8%B7%9D.md) | 位运算 | 简单 |
450452
| 0872 | [叶子相似的树](https://leetcode.cn/problems/leaf-similar-trees/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0872.%20%E5%8F%B6%E5%AD%90%E7%9B%B8%E4%BC%BC%E7%9A%84%E6%A0%91.md) | 树、深度优先搜索、二叉树 | 简单 |
451453
| 0873 | [最长的斐波那契子序列的长度](https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0873.%20%E6%9C%80%E9%95%BF%E7%9A%84%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E5%AD%90%E5%BA%8F%E5%88%97%E7%9A%84%E9%95%BF%E5%BA%A6.md) | 数组、哈希表、动态规划 | 中等 |
452454
| 0875 | [爱吃香蕉的珂珂](https://leetcode.cn/problems/koko-eating-bananas/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0875.%20%E7%88%B1%E5%90%83%E9%A6%99%E8%95%89%E7%9A%84%E7%8F%82%E7%8F%82.md) | 数组、二分查找 | 中等 |
@@ -563,6 +565,7 @@
563565
| 1447 | [最简分数](https://leetcode.cn/problems/simplified-fractions/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1447.%20%E6%9C%80%E7%AE%80%E5%88%86%E6%95%B0.md) | 数学、字符串、数论 | 中等 |
564566
| 1449 | [数位成本和为目标值的最大数字](https://leetcode.cn/problems/form-largest-integer-with-digits-that-add-up-to-target/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1449.%20%E6%95%B0%E4%BD%8D%E6%88%90%E6%9C%AC%E5%92%8C%E4%B8%BA%E7%9B%AE%E6%A0%87%E5%80%BC%E7%9A%84%E6%9C%80%E5%A4%A7%E6%95%B0%E5%AD%97.md) | 数组、动态规划 | 困难 |
565567
| 1450 | [在既定时间做作业的学生人数](https://leetcode.cn/problems/number-of-students-doing-homework-at-a-given-time/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1450.%20%E5%9C%A8%E6%97%A2%E5%AE%9A%E6%97%B6%E9%97%B4%E5%81%9A%E4%BD%9C%E4%B8%9A%E7%9A%84%E5%AD%A6%E7%94%9F%E4%BA%BA%E6%95%B0.md) | 数组 | 简单 |
568+
| 1451 | [重新排列句子中的单词](https://leetcode.cn/problems/rearrange-words-in-a-sentence/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1451.%20%E9%87%8D%E6%96%B0%E6%8E%92%E5%88%97%E5%8F%A5%E5%AD%90%E4%B8%AD%E7%9A%84%E5%8D%95%E8%AF%8D.md) | 字符串、排序 | 中等 |
566569
| 1456 | [定长子串中元音的最大数目](https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1456.%20%E5%AE%9A%E9%95%BF%E5%AD%90%E4%B8%B2%E4%B8%AD%E5%85%83%E9%9F%B3%E7%9A%84%E6%9C%80%E5%A4%A7%E6%95%B0%E7%9B%AE.md) | 字符串、滑动窗口 | 中等 |
567570
| 1480 | [一维数组的动态和](https://leetcode.cn/problems/running-sum-of-1d-array/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1480.%20%E4%B8%80%E7%BB%B4%E6%95%B0%E7%BB%84%E7%9A%84%E5%8A%A8%E6%80%81%E5%92%8C.md) | 数组、前缀和 | 简单 |
568571
| 1482 | [制作 m 束花所需的最少天数](https://leetcode.cn/problems/minimum-number-of-days-to-make-m-bouquets/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1482.%20%E5%88%B6%E4%BD%9C%20m%20%E6%9D%9F%E8%8A%B1%E6%89%80%E9%9C%80%E7%9A%84%E6%9C%80%E5%B0%91%E5%A4%A9%E6%95%B0.md) | 数组、二分查找 | 中等 |
@@ -606,6 +609,8 @@
606609
| 1876 | [长度为三且各字符不同的子字符串](https://leetcode.cn/problems/substrings-of-size-three-with-distinct-characters/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1876.%20%E9%95%BF%E5%BA%A6%E4%B8%BA%E4%B8%89%E4%B8%94%E5%90%84%E5%AD%97%E7%AC%A6%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.md) | 哈希表、字符串、计数、滑动窗口 | 简单 |
607610
| 1877 | [数组中最大数对和的最小值](https://leetcode.cn/problems/minimize-maximum-pair-sum-in-array/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1877.%20%E6%95%B0%E7%BB%84%E4%B8%AD%E6%9C%80%E5%A4%A7%E6%95%B0%E5%AF%B9%E5%92%8C%E7%9A%84%E6%9C%80%E5%B0%8F%E5%80%BC.md) | 贪心、数组、双指针、排序 | 中等 |
608611
| 1879 | [两个数组最小的异或值之和](https://leetcode.cn/problems/minimum-xor-sum-of-two-arrays/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1879.%20%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E6%9C%80%E5%B0%8F%E7%9A%84%E5%BC%82%E6%88%96%E5%80%BC%E4%B9%8B%E5%92%8C.md) | 位运算、数组、动态规划、状态压缩 | 困难 |
612+
| 1893 | [检查是否区域内所有整数都被覆盖](https://leetcode.cn/problems/check-if-all-the-integers-in-a-range-are-covered/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1893.%20%E6%A3%80%E6%9F%A5%E6%98%AF%E5%90%A6%E5%8C%BA%E5%9F%9F%E5%86%85%E6%89%80%E6%9C%89%E6%95%B4%E6%95%B0%E9%83%BD%E8%A2%AB%E8%A6%86%E7%9B%96.md) | 数组、哈希表、前缀和 | 简单 |
613+
| 1897 | [重新分配字符使所有字符串都相等](https://leetcode.cn/problems/redistribute-characters-to-make-all-strings-equal/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1897.%20%E9%87%8D%E6%96%B0%E5%88%86%E9%85%8D%E5%AD%97%E7%AC%A6%E4%BD%BF%E6%89%80%E6%9C%89%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%83%BD%E7%9B%B8%E7%AD%89.md) | 哈希表、字符串、计数 | 简单 |
609614
| 1903 | [字符串中的最大奇数](https://leetcode.cn/problems/largest-odd-number-in-string/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1903.%20%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%9C%80%E5%A4%A7%E5%A5%87%E6%95%B0.md) | 贪心、数学、字符串 | 简单 |
610615
| 1925 | [统计平方和三元组的数目](https://leetcode.cn/problems/count-square-sum-triples/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1925.%20%E7%BB%9F%E8%AE%A1%E5%B9%B3%E6%96%B9%E5%92%8C%E4%B8%89%E5%85%83%E7%BB%84%E7%9A%84%E6%95%B0%E7%9B%AE.md) | 数学、枚举 | 简单 |
611616
| 1929 | [数组串联](https://leetcode.cn/problems/concatenation-of-array/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1929.%20%E6%95%B0%E7%BB%84%E4%B8%B2%E8%81%94.md) | 数组 | 简单 |

‎Contents/00.Introduction/05.Categories-List.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -551,7 +551,7 @@
551551
| 0354 | [俄罗斯套娃信封问题](https://leetcode.cn/problems/russian-doll-envelopes/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0354.%20%E4%BF%84%E7%BD%97%E6%96%AF%E5%A5%97%E5%A8%83%E4%BF%A1%E5%B0%81%E9%97%AE%E9%A2%98.md) | 数组、二分查找、动态规划、排序 | 困难 |
552552
| 0673 | [最长递增子序列的个数](https://leetcode.cn/problems/number-of-longest-increasing-subsequence/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0673.%20%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97%E7%9A%84%E4%B8%AA%E6%95%B0.md) | 树状数组、线段树、数组、动态规划 | 中等 |
553553
| 1310 | [子数组异或查询](https://leetcode.cn/problems/xor-queries-of-a-subarray/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1310.%20%E5%AD%90%E6%95%B0%E7%BB%84%E5%BC%82%E6%88%96%E6%9F%A5%E8%AF%A2.md) | 位运算、数组、前缀和 | 中等 |
554-
| 1893 | [检查是否区域内所有整数都被覆盖](https://leetcode.cn/problems/check-if-all-the-integers-in-a-range-are-covered/) | | 数组、哈希表、前缀和 | 简单 |
554+
| 1893 | [检查是否区域内所有整数都被覆盖](https://leetcode.cn/problems/check-if-all-the-integers-in-a-range-are-covered/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1893.%20%E6%A3%80%E6%9F%A5%E6%98%AF%E5%90%A6%E5%8C%BA%E5%9F%9F%E5%86%85%E6%89%80%E6%9C%89%E6%95%B4%E6%95%B0%E9%83%BD%E8%A2%AB%E8%A6%86%E7%9B%96.md) | 数组、哈希表、前缀和 | 简单 |
555555

556556
### 并查集题目
557557

‎Contents/07.Tree/04.Binary-Indexed-Tree/02.Binary-Indexed-Tree-List.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,5 +9,5 @@
99
| 0354 | [俄罗斯套娃信封问题](https://leetcode.cn/problems/russian-doll-envelopes/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0354.%20%E4%BF%84%E7%BD%97%E6%96%AF%E5%A5%97%E5%A8%83%E4%BF%A1%E5%B0%81%E9%97%AE%E9%A2%98.md) | 数组、二分查找、动态规划、排序 | 困难 |
1010
| 0673 | [最长递增子序列的个数](https://leetcode.cn/problems/number-of-longest-increasing-subsequence/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/0673.%20%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97%E7%9A%84%E4%B8%AA%E6%95%B0.md) | 树状数组、线段树、数组、动态规划 | 中等 |
1111
| 1310 | [子数组异或查询](https://leetcode.cn/problems/xor-queries-of-a-subarray/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1310.%20%E5%AD%90%E6%95%B0%E7%BB%84%E5%BC%82%E6%88%96%E6%9F%A5%E8%AF%A2.md) | 位运算、数组、前缀和 | 中等 |
12-
| 1893 | [检查是否区域内所有整数都被覆盖](https://leetcode.cn/problems/check-if-all-the-integers-in-a-range-are-covered/) | | 数组、哈希表、前缀和 | 简单 |
12+
| 1893 | [检查是否区域内所有整数都被覆盖](https://leetcode.cn/problems/check-if-all-the-integers-in-a-range-are-covered/) | [Python](https://github.com/itcharge/LeetCode-Py/blob/main/Solutions/1893.%20%E6%A3%80%E6%9F%A5%E6%98%AF%E5%90%A6%E5%8C%BA%E5%9F%9F%E5%86%85%E6%89%80%E6%9C%89%E6%95%B4%E6%95%B0%E9%83%BD%E8%A2%AB%E8%A6%86%E7%9B%96.md) | 数组、哈希表、前缀和 | 简单 |
1313

‎README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -255,4 +255,4 @@
255255
- [动态规划优化题目](./Contents/10.Dynamic-Programming/11.DP-Optimization/04.DP-Optimization-List.md)
256256

257257
## 11. 附加内容
258-
## [12. LeetCode 题解（已完成 827 道）](./Contents/00.Introduction/04.Solutions-List.md)
258+
## [12. LeetCode 题解（已完成 832 道）](./Contents/00.Introduction/04.Solutions-List.md)

‎Solutions/0804. 唯一摩尔斯密码词.md‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
# [0804. 唯一摩尔斯密码词](https://leetcode.cn/problems/unique-morse-code-words/)
2+
3+
- 标签：数组、哈希表、字符串
4+
- 难度：简单
5+
6+
## 题目链接
7+
8+
- [0804. 唯一摩尔斯密码词 - 力扣](https://leetcode.cn/problems/unique-morse-code-words/)
9+
10+
## 题目大意
11+
12+
**描述**：国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串， 比如:
13+
14+
- `'a'` 对应 `".-"`，
15+
- `'b'` 对应 `"-..."`，
16+
- `'c'` 对应 `"-.-."` ，以此类推。
17+
18+
为了方便，所有 $26$ 个英文字母的摩尔斯密码表如下：
19+
20+
`[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]`
21+
22+
给定一个字符串数组 $words$，每个单词可以写成每个字母对应摩尔斯密码的组合。
23+
24+
- 例如，`"cab"` 可以写成 `"-.-..--..."` ，(即 `"-.-."` + `".-"` + `"-..."` 字符串的结合)。我们将这样一个连接过程称作单词翻译。
25+
26+
**要求**：对 $words$ 中所有单词进行单词翻译，返回不同单词翻译的数量。
27+
28+
**说明**：
29+
30+
- $1 \le words.length \le 100$。
31+
- $1 \le words[i].length \le 12$。
32+
- $words[i]$ 由小写英文字母组成。
33+
34+
**示例**：
35+
36+
- 示例 1：
37+
38+
```python
39+
输入: words = ["gin", "zen", "gig", "msg"]
40+
输出: 2
41+
解释:
42+
各单词翻译如下:
43+
"gin" -> "--...-."
44+
"zen" -> "--...-."
45+
"gig" -> "--...--."
46+
"msg" -> "--...--."
47+
48+
共有 2 种不同翻译, "--...-." 和 "--...--.".
49+
```
50+
51+
- 示例 2：
52+
53+
```python
54+
输入：words = ["a"]
55+
输出：1
56+
```
57+
58+
## 解题思路
59+
60+
### 思路 1：模拟 + 哈希表
61+
62+
1. 根据题目要求，将所有单词都转换为对应摩斯密码。
63+
2. 使用哈希表存储所有转换后的摩斯密码。
64+
3. 返回哈希表中不同的摩斯密码个数（脊哈希表的长度）作为答案。
65+
66+
### 思路 1：代码
67+
68+
```Python
69+
class Solution:
70+
def uniqueMorseRepresentations(self, words: List[str]) -> int:
71+
table = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
72+
word_set = set()
73+
74+
for word in words:
75+
word_mose = ""
76+
for ch in word:
77+
word_mose += table[ord(ch) - ord('a')]
78+
word_set.add(word_mose)
79+
80+
return len(word_set)
81+
```
82+
83+
### 思路 1：复杂度分析
84+
85+
- **时间复杂度**：$O(s)$，其中 $s$ 为数组 $words$ 中所有单词的长度之和。
86+
- **空间复杂度**：$O(s)$。
87+

‎Solutions/0868. 二进制间距.md‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
# [0868. 二进制间距](https://leetcode.cn/problems/binary-gap/)
2+
3+
- 标签：位运算
4+
- 难度：简单
5+
6+
## 题目链接
7+
8+
- [0868. 二进制间距 - 力扣](https://leetcode.cn/problems/binary-gap/)
9+
10+
## 题目大意
11+
12+
**描述**：给定一个正整数 $n$。
13+
14+
**要求**：找到并返回 $n$ 的二进制表示中两个相邻 $1$ 之间的最长距离。如果不存在两个相邻的 $1$，返回 $0$。
15+
16+
**说明**：
17+
18+
- $1 \le n \le 10^9$。
19+
20+
**示例**：
21+
22+
- 示例 1：
23+
24+
```python
25+
输入：n = 22
26+
输出：2
27+
解释：22 的二进制是 "10110"。
28+
在 22 的二进制表示中，有三个 1，组成两对相邻的 1。
29+
第一对相邻的 1 中，两个 1 之间的距离为 2。
30+
第二对相邻的 1 中，两个 1 之间的距离为 1。
31+
答案取两个距离之中最大的，也就是 2。
32+
```
33+
34+
- 示例 2：
35+
36+
```python
37+
输入：n = 8
38+
输出：0
39+
解释：8 的二进制是 "1000"。
40+
在 8 的二进制表示中没有相邻的两个 1，所以返回 0。
41+
```
42+
43+
## 解题思路
44+
45+
### 思路 1：遍历
46+
47+
1. 将正整数 $n$ 转为二进制字符串形式 $bin\underline{}n$。
48+
2. 使用变量 $pre$ 记录二进制字符串中上一个 $1$ 的位置，使用变量 $ans$ 存储两个相邻 $1$ 之间的最长距离。
49+
3. 遍历二进制字符串形式 $bin\underline{}n$ 的每一位，遇到 $1$ 时判断并更新两个相邻 $1$ 之间的最长距离。
50+
4. 遍历完返回两个相邻 $1$ 之间的最长距离，即 $ans$。
51+
52+
### 思路 1：代码
53+
54+
```Python
55+
class Solution:
56+
def binaryGap(self, n: int) -> int:
57+
bin_n = bin(n)
58+
pre, ans = 2, 0
59+
60+
for i in range(2, len(bin_n)):
61+
if bin_n[i] == '1':
62+
ans = max(ans, i - pre)
63+
pre = i
64+
65+
return ans
66+
```
67+
68+
### 思路 1：复杂度分析
69+
70+
- **时间复杂度**：$O(\log n)$。
71+
- **空间复杂度**：$O(1)$。
72+

‎Solutions/1451. 重新排列句子中的单词.md‎

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
# [1451. 重新排列句子中的单词](https://leetcode.cn/problems/rearrange-words-in-a-sentence/)
2+
3+
- 标签：字符串、排序
4+
- 难度：中等
5+
6+
## 题目链接
7+
8+
- [1451. 重新排列句子中的单词 - 力扣](https://leetcode.cn/problems/rearrange-words-in-a-sentence/)
9+
10+
## 题目大意
11+
12+
**描述**：「句子」是一个用空格分隔单词的字符串。给定一个满足下述格式的句子 $text$:
13+
14+
- 句子的首字母大写。
15+
- $text$ 中的每个单词都用单个空格分隔。
16+
17+
**要求**：重新排列 $text$ 中的单词，使所有单词按其长度的升序排列。如果两个单词的长度相同，则保留其在原句子中的相对顺序。
18+
19+
请同样按上述格式返回新的句子。
20+
21+
**说明**：
22+
23+
- $text$ 以大写字母开头，然后包含若干小写字母以及单词间的单个空格。
24+
- $1 \le text.length \le 10^5$。
25+
26+
**示例**：
27+
28+
- 示例 1：
29+
30+
```python
31+
输入：text = "Leetcode is cool"
32+
输出："Is cool leetcode"
33+
解释：句子中共有 3 个单词，长度为 8 的 "Leetcode" ，长度为 2 的 "is" 以及长度为 4 的 "cool"。
34+
输出需要按单词的长度升序排列，新句子中的第一个单词首字母需要大写。
35+
```
36+
37+
- 示例 2：
38+
39+
```python
40+
输入：text = "Keep calm and code on"
41+
输出："On and keep calm code"
42+
解释：输出的排序情况如下：
43+
"On" 2 个字母。
44+
"and" 3 个字母。
45+
"keep" 4 个字母，因为存在长度相同的其他单词，所以它们之间需要保留在原句子中的相对顺序。
46+
"calm" 4 个字母。
47+
"code" 4 个字母。
48+
```
49+
50+
## 解题思路
51+
52+
### 思路 1：模拟
53+
54+
1. 将 $text$ 按照 `" "` 进行分割为单词数组 $words$。
55+
2. 将单词数组按照「单词长度」进行升序排序。
56+
3. 将单词数组用 `" "` 连接起来，并将首字母转为大写字母，其他字母转为小写字母，将结果存入答案字符串 $ans$ 中。
57+
4. 返回答案字符串 $ans$。
58+
59+
### 思路 1：代码
60+
61+
```Python
62+
class Solution:
63+
def arrangeWords(self, text: str) -> str:
64+
words = text.split(' ')
65+
words.sort(key=lambda word:len(word))
66+
ans = " ".join(words).capitalize()
67+
68+
return ans
69+
```
70+
71+
### 思路 1：复杂度分析
72+
73+
- **时间复杂度**：$O(n \times \log n)$，其中 $n$ 为字符串 $text$ 的长度。
74+
- **空间复杂度**：$O(n)$。
75+

0 commit comments

Comments
 (0)