leetcode weekly contest 334

本场周赛的题目确实不算太难。

2574. 左右元素和的差值

给你一个下标从 0 开始的整数数组 nums ，请你找出一个下标从 0 开始的整数数组 answer ，其中：

answer.length == nums.length
answer[i] = |leftSum[i] - rightSum[i]|
其中：
leftSum[i] 是数组 nums 中下标 i 左侧元素之和。如果不存在对应的元素，leftSum[i] = 0 。
rightSum[i] 是数组 nums 中下标 i 右侧元素之和。如果不存在对应的元素，rightSum[i] = 0 。
返回数组 answer 。

示例 1：

输入：nums = [10,4,8,3]
输出：[15,1,11,22]
解释：数组 leftSum 为 [0,10,14,22] 且数组 rightSum 为 [15,11,3,0] 。
数组 answer 为 [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22] 。

示例 2：

输入：nums = [1]
输出：[0]
解释：数组 leftSum 为 [0] 且数组 rightSum 为 [0] 。
数组 answer 为 [|0 - 0|] = [0] 。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 105

地址

https://leetcode.cn/problems/left-and-right-sum-differences/

题意

直接模拟

思路

简单题目，利用前缀和直接计算即可；
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 为数组的长度。
空间复杂度：$O(n)$。

代码

class Solution {
public:
    vector<int> leftRightDifference(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n + 1);
        vector<int> right(n + 1);
        for(int i = 0; i < n; i++) {
            left[i + 1] = left[i] + nums[i];
        }
        for (int i = n - 1; i >= 0; i--) {
            right[i] = right[i + 1] + nums[i];
        }
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            ans[i] = abs(left[i] - right[i + 1]);
        }
        return ans;
    }
};

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

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

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

如果 word[0,...,i] 所表示的数值能被 m 整除，div[i] = 1
否则，div[i] = 0
返回 word 的可整除数组。

示例 1：

输入：word = "998244353", m = 3
输出：[1,1,0,0,0,1,1,0,0]
解释：仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。

示例 2：

输入：word = "1010", m = 10
输出：[0,1,0,1]
解释：仅有 2 个前缀可以被 10 整除："10" 和 "1010" 。

提示：

1 <= n <= 105
word.length == n
word 由数字 0 到 9 组成
1 <= m <= 109

地址

https://leetcode.cn/problems/find-the-divisibility-array-of-a-string

题意

直接计算

思路

我们直接计算即可，关键问题在于我们不能直接取大数，可以可以编辑算边对计算结果进行取模，这样就可以避免大数计算溢出的问题。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 为字符串的长度。
空间复杂度：$O(n)$，主要为排序需要空间。

代码

class Solution {
public:
    vector<int> divisibilityArray(string word, int m) {
        int n = word.size();
        long long curr = 0;
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            curr = (curr * 10 + word[i] - '0') % m;
            if (curr == 0) {
                ans.emplace_back(1);
            } else {
                ans.emplace_back(0);
            }
        }
        return ans;
    }
};

2576. 求出最多标记下标

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

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

选择两个互不相同且未标记的下标 i 和 j ，满足 2 * nums[i] <= nums[j] ，标记下标 i 和 j 。
请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。

示例 1：

输入：nums = [3,5,2,4]
输出：2
解释：第一次操作中，选择 i = 2 和 j = 1 ，操作可以执行的原因是 2 * nums[2] <= nums[1] ，标记下标 2 和 1 。
没有其他更多可执行的操作，所以答案为 2 。

示例 2：

输入：nums = [9,2,5,4]
输出：4
解释：第一次操作中，选择 i = 3 和 j = 0 ，操作可以执行的原因是 2 * nums[3] <= nums[0] ，标记下标 3 和 0 。
第二次操作中，选择 i = 1 和 j = 2 ，操作可以执行的原因是 2 * nums[1] <= nums[2] ，标记下标 1 和 2 。
没有其他更多可执行的操作，所以答案为 4 。

示例 3：

输入：nums = [7,6,8]
输出：0
解释：没有任何可以执行的操作，所以答案为 0 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109

地址

https://leetcode.cn/problems/find-the-maximum-number-of-marked-indices/

题意

双指针

思路

首先想到的就是要对数组进行排序，只有排序后我们才尽可能的使用贪心算法。我们通过比对发现数组最多只能有 $\frac{n}{2}$ 个配对，因此我们可以尽量使用贪心法：

假设数组存在 $\frac{n}{2}$ 个配对，则一定满足 $nums[i]$ 可以与 $nums[i + \dfrac{n}{2}]$ 一定可以完成配对；
因此我们最优探测法，应该从 $(0, \frac{n}{2})$ 索引开始配对，我们令 $i = 0, j = \frac{n}{2}$：
- 如果 $nums[i] * 2 > nums[j]$，此时我们需要将 $j$ 往右移动;
- 如果 $nums[i] * 2 \le nums[j]$，此时我们需要将 $i,j$ 同时往右移动;

二分法的思路可能更容易理解，假设我们可以找到 $k$ 对配对，则可以知道一定满足最小的 $k$ 个数可以与最大的 $k$ 个数进行配对，否一定无法完成配对，如果题目存在 $k$ 个配对，则一定存在 $k-1$ 个配对；如果题目中无法满足 $k$ 个配对，则一定无法满足 $k+1$ 个配对，满足单调性；
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度。
空间复杂度：$O(\log n)$。

代码

双指针

class Solution {
public:
    int maxNumOfMarkedIndices(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = 0, j = n / 2; i < n / 2 && j < n; i++) {
            while (j < n && nums[j] < nums[i] * 2) {
                j++;
            }
            if (j < n) {
                ans += 2;
                j++;
            }
        }
        return ans;
    }
};

二分查找

class Solution {
public:
    int maxNumOfMarkedIndices(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        auto check = [&](int k)-> bool {
            for (int i = 0; i < k; i++) {
                if (nums[i] * 2 > nums[n - k + i]) {
                    return false;
                }
            }
            return true;
        };
        int L = 0, R = n / 2;
        int ans = 0;
        while (L <= R) {
            int mid = L + (R - L) / 2;
            if (check(mid)) {
                ans = mid * 2;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return ans;
    }
};

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

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

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

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

示例 1：

输入：grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
输出：7
解释：一条可行的路径为：
- 时刻 t = 0 ，我们在格子 (0,0) 。
- 时刻 t = 1 ，我们移动到格子 (0,1) ，可以移动的原因是 grid[0][1] <= 1 。
- 时刻 t = 2 ，我们移动到格子 (1,1) ，可以移动的原因是 grid[1][1] <= 2 。
- 时刻 t = 3 ，我们移动到格子 (1,2) ，可以移动的原因是 grid[1][2] <= 3 。
- 时刻 t = 4 ，我们移动到格子 (1,1) ，可以移动的原因是 grid[1][1] <= 4 。
- 时刻 t = 5 ，我们移动到格子 (1,2) ，可以移动的原因是 grid[1][2] <= 5 。
- 时刻 t = 6 ，我们移动到格子 (1,3) ，可以移动的原因是 grid[1][3] <= 6 。
- 时刻 t = 7 ，我们移动到格子 (2,3) ，可以移动的原因是 grid[2][3] <= 7 。
最终到达时刻为 7 。这是最早可以到达的时间。

示例 2：

输入：grid = [[0,2,4],[3,2,1],[1,0,4]]
输出：-1
解释：没法从左上角按题目规定走到右下角。

提示：

m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 105
0 <= grid[i][j] <= 105
grid[0][0] == 0

地址

https://leetcode.cn/problems/minimum-time-to-visit-a-cell-in-a-grid/

题意

dijistra

思路

题目要求求出到达终点的最早时间，实际上假如我们知道每个格子的最早到达时间，则相应的我们即可求出终点的最早到达时间。思考如下：

如果我们到达格子 $(i,j)$ 的最早时间为 $t$，则其到达 $(i,j + 1)$ 的最早时间是多少呢？分类讨论如下：
- 假设 $t + 1 \ge grid[i][j + 1]$，即 $t + 1$ 满足 $(i, j + 1)$ 最早到达时间，此时我们可以认为 $(i, j + 1)$ 的最早到达时间为可能为 $t + 1$；
- 假设 $t + 1 < grid[i][j + 1]$，即 $t + 1$ 无法满足 $(i, j + 1)$ 最早到达时间，我们可以退一个格子然后再跳回到 $(i, j + 1)$，直到满足 $grid[i][j + 1]$ 的要求，此时我们思考一下，最少需要跳的步数为 $step = grid[i][j + 1] - t$，由于每次来回跳需要的步数总是偶数，如果 $step$ 为奇数的话，我们可以来回跳 $step - 1$ 步，最后在 $step$ 步从 $(i, j)$ 跳到 $(i, j + 1)$，如果 $step$ 为偶数的话，我们可以来回跳 $step$ 步，然后在 $step + 1$ 从 $(i, j)$ 跳到 $(i, j + 1)$。

为了快速计算，我们用 $dijistra$ 算法，这样就使得最早的步骤先进行计算，即可快速的得到每个格子的最早达到步数。
复杂度分析：

时间复杂度：$O(m \times n \times \log (mn))$，其中 $m,n$ 为字符串的长度。
空间复杂度：$O(mn)$。

代码

class Solution {
public:
    int minimumTime(vector<vector<int>>& grid) {
        if (grid[0][1] > 1 && grid[1][0] > 1) {
            return -1;
        }

        typedef tuple<int, int, int> Node;
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
        priority_queue<Node, vector<Node>, greater<Node>> pq;
        int dir[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
        pq.emplace(0, 0, 0);
        dp[0][0] = 0;
        while (!pq.empty()) {
            auto [time, x, y] = pq.top();
            pq.pop();
            if (x == m - 1 && y == n - 1) {
                return time;
            }
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
                if (nx >= 0 && ny >= 0 && nx < m && ny < n && time + 1 < dp[nx][ny]) {
                    if (time + 1 >= grid[nx][ny]) {
                        dp[nx][ny] = time + 1;
                        pq.emplace(time + 1, nx, ny);
                    } else {
                        int step = grid[nx][ny] + ((grid[nx][ny] - time) % 2 == 0 ? 1 : 0);
                        dp[nx][ny] = step;
                        pq.emplace(step, nx, ny);
                    }
                }
            }
        }
        return -1;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛题解

← leetcode weekly contest 333 leetcode weekly biweekly contest 99 →

扫描二维码，分享此文章