Leetcode 344场周赛

Q1 6369. 左右元素和的差值 - 力扣（Leetcode） [Easy] 题解

Q2 6368. 找出字符串的可整除数组 - 力扣（Leetcode） [Medium] 题解

Q3 6367. 求出最多标记下标 - 力扣（Leetcode） [Medium] 题解

Q4 6366. 在网格图中访问一个格子的最少时间 - 力扣（Leetcode） [Hard] 题解

Q1

6369. 左右元素和的差值 - 力扣（Leetcode）

求出数组中每个数左边所有数和右边所有数的差的绝对值。

思路

遍历模拟，可以用前缀和加快处理。

代码

class Solution:
    def leftRigthDifference(self, nums: List[int]) -> List[int]:
        n = len(nums)
        l, r = [0]*(n+2), [0]*(n+2)
        for i in range(1, n+1):
            l[i] = l[i-1]+nums[i-1]
        for i in range(n, 0, -1):
            r[i] = r[i+1]+nums[i-1]
        ans = [0]*n
        for i in range(n):
            ans[i] = abs(l[i]-r[i+2])
        return ans

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

Q2

6368. 找出字符串的可整除数组 - 力扣（Leetcode）

给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。

word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：

如果 word[0,...,i] 所表示的数值能被 m 整除，div[i] = 1

否则，div[i] = 0

返回 word 的可整除数组。

思路

从左到右遍历，并维持word[0,…i]的和。

在求和过程中，把每次求出的和对m取模，这样不会影响判断。

当和为0，说明可以整除。

代码

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

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

Q3

6367. 求出最多标记下标 - 力扣（Leetcode）

给你一个下标从 0 开始的整数数组 nums 。

一开始，所有下标都没有被标记。你可以执行以下操作任意次：

选择两个 互不相同且未标记 的下标 i 和 j ，满足 2 * nums[i] <= nums[j] ，标记下标 i 和 j 。

请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。

思路

首先这题所求i和j并没有位置约束，所以可以先对数组排序。
贪心思考。假设可以标记 2 * m 个下标（标记成对出现），那么选择前m个最小的数，和后m个最大的数是最优的。
如果可以标记k对，那么一定可以标记k-1对。从k对中任意删去一对即可。二分答案。

代码

class Solution {
    boolean ck(int[] nums, int t, int n){
        for (int i = 0;i < t;i++){
            if (nums[i]*2 > nums[n-t+i]) return false;
        }return true;
    }
    public int maxNumOfMarkedIndices(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int l = 0, r = n/2;
        while (l <= r){
            int m = l+r >> 1;
            if (ck(nums, m, n)) l = m+1;
            else r = m-1;
        }return r*2;
    }
}

复杂度分析

时间复杂度：O(nlog n)。
空间复杂度：O(1)

Q4

6366. 在网格图中访问一个格子的最少时间 - 力扣（Leetcode）

给你一个 m x n 的矩阵 grid ，每个元素都为非负整数，其中 grid[row][col] 表示可以访问格子 (row, col) 的最早时间。也就是说当你访问格子 (row, col) 时，最少已经经过的时间为 grid[row][col] 。

你从 最左上角 出发，出发时刻为 0 ，你必须一直移动到上下左右相邻四个格子中的任意一个格子（即不能停留在格子上）。每次移动都需要花费 1 单位时间。

请你返回最早到达右下角格子的时间，如果你无法到达右下角的格子，请你返回 -1 。

思路

不考虑grid限制，就是一个BFS最短路。
考虑grid限制，在BFS转移时有三种情况：

大于等于最少经过时间，直接在原时间上+1
最少经过时间与当前时间同奇偶，转移后时间为最少经过时间+1
最少经过时间与当前时间同奇偶，转移后时间为最少经过时间

这样BFS每走一步时间不一定只增加1，所以需要用优先队列来获得当前最短的时间

代码

class Solution {
    public int minimumTime(int[][] g) {
        if (g[0][1]>1 && g[1][0]>1) return -1;
        int n = g.length, m = g[0].length;
        boolean[][] v = new boolean[n][m];
        int[] dx={0,0,-1,1}, dy={1,-1,0,0};
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (x, y) -> x[2]-y[2]
        );
        pq.add(new int[]{0, 0, 0});
        while (!pq.isEmpty()){
            int[] cur = pq.poll();
            int x = cur[0], y = cur[1], c = cur[2];
            if (x == n-1 && y == m-1) return c;
            if (v[x][y]) continue;
            v[x][y] = true;
            for (int k = 0;k < 4;k++){
                int nx = x+dx[k], ny = y+dy[k];
                if (nx<0||ny<0||nx>=n||ny>=m) continue;
                if (c+1 >= g[nx][ny]){
                    pq.add(new int[]{nx, ny, c+1});
                }else if (g[nx][ny]%2 == c%2){
                    pq.add(new int[]{nx, ny, g[nx][ny]+1});
                }else{
                    pq.add(new int[]{nx, ny, g[nx][ny]});
                }
            }
        }return -1;
    }
}

复杂度分析

时间复杂度：O(nmlog nm)
空间复杂度：O(nm)