283. 移动零

283. 移动零

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        p0 = 0
        for i in range(1, len(nums)):
            while nums[p0] != 0 and p0 < i:
                p0 += 1
            if nums[p0] == 0 and nums[i] != 0:
                nums[p0], nums[i] = nums[i], nums[p0]

2848. 与车相交的点

2848. 与车相交的点

差分数组

from itertools import accumulate

class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        nums.sort(key=lambda x: x[1])
        diff = [0 for i in range(nums[-1][-1] + 2)]
        for s, e in nums:
            diff[s] += 1
            diff[e + 1] -= 1
        return sum(s > 0 for s in accumulate(diff))

1094. 拼车

1094. 拼车

差分数组

from itertools import accumulate


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trips.sort(key=lambda x: x[-1])
        diff = [0] * (trips[-1][-1] + 2)
        for i in range(len(trips)):
            diff[trips[i][1]] += trips[i][0]
            diff[trips[i][2]] -= trips[i][0]
        for i in accumulate(diff):
            if i > capacity:
                return False
        return True

1109. 航班预订统计

1109. 航班预订统计

差分数组

from itertools import accumulate


class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0] * (n + 2)
        for i in range(len(bookings)):
            diff[bookings[i][0]] += bookings[i][2]
            diff[bookings[i][1] + 1] -= bookings[i][2]
        return [i for i in accumulate(diff)][1:-1]

2381. 字母移位 II

2381. 字母移位 II

差分数组

from itertools import accumulate


class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        diff = [0] * (len(s) + 1)
        ans = [''] * len(s)
        for i in range(len(shifts)):
            diff[shifts[i][0]] += shifts[i][2] if shifts[i][2] == 1 else -1
            diff[shifts[i][1] + 1] -= shifts[i][2] if shifts[i][2] == 1 else -1
        for i, v in enumerate(accumulate(diff[:-1])):
            ans[i] = chr(((ord(s[i]) + v) - 97) % 26 + 97)
        return ''.join(ans)

230. 二叉搜索树中第K小的元素

230. 二叉搜索树中第K小的元素

注意是二叉搜索树，可以直接使用中序遍历，这里使用堆排序，因为没注意到是二叉搜索树。

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        ans = root.val
        for i in range(k):
            self.heapify(root)
            ans = root.val
            root.val = float('inf')
        return ans

    def heapify(self, root: Optional[TreeNode]):
        if root.left is None and root.right is None:
            return
        if root.left:
            self.heapify(root.left)
        if root.right:
            self.heapify(root.right)

        if root.left and root.right:
            if root.left.val < root.val and root.left.val < root.right.val:
                root.val, root.left.val = root.left.val, root.val
            elif root.right.val < root.val and root.right.val < root.left.val:
                root.val, root.right.val = root.right.val, root.val
        elif root.right:
            if root.right.val < root.val:
                root.val, root.right.val = root.right.val, root.val
        elif root.left:
            if root.left.val < root.val:
                root.val, root.left.val = root.left.val, root.val

754. 到达终点数字

754. 到达终点数字

找到第一个使 sum = 1 + 2 + ... + k >= target 且 sum - target 为偶数的 k，k即为答案。

class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)
        ans = 0
        total = 0
        while True:
            ans += 1
            total += ans
            if total >= target and (total - target) % 2 == 0:
                break
        return ans

731. 我的日程安排表 II

731. 我的日程安排表 II

遍历

class MyCalendarTwo:
    def __init__(self):
        self.single = []
        self.double = []

    def book(self, start: int, end: int) -> bool:
        for i in range(len(self.double)):
            if start < self.double[i][1] and self.double[i][0] < end:
                return False
        for i in range(len(self.single)):
            if start < self.single[i][1] and self.single[i][0] < end:
                self.double.append([max(start, self.single[i][0]), min(end, self.single[i][1])])
        self.single.append([start, end])
        return True