算法题记录 28

3340.检查平衡字符串（1172）

给你一个仅由数字 0 - 9 组成的字符串 num。如果偶数下标处的数字之和等于奇数下标处的数字之和，则认为该数字字符串是一个 平衡字符串。

如果 num 是一个 平衡字符串，则返回 true；否则，返回 false。

涉及知识点

字符串

解决思路

送分题

class Solution:
    def isBalanced(self, num: str) -> bool:
        flag=0
        sum1=0
        sum2=0
        for i in range(len(num)):
            if flag==0:
                sum1+=int(num[i])
                flag=1
            else:
                sum2+=int(num[i])
                flag=0
        return True if sum1==sum2 else False

855.考场就座（2067）

在考场里，有 n 个座位排成一行，编号为 0 到 n - 1。

当学生进入考场后，他必须坐在离最近的人最远的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)

设计一个模拟所述考场的类。

实现 ExamRoom 类：

ExamRoom(int n) 用座位的数量 n 初始化考场对象。
int seat() 返回下一个学生将会入座的座位编号。
void leave(int p) 指定坐在座位 p 的学生将离开教室。保证座位 p 上会有一位学生。

涉及知识点

有序集合、哈希表

解决思路

首先很显然，当0为空时我们可能坐在0处，最后位置为空时亦然。但是对于中间的位置，我们只能坐在两个邻居的中间，即(left+right)/2的地方。那我们就有了距离的计算方式。用一个有序集合sortedlist，根据距离进行从大到小排序，优先入座距离远的地方。但是我们怎么知道left、right是什么呢？因此我们不仅要记录距离，更要以区间的形式进行记录。这样当我们入座时，有序集合就会多被分割出一个区间。当离开座位时，我们用两个哈希表left、right提前记录每个有人的位置的左右邻居，我们就可以把left,p和p,right合并为left,right了，对两个哈希表、有序集合进行更新即可。

from sortedcontainers import SortedList


class ExamRoom:
    def __init__(self, n: int):
        def dist(x):
            l, r = x
            return r - l - 1 if l == -1 or r == n else (r - l) >> 1

        self.n = n
        self.ts = SortedList(key=lambda x: (-dist(x), x[0]))
        self.left = {}
        self.right = {}
        self.add((-1, n))

    def seat(self) -> int:
        s = self.ts[0]
        p = (s[0] + s[1]) >> 1
        if s[0] == -1:
            p = 0
        elif s[1] == self.n:
            p = self.n - 1
        self.delete(s)
        self.add((s[0], p))
        self.add((p, s[1]))
        return p

    def leave(self, p: int) -> None:
        l, r = self.left[p], self.right[p]
        self.delete((l, p))
        self.delete((p, r))
        self.add((l, r))

    def add(self, s):
        self.ts.add(s)
        self.left[s[1]] = s[0]
        self.right[s[0]] = s[1]

    def delete(self, s):
        self.ts.remove(s)
        self.left.pop(s[1])
        self.right.pop(s[0])

3250.单调数组对的数目1（1898）

给你一个长度为 n 的 正 整数数组 nums 。

如果两个 非负 整数数组 (arr1, arr2) 满足以下条件，我们称它们是 单调 数组对：

两个数组的长度都是 n 。
arr1 是单调 非递减 的，换句话说 arr1[0] <= arr1[1] <= … <= arr1[n - 1] 。
arr2 是单调 非递增 的，换句话说 arr2[0] >= arr2[1] >= … >= arr2[n - 1] 。
对于所有的 0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。
请你返回所有 单调 数组对的数目。

由于答案可能很大，请你将它对 10^9 + 7 取余 后返回。

涉及知识点

动态规划

解决思路

跟之前的一道题一样。

class Solution:
    def countOfPairs(self, nums: List[int]) -> int:
        MOD = 1_000_000_007
        n = len(nums)
        m = max(nums)
        f = [[0] * (m + 1) for _ in range(n)]
        for j in range(nums[0] + 1):
            f[0][j] = 1
        for i in range(1, n):
            s = list(accumulate(f[i - 1]))  # f[i-1] 的前缀和
            for j in range(nums[i] + 1):
                max_k = j + min(nums[i - 1] - nums[i], 0)
                f[i][j] = s[max_k] % MOD if max_k >= 0 else 0
        return sum(f[-1][:nums[-1] + 1]) % MOD

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。