本周学习情况

主要是在上课，但也保证了每日一题打卡，并额外刷了十道左右的 Medium+ 题。

下周计划刷一些洛谷的题目，其题设更接近真实工作时的环境。

课程笔记暂不更新，基本第一周的课都没有太多要记的。

周赛

10 分钟做出了两题，第二题 WA 一发。

第三题直到最后一秒才做出来，可惜提交时刚好12点整，通过了但是不算分。

最后 1600 名左右，又要掉分了，离 1880 又远了一些。

P1 6369. 左右元素和的差值

没啥说的

class Solution:
    def leftRigthDifference(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [abs(sum(nums[:idx]) - sum(nums[idx + 1:])) for idx in range(n)]
        return ans

P2 6368. 找出字符串的可整除数组

直接转换成整型或者累加数字都会溢出，要利用模运算的性质，防止溢出。

class Solution:
    def divisibilityArray(self, word: str, m: int) -> List[int]:
        div = []
        n = len(word)
        cur = 0
        for i in range(n):
            cur *= 10
            cur += int(word[i])
            cur %= m
            if cur == 0:
                div.append(1)
            else:
                div.append(0)
        return div

P3 6367. 求出最多标记下标

理论上要有严格数学证明，我是猜出来的……

直接将数组排序后一分为二，双指针逐个匹配即可。

class Solution:
    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0
        l, r = 0, (len(nums) >> 1) - 1
        while l < (len(nums) >> 1) and r < len(nums):
            if nums[l] * 2 <= nums[r]:
                ans += 2
                l += 1
                r += 1
            else:
                r += 1
        return ans

P4 6366. 在网格图中访问一个格子的最少时间

看题解才会的。主要思路是二分，见注释。

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        '''
        如果在时间 end_time 可以到达终点
        那么在更长的时间内也一定可以到达
        具有单调性，因此可以二分查找答案
        '''
        m, n = len(grid), len(grid[0])
        # 无法走出起始单元格
        if grid[0][1] > 1 and grid[1][0] > 1:
            return -1
        '''
        vis 用于记录当前单元格是否已经遍历过
        用当前正在 check 的 end_time 作为标记
        ''' 
        vis = [[-inf] * n for _ in range(m)]
        start_time = inf

        def check(end_time):
            # q 存储的是等待被遍历其周围单元格的单元格（本身已经遍历过）
            q = [(m - 1, n - 1)]
            vis[-1][-1] = end_time
            t = end_time
            while q:
                t -= 1
                tmp = q
                q = []
                for i, j in tmp:
                    # 遍历上下左右四个格子
                    for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):
                        # 如果行列号合法，也未被访问，且时间小于等于当前时间，说明可以被合法访问
                        if 0 <= x < m and 0 <= y < n and vis[x][y] != end_time and grid[x][y] <= t:
                            if x == 0 and y == 0:
                                nonlocal start_time
                                start_time = min(start_time, t)
                                return True
                            # 将当前单元格标记为已访问
                            vis[x][y] = end_time
                            # 将其入队，等待遍历其周围单元格
                            q.append((x, y))
            return False

        # 上下界均为开区间
        left = max(grid[-1][-1], m + n - 2) - 1
        right = max(map(max, grid)) + m + n

        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid
        return right + start_time % 2