2696. 删除子串后的字符串最小长度

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 站中转内最便宜的航班

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. 装饰树

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. 二叉树的最近公共祖先

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. 设计浏览器历史记录

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. 数字流的秩

面试题 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)