前言:每天必須寫(xiě),多忙都得寫(xiě),如果我今年 12 月份之前沒(méi)做到 700 道,我會(huì)瞧不起我自己一輩子的
0X00 leetcode 刷題 7 道
0X01 每道題的小小總結(jié)
Reverse Linked List
熱身題, 這道題之前做過(guò),但是第一眼..看過(guò)去沒(méi)思路
其實(shí)就是兩個(gè)前向指針的問(wèn)題, 然后不斷的移動(dòng)
pre 記錄上一個(gè)節(jié)點(diǎn), cur 記錄當(dāng)前節(jié)點(diǎn),temp 記錄 cur.next 然后不斷移動(dòng)
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 有一個(gè)確實(shí)能找到所有在一個(gè)集合里面的點(diǎn)
但是不能,讓這個(gè)集合的所有點(diǎn),都知道某個(gè)點(diǎn)碰到邊界的事情,所以要遍歷完所有集合的值以后,保存下來(lái),統(tǒng)一更新
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 樹(shù),這個(gè)題目做過(guò), 3.3 的時(shí)候好好總結(jié)一下 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 樹(shù)的典型應(yīng)用,不多說(shuō)了
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
這個(gè) dfs 的題目卡了我很久....還是 dfs 沒(méi)有總結(jié),這個(gè)代碼寫(xiě)得很亂,,,有時(shí)間得重做一下,,我用了一個(gè)回溯去做
但是看到下一題的大佬的代碼以后,知道自己寫(xiě)得就是一坨屎...
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
好吧...我還是把代碼改回來(lái)了:
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 樹(shù)的經(jīng)典題,用 trie 樹(shù)加速 dfs 搜索
- 根據(jù)輸入單詞建立一個(gè) trie
- 將 trie 在 board 里用 dfs 去搜索
有兩個(gè)坑的地方:
- 最后不得重復(fù)
- 可能出現(xiàn)一個(gè)詞是另外一個(gè)詞的前綴,所以找到了這樣一個(gè)單詞以后,不能立即退出,還要繼續(xù)遍歷
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
背包型動(dòng)態(tài)規(guī)劃,唉,懵逼了,沒(méi)想到轉(zhuǎn)移方程
看了答案才知道是一個(gè)完全背包問(wèn)題,背包問(wèn)題的動(dòng)態(tài)規(guī)劃我也沒(méi)總結(jié)....
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
# 完全背包問(wèn)題
# 而且是 可重復(fù)使用, 且要注意順序
# 轉(zhuǎn)移方程:
# dp[x] = dp[x-nums[0]] + dp[x-nums[1]] + ... + dp[x-nums[-1]]
# 一定是可重復(fù)使用且注意順序才能這么用
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]
