Skip to content

Commit 61f2a27

Browse files
authored
Add files via upload
1 parent 8bba6c5 commit 61f2a27

8 files changed

+212
-0
lines changed

leetcode/079.单词搜索.py

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
class Solution(object):
2+
def exist(self, board, word):
3+
m, n = len(board), len(board[0])
4+
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
5+
6+
def dfs(x, y, word, board):
7+
# 递归终止条件,全部搜索完成
8+
if not word:
9+
return True
10+
# 记录字符,然后变换该字符,避免重用
11+
c = board[x][y]
12+
board[x][y] = '.'
13+
# 遍历搜索四个方向的字符
14+
for dx, dy in d:
15+
nx, ny = x+dx, y+dy
16+
if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == word[0] and dfs(nx, ny, word[1:], board):
17+
return True
18+
# 四个方向都不满足条件,回溯,返回False
19+
board[x][y] = c
20+
return False
21+
22+
# 遍历二维矩阵每个字符,深度优先搜索
23+
for i in range(m):
24+
for j in range(n):
25+
# 有一条路径满足条件
26+
if board[i][j] == word[0] and dfs(i, j, word[1:], board):
27+
return True
28+
# 全部不满足条件
29+
return False
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
# 将单词按照长度归类存到字典中,匹配时逐个遍历比较相同长度的单词
2+
class WordDictionary(object):
3+
4+
def __init__(self):
5+
from collections import defaultdict
6+
self.d = defaultdict(list)
7+
8+
def addWord(self, word):
9+
self.d[len(word)] += [word]
10+
11+
def search(self, word):
12+
n = len(word)
13+
for w in self.d[n]:
14+
for i in range(n):
15+
if word[i] == '.':
16+
continue
17+
if word[i] != w[i]:
18+
break
19+
else:
20+
return True
21+
return False
22+
23+
24+
# 字典树,回溯法
25+
class WordDictionary(object):
26+
27+
def __init__(self):
28+
# {'b': {'a': {'d': {'#': {}}}}, 'd': {'a': {'d': {'#': {}}}}, 'm': {'a': {'d': {'#': {}}}}}
29+
self.lookup = {}
30+
31+
def addWord(self, word):
32+
tree = self.lookup
33+
for a in word:
34+
tree = tree.setdefault(a, {})
35+
tree["#"] = {}
36+
37+
def search(self, word):
38+
def helper(word, tree):
39+
# 递归终止条件
40+
if not word:
41+
# 搜索完最后一个字符
42+
if "#" in tree:
43+
return True
44+
# 未搜索完
45+
return False
46+
# 如果字符是'.',需要遍历判断每个字典树
47+
if word[0] == ".":
48+
for t in tree:
49+
if helper(word[1:], tree[t]):
50+
return True
51+
# 如果字符在字典中,只需要判断该字符的字典树
52+
elif word[0] in tree:
53+
if helper(word[1:], tree[word[0]]):
54+
return True
55+
# 字符不在字典中
56+
return False
57+
return helper(word, self.lookup)

leetcode/347.前 K 个高频元素.py

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
from collections import Counter
2+
class Solution(object):
3+
def topKFrequent(self, nums, k):
4+
# {1: 3, 2: 2, 3: 1} → [(1, 3), (2, 2)]
5+
return [item[0] for item in Counter(nums).most_common(k)]
6+
7+
s = Solution()
8+
nums = [1,1,1,2,2,3]
9+
k = 2
10+
res = s.topKFrequent(nums, k)
11+
print(res)

leetcode/435.无重叠区间.py

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
# 贪心算法。按结尾升序排序,以最小结尾与其他区间的开头比较,跳过重叠的区间,记录不重叠区间的个数,并更新结尾,再相减得到要移除的区间个数。
2+
class Solution(object):
3+
def eraseOverlapIntervals(self, intervals):
4+
if not intervals:
5+
return 0
6+
intervals = sorted(intervals, key=lambda k: k[1])
7+
end, count, n = intervals[0][1], 1, len(intervals)
8+
for i in range(1, n):
9+
if intervals[i][0] < end:
10+
continue
11+
count += 1
12+
end = intervals[i][1]
13+
return n-count

leetcode/542.01 矩阵.py

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
class Solution(object):
2+
def updateMatrix(self, matrix):
3+
m, n = len(matrix), len(matrix[0])
4+
# 结果矩阵初始化为-1,表示未搜索
5+
q, res = [], [[-1]*n for _ in range(m)]
6+
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
7+
8+
# 从值为0开始搜索,将其添加到队列
9+
for i in range(m):
10+
for j in range(n):
11+
if matrix[i][j] == 0:
12+
res[i][j] = 0
13+
q += [(i, j)]
14+
15+
# 搜索四个方向
16+
for x, y in q:
17+
for dx, dy in d:
18+
nx, ny = x + dx, y + dy
19+
# 将未搜索的区域赋值,值为上个区域值加1,并将新区域添加到队列中继续搜素偶
20+
if 0 <= nx < m and 0 <= ny < n and res[nx][ny] == -1:
21+
res[nx][ny] = res[x][y] + 1
22+
q += [(nx, ny)]
23+
24+
return res

leetcode/621.任务调度器.py

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
# 完成所有任务的最短时间取决于出现次数最多的任务数量
2+
# A -> (单位时间) -> (单位时间) -> A -> (单位时间) -> (单位时间) -> A
3+
# 计算过程: (出现最多次数的任务的次数 - 1) * (n + 1) + (出现最多次数的任务个数)
4+
class Solution(object):
5+
def leastInterval(self, tasks, n):
6+
d = {}
7+
# 统计每个任务的次数,并按次数归类存放在字典中
8+
for task in set(tasks):
9+
count = tasks.count(task)
10+
if count not in d:
11+
d[count] = [task]
12+
else:
13+
d[count] += [task]
14+
# 获取最大次数
15+
max_count = max(d.keys())
16+
# 计算最短时间
17+
res = (max_count - 1) * (n + 1) + len(d[max_count])
18+
# 当出现次数最多的任务中间的单位时间填满后,仍有其他次数小的任务需要执行
19+
# 用上面的计算方法会使最短次数比原数组长度短,此时应返回原数组长度
20+
if res < len(tasks):
21+
return len(tasks)
22+
return res

leetcode/934.最短的桥.py

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
class Solution(object):
2+
def shortestBridge(self, A):
3+
m, n = len(A), len(A[0])
4+
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
5+
6+
# 深度优先搜索,将一片岛屿置为-1
7+
def dfs(x, y):
8+
A[x][y] = -1
9+
for dx, dy in d:
10+
nx, ny = x + dx, y + dy
11+
if 0 <= nx < m and 0 <= ny < n and A[nx][ny] == 1:
12+
dfs(nx, ny)
13+
14+
# 找到一个1,将其所在的A岛屿置为-1
15+
flag = 0
16+
for i in range(m):
17+
for j in range(n):
18+
if A[i][j] == 1:
19+
dfs(i, j)
20+
flag = 1
21+
if flag:
22+
break
23+
if flag:
24+
break
25+
26+
# 将B岛屿每个位置添加到队列中
27+
q = []
28+
for i in range(m):
29+
for j in range(n):
30+
if A[i][j] == 1:
31+
q.append((i, j, 0))
32+
33+
# 广度优先搜索,B岛屿中某个位置先到达A岛屿,则返回其路径长度
34+
while q:
35+
x, y, r = q.pop(0)
36+
for dx, dy in d:
37+
nx, ny = x + dx, y + dy
38+
if 0 <= nx < m and 0 <= ny < n:
39+
if A[nx][ny] == 0:
40+
A[nx][ny] = 1
41+
q.append((nx, ny, r + 1))
42+
if A[nx][ny] == -1:
43+
return r
Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
# 逆向操作
2+
class Solution(object):
3+
def deckRevealedIncreasing(self, deck):
4+
# 将原数组倒序排序
5+
deck.sort(reverse=True)
6+
res = []
7+
while deck:
8+
# 如果新数组有元素,则将最后一个元素移到首位
9+
if res:
10+
res = [res[-1]] + res[:-1]
11+
# 再插入新元素到首位
12+
res.insert(0, deck.pop(0))
13+
return res

0 commit comments

Comments
 (0)