讨论/题目交流/🐱 第 19 场夜喵双周赛/
🐱 第 19 场夜喵双周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 将数字变成 0 的操作次数
4 分 - 大小为 K 且平均值大于等于阈值的子数组数目
5 分 - 时钟指针的夹角
6 分 - 跳跃游戏 IV

展开讨论

题解+关于第四题的一个错误解法

在第四题中,直接按照元素进行BFS是超时的。
但是,只需要把BFS顺序反过来就可以卡进时限。
个人认为数据太弱,极限数据是[7,7,7,7,7,7,7,...],反过来之后就会很快。
我的代码:

class Solution {
public:
    unordered_map <int, vector <int> > g;
    vector <int> ans;
    vector <int> vis;
    int minJumps(vector<int>& arr) {
        for (int i = 0; i < arr.size(); i++) g[arr[i]].push_back(i);
        ans.resize(arr.size());
        vis.resize(arr.size());
        int n = arr.size();
        fill(ans.begin(), ans.end(), 0x3f3f3f3f);
        queue <int> q;
        q.push(0);
        ans[0] = 0;
        vis[0] = true;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (u == n - 1) break;
            if (u - 1 >= 0 && !vis[u - 1]) {
                ans[u - 1] = ans[u] + 1;
                vis[u - 1] = true;
                q.push(u - 1);
            }
            if (u + 1 < arr.size() && !vis[u + 1]) {
                vis[u + 1] = true;
                ans[u + 1] = ans[u] + 1;
                if (u + 1 == n - 1) break;
                q.push(u + 1);
            }
            reverse(g[arr[u]].begin(), g[arr[u]].end());    //此处如果去掉reverse就会T掉
            for (auto v:g[arr[u]]) {
                if (v != u) {
                    if (!vis[v]) {
                        vis[v] = true;
                        ans[v] = ans[u] + 1;
                        if (v == n - 1) break;
                        q.push(v);
                    }
                }
            }
        }
        return ans[arr.size() - 1];
    }
};

前面三题都非常的水。

T1

或许大多数人都能想到朴素模拟做法,但实际上本题可以一行解决。

注意到两种操作要么减少一个二进制位,要么去掉二进制中的一个1,因此答案就是二进制位的数量加上二进制表示中1的数量。

class Solution {
public:
    int numberOfSteps (int num) {
        return (int)log2(num) + __builtin_popcount(num);
    }
};

T2

维护序列的前缀和,然后扫描一遍判断有没有超过k×thresholdk\times threshold 即可。

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int sum = k * threshold;
        vector <int> prefix; prefix.resize(arr.size());
        prefix[0] = arr[0];
        for (int i = 1; i < arr.size(); i++) {
            prefix[i] = prefix[i - 1] + arr[i];
        }
        int ans = 0;
        for (int i = 0; i + k - 1 < arr.size(); i++) {
            if (prefix[i + k - 1] - ((i == 0) ? 0 : prefix[i - 1]) >= sum) ans++;
        }
        return ans;
    }
};

T3

常识+小学奥数

class Solution {
public:
    double angleClock(int hour, int minutes) {
        if (hour == 12) hour = 0;
        double first = hour * 30 + minutes / 60.0 * 30;
        double second = minutes * 6.0;
        return min(abs(second - first), 360 - abs(second - first));
    }
};
展开全部 14 讨论