2645. 构造有效字符串的最少插入数

2645. 构造有效字符串的最少插入数

class Solution:
    def addMinimum(self, word: str) -> int:
        res = ord(word[0]) - ord(word[-1]) + 2
        for i in range(1, len(word)):
            res += (ord(word[i]) - ord(word[i - 1]) + 2) % 3
        return res

1020. 飞地的数量

1020. 飞地的数量

from typing import List


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

    def find(self, val):
        if val not in self.father:
            self.father[val] = val
        if self.father[val] != val:
            self.father[val] = self.find(self.father[val])
        return self.father[val]

    def union(self, val1, val2):
        root_val1 = self.find(val1)
        root_val2 = self.find(val2)
        self.father[root_val2] = root_val1


class Solution:
    def __init__(self):
        self.direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    def numEnclaves(self, grid: List[List[int]]) -> int:
        uf = UnionFindSet()
        for i in (0, len(grid) - 1):
            for j in range(len(grid[i])):
                self.set_zero(grid, i, j)
        for i in range(len(grid)):
            for j in (0, len(grid[i]) - 1):
                self.set_zero(grid, i, j)
        for i in range(1, len(grid) - 1):
            for j in range(1, len(grid[i]) - 1):
                if grid[i][j] == 1:
                    uf.find((i, j))
                    grid[i][j] = 2
                    for x, y in self.direction:
                        if grid[i + x][j + y] == 1:
                            uf.union((i, j), (i + x, j + y))

        return len(uf.father)

    def set_zero(self, grid, x, y):
        if grid[x][y] == 0:
            return
        grid[x][y] = 0
        for i, j in self.direction:
            if x + i < 0 or x + i >= len(grid) or y + j < 0 or y + j >= len(grid[x + i]):
                continue
            self.set_zero(grid, x + i, y + j)

1559. 二维网格图中探测环

1559. 二维网格图中探测环

from typing import List


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

    def find(self, val):
        if val not in self.father:
            self.father[val] = val
        if self.father[val] != val:
            self.father[val] = self.find(self.father[val])
        return self.father[val]

    def union(self, val1, val2):
        root_val1 = self.find(val1)
        root_val2 = self.find(val2)
        if root_val1 == root_val2:
            return True
        self.father[root_val1] = self.find(root_val2)
        return False


class Solution:
    def __init__(self):
        self.direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    def containsCycle(self, grid: List[List[str]]) -> bool:
        uf = UnionFindSet()
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                uf.find((i, j))
                for x, y in self.direction:
                    if i + x < 0 or i + x >= len(grid) or j + y < 0 or j + y >= len(grid[i + x]):
                        continue
                    if grid[i][j] == grid[i + x][j + y]:
                        if uf.union((i, j), (i + x, j + y)):
                            return True
                grid[i][j] = ''
        return False

2241. 设计一个 ATM 机器

2241. 设计一个 ATM 机器

from typing import List


class ATM:
    def __init__(self):
        self.moneys = [0, 0, 0, 0, 0]
        self.pos = {20: 0, 50: 1, 100: 2, 200: 3, 500: 4}
        self.order = {0: 20, 1: 50, 2: 100, 3: 200, 4: 500}

    def deposit(self, banknotesCount: List[int]) -> None:
        for i, count in enumerate(banknotesCount):
            self.moneys[i] += count


    def withdraw(self, amount: int) -> List[int]:
        ans = [0, 0, 0, 0, 0]
        for i in range(len(self.moneys) - 1, -1, -1):
            ans[i] += amount // self.order[i] if (amount // self.order[i]) <= self.moneys[i] else self.moneys[i]
            self.moneys[i] -= ans[i]
            amount -= ans[i] * self.order[i]
        if amount:
            self.deposit(ans)
            return [-1]
        return ans

1381. 设计一个支持增量操作的栈

1381. 设计一个支持增量操作的栈

class CustomStack:
    def __init__(self, maxSize: int):
        self.stack = []
        self.max_size = maxSize
        self.top = 0

    def push(self, x: int) -> None:
        if len(self.stack) == self.max_size:
            return
        self.stack.append(x - self.top)
        self.top += self.stack[-1]

    def pop(self) -> int:
        if not self.stack:
            return -1
        ans = self.top
        self.top -= self.stack.pop()
        return ans

    def increment(self, k: int, val: int) -> None:
        if not self.stack:
            return 
        self.stack[0] += val
        if k < len(self.stack):
            self.stack[k] -= val
        else:
            self.top += val

1305. 两棵二叉搜索树中的所有元素

1305. 两棵二叉搜索树中的所有元素

生成器

class Solution:
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        tree1 = self.dfs(root1)
        tree2 = self.dfs(root2)
        tree1_val = next(tree1, None)
        tree2_val = next(tree2, None)
        ans = []
        while tree1_val is not None or tree2_val is not None:
            if tree1_val is None:
                ans.append(tree2_val)
                tree2_val = next(tree2, None)
            elif tree2_val is None:
                ans.append(tree1_val)
                tree1_val = next(tree1, None)
            elif tree1_val < tree2_val:
                ans.append(tree1_val)
                tree1_val = next(tree1, None)
            else:
                ans.append(tree2_val)
                tree2_val = next(tree2, None)
        return ans

    def dfs(self, node: TreeNode):
        if node is None:
            return
        if node.left:
            yield from self.dfs(node.left)
        yield node.val
        if node.right:
            yield from self.dfs(node.right)