1029. 两地调度

1029. 两地调度

from typing import List


class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key=lambda x: x[0] - x[1])
        a = 0
        b = 0
        for i in range(len(costs) // 2):
            a += costs[i][0]
        for i in range(len(costs) // 2, len(costs)):
            b += costs[i][1]
        return a + b

951. 翻转等价二叉树

951. 翻转等价二叉树

from typing import Optional
from collections import deque
# Definition for a binary tree node.


class Solution:
    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        if not root1 and not root2:
            return True
        if not root1 or not root2:
            return False
        queue1 = deque([root1])
        queue2 = deque([root2])
        while queue1 and queue2:
            val1 = queue1.popleft()
            val2 = queue2.popleft()
            if val1 is None and val2 is None:
                continue
            if not all([val2, val1]):
                return False
            if val1.val != val2.val:
                return False
            queue1.extend(self.get_sorted_child(val1))
            queue2.extend(self.get_sorted_child(val2))
        if queue1 or queue2:
            return False
        return True

    def get_sorted_child(self, root: Optional[TreeNode]):
        if root is None:
            return []
        if root.right is None and root.left is None:
            return [None, None]
        elif root.right is None:
            return [root.left, None]
        elif root.left is None:
            return [root.right, None]
        else:
            return sorted([root.right, root.left], key=lambda x: x.val)

1752. 检查数组是否经排序和轮转得到

1752. 检查数组是否经排序和轮转得到

class Solution:
    def check(self, nums: List[int]) -> bool:
        times = 0
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                times += 1
        if times == 1 and nums[-1] <= nums[0] or times == 0:
            return True
        return False

646. 最长数对链

646. 最长数对链

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort()
        dp = [1 for i in range(len(pairs))]
        for i in range(len(pairs)):
            for j in range(i):
                if pairs[j][1] < pairs[i][0]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return dp[-1]