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

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

image.png

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

过于着急的 WA 了 3 次

5311. 将数字变成 0 的操作次数

根据题意来搞就行了..水题 1

class Solution:
    def numberOfSteps (self, num: int) -> int:
        cnt = 0
        while num != 0:
            if num % 2 == 1:
                num -= 1
                cnt += 1
            if num != 0:    
                num = num // 2
                cnt += 1
        return cnt         

5312. 大小为 K 且平均值大于等于阈值的子数组数目

要计算长度为 k ,切均值大于等于 threshold,那其实就找数组和大于等于 k * threshold 的个数就行。这道题说子数组数目,那其实就遍历一遍就可以了。先预处理前缀和,然后算区间个数即可。

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        ss = [0] * len(arr)
        ss[0] = arr[0]
        for i in range(1, len(arr)):
            ss[i] = arr[i] + ss[i - 1]
            
        l, r = 0, k - 1
        res = 0
        while r < len(arr):
            curs = 0
            if l - 1 < 0:
                curs = ss[r]
            else:    
                curs = ss[r] - ss[l - 1]
            if curs >= k * threshold:
                res += 1    
            l += 1    
            r += 1    
        return res     

5313. 时钟指针的夹角

很古老的一道 Google 面试题,推一下公式就出来了 (m * 30 + n * 0.5) - n * 6。另外题里给的是 12 点,换成 0 点,再和 180 度比一下,因为只能出现小于 180° 的角。

class Solution:
    def angleClock(self, m: int, n: int) -> float:
        if m == 12:
            m = 0
        res = n * 6 - (m * 30 + n * 0.5) 
        if res < 0:
            res = (m * 30 + n * 0.5) - n * 6
        if res >= 180:
            res = 360 - res    
        return res

5314. 跳跃游戏 IV

做完之后和很多 AK 的大佬交流,据说可以用数组预处理 + BFS 来搞,所以说明数据很水。

这里我上的 Dijkstra,相邻节点建边,相同数字节点建边,然后从 0 节点跑到 len - 1 节点最短路即可。

另外,数组可以做一个预处理,连续出现相同的数字可以缩成两个节点,因为相同节点是可以直接到达,所以其实就是一步。

struct edge {
    int to, cost;
    edge(int to, int cost) {
        this -> to = to;
        this -> cost = cost;
    };
};
typedef pair<int, int> P;

class Solution {
public:
    int V;
    vector<edge> G[50005];
    int d[50005];
    void dijkstra(int s) {
        int inf = 1000000;
        priority_queue<P, vector<P>, greater<P> > que;
        fill(d, d + V, inf);        
        d[s] = 0;
        que.push(P(0, s));
        while (!que.empty()) {
            pair<int, int> p = que.top();
            que.pop();
            int v = p.second;
            if (d[v] < p.first) continue;
            for (int i = 0; i < G[v].size(); ++ i) {
                edge e = G[v][i];
                if (d[e.to] > d[v] + e.cost) {
                    d[e.to] = d[v] + e.cost;
                    que.push(P(d[e.to], e.to));
                }
            }
        }
    }
    
    int minJumps(vector<int>& arr) {
        vector<int> arrm;
        arrm.push_back(arr[0]);
        int last = 1e9;
        for (int i = 1; i < arr.size(); ++ i) {
            if (arr[i] == arr[i - 1]) {
                if (arr[i] != last) {
                    arrm.push_back(arr[i]);
                    last = arr[i];
                }
            } else {
                arrm.push_back(arr[i]);
            }
        }
        V = arrm.size();
        map<int, vector<int>> ct;
        for (int i = 0; i < arrm.size(); ++ i) {
            if (i == 0) {
                edge x(i + 1, 1);
                G[i].push_back(x);
            }
            else if (i == arrm.size() - 1) {
                edge x(i - 1, 1);
                G[i].push_back(x);
            } 
            else {
                edge x1(i - 1, 1);
                edge x2(i + 1, 1);
                G[i].push_back(x1);
                G[i].push_back(x2);
            }
            int cur = arrm[i];
            ct[cur].push_back(i);
        }
        for (int i = 0; i < arrm.size(); ++ i) {
            vector<int> oth = ct[arrm[i]];
            for (auto &ind: oth) {
                if (ind != i && ind != i + 1 && ind != i - 1) {
                    edge x(ind, 1);
                    G[i].push_back(x);
                }
            }
        }
        dijkstra(0);
        return d[arrm.size() - 1];
    }
};


最后,如果大家对移动端和刷算法题感兴趣,可以微信关注我的技术公众号。

image.png

3
展开全部 14 讨论