第 334 场周赛

Date: 2023-02-26

A 左右元素和的差值

直接暴力

C++Python

class Solution {
public:
    vector<int> leftRigthDifference(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        int l = 0, r = accumulate(nums.begin(), nums.end(), 0);
        for (int i = 0; i < n; i++) {
            r -= nums[i];
            res[i] = abs(l - r);
            l += nums[i];
        }
        return res;
    }
};

class Solution:
    def leftRigthDifference(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n
        l, r = 0, sum(nums)
        for i, x in enumerate(nums):
            r -= x
            res[i] = abs(r - l)
            l += x
        return res

复杂度分析

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

B 找出字符串的可整除数组

根据模数的性质，\((x * 10 + y) \mod p = ((x \mod p) * 10 + y) \mod p\)。因此，维护前缀模数，然后递推即可。

C++

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

复杂度分析

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

C 求出最多标记下标

首先对所有数字排个序，然后考虑到最终答案不会超过 \(n / 2\)，因此假设答案是 \(m\)，那么应该是最小的 \(m\) 个数字和剩下比较大的 \(n - m\) 个数字中的 \(m\) 个进行配对。

而答案又具有二分性质，因此我们可以先二分一个答案 \(m\)，然后去用双指针依次匹配前 \(m\) 个数字，寻找它们所对应的那个大于等于本身二倍的数值。

更进一步的，可以直接简化为从 \(n\) 个数字中选 \(m\) 个最小的和 \(m\) 个最大的进行匹配。读者不妨从上面的双指针查找策略来推演到这一步。

C++

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

复杂度分析

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

本题也有 \(O(n)\) 的做法，即直接从 \(n / 2\) 开始往右找，去不断匹配前面的数字即可。

C++

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

复杂度分析

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

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

比较裸的 dij 模版题，特殊点是需要计算一下奇偶性。

C++

class Solution {
public:
    using TP = tuple<int, int, int>;
    int minimumTime(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> d(n, vector<int>(m, -1));
        priority_queue<TP, vector<TP>, greater<TP>> q;
        d[0][0] = 0;
        q.push(make_tuple(0, 0, 0));
        int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while(q.size()) {
            auto [dis, x, y] = q.top();q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0], ny = y + dir[i][1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (d[nx][ny] != -1) continue;
                if (grid[nx][ny] <= d[x][y] + 1) {
                    d[nx][ny] = d[x][y] + 1;
                    q.push(make_tuple(d[nx][ny], nx, ny));
                } else if (!(x == 0 && y == 0)) {
                    d[nx][ny] = d[x][y] + 1 + (grid[nx][ny] - (d[x][y] + 1)) + (grid[nx][ny] - (d[x][y] + 1)) % 2;
                    q.push(make_tuple(d[nx][ny], nx, ny));
                }
            }
        }
        return d[n - 1][m - 1];
    }
};

（赛后 rejudge 寄了，因为没有特判起点，例如：[[0,1,99],[3,99,99],[4,5,6]]）

正确的做法是直接在一开始就特判起点。

class Solution {
public:
    using TP = tuple<int, int, int>;
    int minimumTime(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        if (grid[0][1] > 1 && grid[1][0] > 1) {
            return -1;
        }
        vector<vector<int>> d(n, vector<int>(m, -1));
        priority_queue<TP, vector<TP>, greater<TP>> q;
        d[0][0] = 0;
        q.push(make_tuple(0, 0, 0));
        int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while(q.size()) {
            auto [dis, x, y] = q.top();q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0], ny = y + dir[i][1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (d[nx][ny] != -1) continue;
                if (grid[nx][ny] <= d[x][y] + 1) {
                    d[nx][ny] = d[x][y] + 1;
                    q.push(make_tuple(d[nx][ny], nx, ny));
                } else {
                    d[nx][ny] = d[x][y] + 1 + (grid[nx][ny] - (d[x][y] + 1)) + (grid[nx][ny] - (d[x][y] + 1)) % 2;
                    q.push(make_tuple(d[nx][ny], nx, ny));
                }
            }
        }
        return d[n - 1][m - 1];
    }
};

复杂度分析

时间复杂度：\(O(nm\log (nm))\)
空间复杂度：\(O(nm)\)

本文访问次