Leetcode第50场双周赛

Leetcode第50场双周赛

Louis 886 2021-04-19

喜闻乐见的临时紧急事项清单，这次是第50场双周赛。第一次参加双周赛，原来是晚上十点半到晚上十二点。结果周六八点睡觉睡过头了，醒来直接是11点，剩下60分钟打周赛，所以结果怎样呢。
周赛连接：第 50 场双周赛

最少操作使数组递增

题目连接：最少操作使数组递增

我的解法：

周赛日常热身简单题。

要变成递增数列，需要将当前值变成前面的值加一。

然后当前值替换成新值，不断迭代。

class Solution {
public:
    int minOperations(vector<int> &nums) {
        int ret = 0;
        if (nums.size() == 1) {
            return 0;
        }
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] <= nums[i - 1]) {
                ret += nums[i - 1] - nums[i] + 1;
                nums[i] = nums[i - 1] + 1;
            }
        }
        return ret;
    }
};

没什么太有意思的解法，毕竟是简单题。

统计一个圆中点的数目

题目连接：统计一个圆中点的数目

思路：

  1. 是否在圆中的问题，可以转化成离圆心的距离。
  2. 遍历点、遍历圆圈，判断O(mn)次
  3. 应该没有更换的方法了吧，没做什么冗余计算的感觉

自己的解法：

class Solution {
public:
    vector<int> countPoints(vector<vector<int>> &points, vector<vector<int>> &queries) {
        vector<int> ret(queries.size());
        int index = 0;
        for (auto c : queries) {
            for (auto p: points) {
                if (is_in_cycle(p, c)) {
                    ret[index]++;
                }
            }
            index++;
        }
        return ret;
    }

    bool is_in_cycle(vector<int> &point, vector<int> &cycle) {
        //求距离，看看是否大于半径
        int x = abs(point[0] - cycle[0]);
        int y = abs(point[1] - cycle[1]);
        long double dis = (x * x )+ (y * y);
        dis = sqrt(dis);
        return dis <= cycle[2];
    }
};

一顿操作猛如虎，一看击败百分五。害，太难了，看来还是有更好的解法的，我找找看。

大概瞄了一下评论区，这题大家都在混暴力解。等一下吧，毕竟是新题。

别人的解法：

大概看了一下别人的提交，优化点有一个，将for循环的传入引用。

    vector<int> countPoints(vector<vector<int>> &points, vector<vector<int>> &queries) {
        vector<int> ret(queries.size());
        int index = 0;
        for (auto &c : queries) {//这里变成引用了
            for (auto &p: points) {
                if (is_in_cycle(p, c)) {
                    ret[index]++;
                }
            }
            index++;
        }
        return ret;
    }

一个这么小的改动居然能带来十倍的优化，惊了。

每个查询的最大异或值

题目链接：每个查询的最大异或值

我的思路：

  1. 明显有重复计算，可以从第一个值开始，逐渐往后取亦或，保存在backup
  2. 取亦或的最大值M=2^maximumBit -1 ，需要找一个K值，使得K=N时，与backup取余可以得到最大值M。
  3. 经过验证，N=M-backup
  4. 由于是先算出后面的结果，需要将返回的vector反向一下
class Solution {
public:
    vector<int> getMaximumXor(vector<int> &nums, int maximumBit) {
        vector<int> ret;
        //上一个异或结果
        int backup = 0;
        for (int i = 0; i < nums.size(); i++) {
            backup = backup ^ nums[i];
            //求出k
            int k = pow(2, maximumBit) - 1;
            k -= backup;
            ret.push_back(k);
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

执行用时：168 ms, 在所有 C++ 提交中击败了55.60%的用户
内存消耗：94.9 MB, 在所有 C++ 提交中击败了33.46%的用户

这题的官方题解，也是一样的拉垮样……

class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
        int n = nums.size();
        int mask = (1 << maximumBit) - 1;
        int xorsum = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
        
        vector<int> ans;
        for (int i = n - 1; i >= 0; --i) {
            ans.push_back(xorsum ^ mask);
            xorsum ^= nums[i];
        }
        return ans;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-xor-for-each-query/solution/mei-ge-cha-xun-de-zui-da-yi-huo-zhi-by-l-haol/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

C++的双百解法到底在哪里……

尾声

这次周赛的题目好简单，虽然前面半个小时睡过去了，居然首次在正式周赛中完成了3个题，并且全AC没有罚时，挺爽。全国排名1400+ 应该能把上周的拉垮排名拉回来一点。

Leetcode