735. 小行星碰撞

735. 小行星碰撞

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = [asteroids[0]]
        for i in range(1, len(asteroids)):
            if stack and stack[-1] < 0:
                stack.append(asteroids[i])
            elif stack and asteroids[i] < 0:
                while stack and -asteroids[i] > stack[-1] > 0:
                    stack.pop()
                if stack and -asteroids[i] == stack[-1]:
                    stack.pop()
                    continue
                if stack and -asteroids[i] < stack[-1]:
                    continue
                stack.append(asteroids[i])
            else:
                stack.append(asteroids[i])
        return stack

895. 最大频率栈

895. 最大频率栈

优先队列，时间复杂度$O(nlogn)$；题解将栈序列分解成为多个频率不同的栈序列，时间复杂度$O(1)$。

from collections import defaultdict
from typing import Dict
import heapq


class FreqStack:
    def __init__(self):
        self.frequency: Dict[int, int] = defaultdict(int)
        self.heap = []
        self.index = 0

    def push(self, val: int) -> None:
        self.frequency[val] += 1
        self.index -= 1
        heapq.heappush(self.heap, (-self.frequency[val], self.index, val))

    def pop(self) -> int:
        freq, index, val = heapq.heappop(self.heap)
        self.frequency[val] -= 1
        return val

1319. 连通网络的操作次数

1319. 连通网络的操作次数

深度优先搜索，还可使用并查集

from typing import List, Dict
from collections import defaultdict


class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1
        conn: Dict[int, list] = defaultdict(list)
        for src, dst in connections:
            conn[src].append(dst)
            conn[dst].append(src)
        checked = set()
        ans = 0
        for i in range(n):
            if i not in checked:
                self.dfs(conn, i, checked)
                ans += 1
        return ans - 1

    def dfs(self, conn, start, checked):
        checked.add(start)
        for computer in conn[start]:
            if computer in checked:
                continue
            self.dfs(conn, computer, checked)

LCR 066. 键值映射

LCR 066. 键值映射

字典树

class Node:
    __slots__ = ["child", 'char', 'val']
    
    def __init__(self, c, val=0):
        self.child = {}
        self.char = c
        self.val = val


class MapSum:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.tree = Node(None)

    def insert(self, key: str, val: int) -> None:
        node = self.tree
        for c in key:
            if c in node.child:
                node = node.child[c]
            else:
                new_node = Node(c)
                node.child[c] = new_node
                node = new_node
        node.val = val

    def sum(self, prefix: str) -> int:
        node = self.tree
        for c in prefix:
            if c not in node.child:
                return 0
            node = node.child[c]
        return self.dfs(node)

    def dfs(self, node):
        ret = node.val
        for char, child_node in node.child.items():
            ret += self.dfs(child_node)
        return ret

684. 冗余连接

684. 冗余连接

class UnionFindSet:
    def __init__(self):
        self.parent = {}

    def find(self, x):
        if x not in self.parent:
            self.parent[x] = x
        elif self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        self.parent[root_x] = root_y
        return True


class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        uf = UnionFindSet()
        for x, y in edges:
            if not uf.union(x, y):
                return [x, y]