2696. 删除子串后的字符串最小长度
class Solution:
def minLength(self, s: str) -> int:
while True:
tmp_s = s
s = s.replace('AB', '').replace('CD', '')
if tmp_s == s:
break
return len(s)
787. K 站中转内最便宜的航班
from typing import List, Dict
from collections import defaultdict
import heapq
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
edges = flights
flights: Dict[int, list] = defaultdict(list)
for s, d, c in edges:
flights[s].append((c, d))
priority_queue = [(0, src, 0, [])]
arrived_airport = set()
while priority_queue:
cost, airport, transfer_cnt, path = heapq.heappop(priority_queue)
arrived_airport.add(airport)
if airport == dst:
return cost
if transfer_cnt == k + 1:
for item in path:
arrived_airport.discard(item)
continue
for c, d in flights[airport]:
if d in arrived_airport:
continue
path.append(d)
heapq.heappush(priority_queue, (cost + c, d, transfer_cnt + 1, path[:]))
path.pop()
return -1
LCP 67. 装饰树
class Solution:
def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
self.dfs(root)
return root
def dfs(self, node: Optional[TreeNode]):
if node.left:
insert_node = TreeNode(-1)
insert_node.left = node.left
node.left = insert_node
self.dfs(insert_node.left)
if node.right:
insert_node = TreeNode(-1)
insert_node.right = node.right
node.right = insert_node
self.dfs(insert_node.right)
236. 二叉树的最近公共祖先
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
p_path = []
self.dfs(root, p, p_path)
q_path = []
self.dfs(root, q, q_path)
index = 0
while index < len(p_path) and index < len(q_path):
if p_path[index].val != q_path[index].val:
return p_path[index - 1]
index += 1
return p_path[-1] if len(p_path) < len(q_path) else q_path[-1]
def dfs(self, node, search_node, path: list):
if node.val == search_node.val:
path.append(node)
return True
path.append(node)
if node.left and self.dfs(node.left, search_node, path):
return True
if node.right and self.dfs(node.right, search_node, path):
return True
path.pop()
return False
1472. 设计浏览器历史记录
对顶栈
from collections import deque
class BrowserHistory:
def __init__(self, homepage: str):
self.stack_before = deque([homepage])
self.stack_after = deque()
def visit(self, url: str) -> None:
self.stack_before.append(url)
self.stack_after.clear()
def back(self, steps: int) -> str:
for i in range(steps):
if len(self.stack_before) == 1:
break
self.stack_after.appendleft(self.stack_before.pop())
return self.stack_before[-1]
def forward(self, steps: int) -> str:
for i in range(steps):
if not self.stack_after:
break
self.stack_before.append(self.stack_after.popleft())
return self.stack_before[-1]
面试题 10.10. 数字流的秩
import bisect
class StreamRank:
def __init__(self):
self.stream = []
def track(self, x: int) -> None:
bisect.insort(self.stream, x)
def getRankOfNumber(self, x: int) -> int:
return bisect.bisect_right(self.stream, x)
Comments | NOTHING