前言:每天必须写,多忙都得写,如果我今年 12 月份之前没做到 700 道,我会瞧不起我自己一辈子的
0X00 leetcode 刷题 7 道
0X01 每道题的小小总结
Reverse Linked List
热身题, 这道题之前做过,但是第一眼..看过去没思路
其实就是两个前向指针的问题, 然后不断的移动
pre 记录上一个节点, cur 记录当前节点,temp 记录 cur.next 然后不断移动
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head == None or head.next == None: return head
pre, cur = None, head
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre
Surrounded Regions
一道 dfs 的题目, dfs 有一个确实能找到所有在一个集合里面的点
但是不能,让这个集合的所有点,都知道某个点碰到边界的事情,所以要遍历完所有集合的值以后,保存下来,统一更新
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if len(board) == 0: return
m, n = len(board), len(board[0])
visited = [[False] * n for _ in range(m)]
def dfs(x, y):
if x < 0 or y < 0 or x >= m or y >= n:
self.flip = False
return
if board[x][y] == "X" or visited[x][y]: return
visited[x][y] = True
self.collection.append((x, y))
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for dx, dy in dirs:
dfs(x + dx, y + dy)
for x in range(m):
for y in range(n):
if board[x][y] == "X" or visited[x][y]: continue
self.flip = True
self.collection = []
dfs(x, y)
if not self.flip: continue
for x1, y1 in self.collection:
board[x1][y1] = "X"
Implement Trie (Prefix Tree)
今天主要做了 trie 树,这个题目做过, 3.3 的时候好好总结一下 trie
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = {}
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
p = self.root
for c in word:
if c not in p:
p[c] = {}
p = p[c]
p['#'] = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.find(word)
return node is not None and '#' in node
def find(self, prefix):
p = self.root
for c in prefix:
if c not in p: return None
p = p[c]
return p
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
return self.find(prefix) is not None
Add and Search Word - Data structure design
trie 树的典型应用,不多说了
class WordDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = {}
def addWord(self, word: str) -> None:
"""
Adds a word into the data structure.
"""
p = self.root
for c in word:
if c not in p:
p[c] = {}
p = p[c]
p['#'] = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
"""
def helper(root, start):
p = root
for i in range(start, len(word)):
c = word[i]
if c != '.':
if c not in p: return False
p = p[c]
else:
for letter in string.ascii_letters:
if letter not in p: continue
if helper(p[letter], i + 1):
return True
return False
return '#' in p
return helper(self.root, 0)
Word Search
这个 dfs 的题目卡了我很久....还是 dfs 没有总结,这个代码写得很乱,,,有时间得重做一下,,我用了一个回溯去做
但是看到下一题的大佬的代码以后,知道自己写得就是一坨屎...
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if len(board) == 0 or len(word) == 0: return False
m, n = len(board), len(board[0])
dirs = [(1, 0), (0, -1), (0, 1), (-1, 0)]
def pos2idx(x, y):
return x * n + y
def dfs(x, y, idx):
if idx == len(word): return True
if x < 0 or y < 0 or x >= m or y >= n: return False
if board[x][y] != word[idx]: return False
idx1 = pos2idx(x, y)
if idx1 in self.visited: return False
self.visited.add(idx1)
for dx, dy in dirs:
if dfs(x+dx, y+dy, idx+1):
return True
self.visited.remove(idx1)
return False
self.visited = set()
for x in range(m):
for y in range(n):
if board[x][y] != word[0]: continue
idx = pos2idx(x, y)
self.visited.add(idx)
for dx, dy in dirs:
if dfs(x+dx, y+dy, 1): return True
self.visited.remove(idx)
return False
好吧...我还是把代码改回来了:
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if len(board) == 0 or len(word) == 0: return False
m, n = len(board), len(board[0])
dirs = [(1, 0), (0, -1), (0, 1), (-1, 0)]
def dfs(x, y, idx, visited):
if idx == len(word): return True
for dx, dy in dirs:
x1, y1 = x + dx, y + dy
if x1 < 0 or x1 >= m or y1 < 0 or y1 >= n: continue
if (x1, y1) in visited: continue
if board[x1][y1] != word[idx]: continue
if dfs(x1, y1, idx + 1, {(x1, y1)} | visited): return True
return False
self.visited = set()
for x in range(m):
for y in range(n):
if board[x][y] != word[0]: continue
if dfs(x, y, 1, {(x, y)}): return True
return False
这样就好看多了..
Word Search II
trie 树的经典题,用 trie 树加速 dfs 搜索
- 根据输入单词建立一个 trie
- 将 trie 在 board 里用 dfs 去搜索
有两个坑的地方:
- 最后不得重复
- 可能出现一个词是另外一个词的前缀,所以找到了这样一个单词以后,不能立即退出,还要继续遍历
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
if len(board) == 0: return None
m, n = len(board), len(board[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
# 建立 trie
trie = {}
for word in words:
node = trie
for char in word:
node = node.setdefault(char, {})
node['#'] = word
def dfs(x, y, node, visited):
if '#' in node: res.add(node['#'])
for dx, dy in dirs:
x1, y1 = x+dx, y+dy
if x1 < 0 or x1 >= m or y1 < 0 or y1 >= n: continue
if (x1, y1) in visited: continue
if board[x1][y1] not in node: continue
dfs(x1, y1, node[board[x1][y1]], visited | {(x1, y1)})
res = set()
for x in range(m):
for y in range(n):
if board[x][y] not in trie: continue
dfs(x, y, trie[board[x][y]], {(x, y)})
return list(res)
Combination Sum IV
背包型动态规划,唉,懵逼了,没想到转移方程
看了答案才知道是一个完全背包问题,背包问题的动态规划我也没总结....
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
# 完全背包问题
# 而且是 可重复使用, 且要注意顺序
# 转移方程:
# dp[x] = dp[x-nums[0]] + dp[x-nums[1]] + ... + dp[x-nums[-1]]
# 一定是可重复使用且注意顺序才能这么用
if len(nums) == 0: return 0
dp = [0] * (target + 1)
dp[0] = 1
for i in range(1, target+1):
for n in nums:
if i < n: continue
dp[i] += dp[i - n]
return dp[target]
网友评论