2224. 转化时间需要的最少操作数

2224. 转化时间需要的最少操作数

class Solution:
    def convertTime(self, current: str, correct: str) -> int:
        current = self.to_min(current)
        correct = self.to_min(correct)
        diff = correct - current
        ans = 0
        add_time = [60, 15, 5, 1]
        for i in range(4):
            ans += diff // add_time[i]
            diff = diff % add_time[i]
        return ans

    def to_min(self, t: str):
        t = t.split(':')
        return int(t[0]) * 60 + int(t[1])

2511. 最多可以摧毁的敌人城堡数目

2511. 最多可以摧毁的敌人城堡数目

class Solution:
    def captureForts(self, forts: List[int]) -> int:
        left = None
        right = None
        if len(set(forts)) != 3:
            return 0
        ans = 0
        for i in range(len(forts)):
            if forts[i] == 1 or forts[i] == -1:
                if left is None:
                    left = i
                elif right is None:
                    right = i
                else:
                    left = right
                    right = i
                if left is not None and right is not None and forts[left] != forts[right]:
                    if right - left > ans:
                        ans = right - left
        return ans - 1

1304. 和为零的 N 个不同整数

1304. 和为零的 N 个不同整数

class Solution:
    def sumZero(self, n: int) -> List[int]:
        if n % 2 == 1:
            ans = [i for i in range(-n // 2 + 1, n // 2 + 1)]
        else:
            ans = [i for i in range(-n // 2, 0)] + [i for i in range(1, n // 2 + 1)]
        return ans

1300. 转变数组后最接近目标值的数组和

1300. 转变数组后最接近目标值的数组和

二分法

import bisect


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        prefix = [0]
        for i in range(len(arr)):
            prefix.append(prefix[-1] + arr[i])
        ans = 0
        right = arr[-1]
        diff = target
        for i in range(right + 1):
            pos = bisect.bisect_left(arr, i)
            cur = prefix[pos] + (len(arr) - pos) * i
            if abs(cur - target) < diff:
                diff = abs(cur - target)
                ans = i
        return ans

LCR 091. 粉刷房子

LCR 091. 粉刷房子

动态规划

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        dp = [[0, 0, 0] for i in range(len(costs) + 1)]
        for i in range(len(costs)):
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0]
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1]
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2]
        return min(dp[-2])

518. 零钱兑换 II

518. 零钱兑换 II

递归

from functools import cache

class Solution:
    def __init__(self):
        self.coins = None
    def change(self, amount: int, coins: List[int]) -> int:
        coins.sort()
        self.coins = coins
        return self.recursion(amount, len(coins) - 1)
    
    @cache
    def recursion(self, num, border):
        if border == 0:
            return 1 if num % self.coins[border] == 0 else 0
        ret = 0
        for i in range(0, num + 1, self.coins[border]):
            ret += self.recursion(num - i, border - 1)
        return ret

2096. 从二叉树一个节点到另一个节点每一步的方向

2096. 从二叉树一个节点到另一个节点每一步的方向

广度优先搜索

from collections import deque


class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        father = {root.val: None}
        val_map = {}
        queue = deque([root])
        while queue:
            node = queue.pop()
            val_map[node.val] = node
            if node.right:
                father[node.right.val] = node
                queue.appendleft(node.right)
            if node.left:
                father[node.left.val] = node
                queue.appendleft(node.left)
        startValue2root = [startValue]
        destValue2root = [destValue]
        while father[startValue2root[-1]] is not None or father[destValue2root[-1]] is not None:
            if father[startValue2root[-1]]:
                startValue2root.append(father[startValue2root[-1]].val)
            if father[destValue2root[-1]]:
                destValue2root.append(father[destValue2root[-1]].val)
        tmp = root.val
        while startValue2root and destValue2root and startValue2root[-1] == destValue2root[-1] :
            startValue2root.pop()
            tmp = destValue2root.pop()
        startValue2root.append(tmp)
        path = startValue2root + list(reversed(destValue2root))
        ans = []
        for i in range(0, len(path) - 1):
            ans.append(self.get_relation(val_map[path[i]], val_map[path[i + 1]]))

        return ''.join(ans)


    def get_relation(self, node1, node2):
        if node2.left == node1 or node2.right == node1:
            return 'U'
        if node1.left == node2:
            return 'L'
        if node1.right == node2:
            return 'R'