Leetcode按类型
字典树
框架
原理
- 字典树（Trie）：
- 想字典一样的树
🚩(1.5h) 440. 字典序的第K小数字
给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。
注意：1 ≤ k ≤ n ≤ 109。
1
2
3
4
5
6
7
8
9
10
示例 :
输入:
n: 13 k: 2
输出:
10
解释:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def findKthNumber(self, n: int, k: int) -> int:
# prefix 前缀 n 上界
p = 1
prefix = 1
while p < k:
count += next_prefix - cur
cur *= 10 # 10
next_prefix *= 10 # 20
return count
1
2
3
4
5
6
from typing import List
nums =
solution = Solution()
result = solution.maxArea(nums)
result
并查集
🚩200. 岛屿数量
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
示例 1:
输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1
示例 2:
输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
