2008. 出租车的最大盈利

2008. 出租车的最大盈利

import bisect


class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        rides.sort(key=lambda x: x[1])
        dp = [[0, 0]]
        ans = 0
        for start, end, tip in rides:
            if dp[-1][1] != end:
                dp.append([dp[-1][0], end])
            index = bisect.bisect_right(dp, start, key=lambda x: x[1])
            dp[-1][0] = max(dp[-1][0], dp[index - 1][0] + end - start + tip)
            if dp[-1][0] > ans:
                ans = dp[-1][0]
        # print(dp)
        return ans

144. 二叉树的前序遍历

144. 二叉树的前序遍历

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        ans = []
        def dfs(node: Optional[TreeNode]):
            ans.append(node.val)
            if node.left:
                dfs(node.left)
            if node.right:
                dfs(node.right)
        dfs(root)
        return ans

LCP 61. 气温变化趋势

LCP 61. 气温变化趋势

class Solution:
    def temperatureTrend(self, temperatureA: List[int], temperatureB: List[int]) -> int:
        ans = 0
        tmp_ans = 0
        for i in range(len(temperatureA) - 1):
            a = temperatureA[i + 1] - temperatureA[i]
            b = temperatureB[i + 1] - temperatureB[i]
            if (a ^ b) >= 0 and a != 0 and b != 0:
                tmp_ans += 1
            elif a == 0 and b == 0:
                tmp_ans += 1
            else:
                tmp_ans = 0
            if ans < tmp_ans:
                ans = tmp_ans
        return ans

740. 删除并获得点数

740. 删除并获得点数

import bisect
from typing import List
from collections import Counter


class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        nums = list(Counter(nums).items())
        nums.sort()
        dp = [[-1, 0]]
        ans = 0
        for i in range(len(nums)):
            index0 = bisect.bisect_right(dp, nums[i][0] - 2, key=lambda x:x[0]) - 1
            index1 = bisect.bisect_right(dp, nums[i][0] - 1, key=lambda x:x[0]) - 1
            dp.append([nums[i][0], max(dp[index0][1] + nums[i][0] * nums[i][1], dp[index1][1])])
            if dp[-1][1] > ans:
                ans = dp[-1][1]
        return ans

1877. 数组中最大数对和的最小值

1877. 数组中最大数对和的最小值

class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        nums.sort()
        ans = float('-inf')
        for i in range(len(nums) // 2):
            ans = max(nums[i] + nums[len(nums) - i - 1], ans)
        return ans