2707. 字符串中的额外字符
class Solution:
def minExtraChar(self, s: str, dictionary: List[str]) -> int:
dictionary = set(dictionary)
dp = [0 for i in range(len(s) + 1)]
for i in range(1, len(s) + 1):
dp[i] = dp[i - 1] + 1
for j in range(i - 1, -1, -1):
if s[j:i] in dictionary:
dp[i] = min(dp[i], dp[j])
return dp[-1]
841. 钥匙和房间
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
need_enter = {i for i in range(len(rooms))}
have_keys = {0}
while have_keys:
key = have_keys.pop()
if key in need_enter:
need_enter.discard(key)
have_keys.update(set(rooms[key]))
return not bool(need_enter)
1261. 在受污染的二叉树中查找元素
from typing import List, Optional
from tools import treeGenerate
import json
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
from collections import deque
class FindElements:
def __init__(self, root: Optional[TreeNode]):
root.val = 0
self.root = self.recover(root)
def recover(self, node: Optional[TreeNode]):
if node.left:
node.left.val = 2 * node.val + 1
self.recover(node.left)
if node.right:
node.right.val = 2 * node.val + 2
self.recover(node.right)
return node
def find(self, target: int) -> bool:
path = deque()
while target != 0:
path.appendleft(target)
target = (target - 1) // 2
node = self.root
while path:
val = path.popleft()
if node.val * 2 + 1 == val and node.left:
node = node.left
elif node.val * 2 + 2 == val and node.right:
node = node.right
else:
return False
return True
1905. 统计子岛屿
class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
m = len(grid1)
n = len(grid1[0])
not_check_island = set()
for i in range(m):
for j in range(n):
if grid1[i][j] == 0 and grid2[i][j] == 1:
not_check_island.add((i, j))
island = []
for i in range(len(grid2)):
for j in range(len(grid2[i])):
if grid2[i][j] == 1:
island_area = set()
ret = self.dfs(grid2, i, j, island_area, not_check_island)
if ret:
island.append(island_area)
return len(island)
def dfs(self, grid, i, j, island_area: set, not_check_island: set):
if (i, j) in not_check_island:
return False
if grid[i][j] != 1:
return True
island_area.add((i, j))
grid[i][j] = 2
ret = []
for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
if i + x < 0 or i + x >= len(grid) or j + y < 0 or j + y >= len(grid[x]):
continue
ret.append(self.dfs(grid, i + x, j + y, island_area, not_check_island))
return all(ret)
1268. 搜索推荐系统
字典树 + 二分法
import bisect
class Node:
__slots__ = ['char', 'child', 'end_mark', 'child_vals']
def __init__(self, char):
self.char = char
self.child_vals = []
self.child = {}
self.end_mark = False
class DictionaryTree:
def __init__(self):
self.root = Node(None)
def add_word(self, word):
node = self.root
for c in word:
if c in node.child:
node = node.child.get(c)
else:
new = Node(c)
node.child[c] = new
bisect.insort(node.child_vals, c)
node = new
node.end_mark = True
def dfs(self, node: Optional[Node], words: list, chars: list, limit: int):
if node is None:
return
if len(words) >= limit:
return
if not node.child:
words.append(''.join(chars))
return
if node.end_mark:
words.append(''.join(chars))
for k in node.child_vals:
chars.append(k)
self.dfs(node.child[k], words, chars, limit)
chars.pop()
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
dt = DictionaryTree()
for word in products:
dt.add_word(word)
ans = []
node = dt.root
for i, c in enumerate(searchWord, start=1):
if node:
node = node.child.get(c)
candidate_words = []
dt.dfs(node, candidate_words, [searchWord[:i]], 3)
ans.append(candidate_words)
return ans
743. 网络延迟时间
优先队列或使用最短路算法
import heapq
from collections import defaultdict
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
net: Dict[int, list] = defaultdict(list)
nodes = {i + 1 for i in range(n)}
for u, v, w in times:
net[u].append((v, w))
priority_queue = [(0, k)]
t = 0
while priority_queue and nodes:
t, node = heapq.heappop(priority_queue)
nodes.discard(node)
for v, w in net[node]:
if v in nodes:
heapq.heappush(priority_queue, (t + w, v))
if nodes:
return -1
return t
Comments | NOTHING