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

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

image.png

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

展开讨论
共 14 个讨论

圆满了,希望今年rating能打到前三

7

我太难了,半小时做3题,最后一题,先是DP,然后是DFS,最后还是没过,哎

5

LeetCode双周赛 19

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

题目描述

给你一个非负整数 num ,请你返回将它变成 0 所需要的步数。 如果当前数字是偶数,你需要把它除以 2 ;否则,减去 1 。


解题方法非常简单, 直接按照题目意思就可以了.

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

算法复杂度:O(n), nnum, 空间复杂度: O(1).

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

题目描述

给你一个整数数组 arr 和两个整数 kthreshold

请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。


使用滑动窗口求解, 这里必须说明一下, 必须判断数组大小len(arr)小于k的情况, 否则会出错.

滑动窗口: 先计算前k-1个元素的和. 然后从第k个元素假定为i开始, 加上当前元素arr[i], 判断是否符合要求, 然后减去在他之前的第 k-1个元素arr[i-k+1]. 直到数组结束.

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        if len(arr) < 0: return 0
        total, ans = sum(arr[:k-1]), 0
        for i in range(k - 1, len(arr)):
            total += arr[i]
            if total >= k * threshold: ans = ans + 1
            total -= arr[i-k+1]
        return ans

算法复杂度:O(n), n为数组长度, 空间复杂度:O(1)

5313. 时钟指针的夹角

题目描述

给你两个数 hourminutes 。请你返回在时钟上,由给定时间的时针和分针组成的较小角的角度(60 单位制)。


思路: 分别求解时针,分针与12点的夹角, 然后相减就可以. 注意: 返回的角度应该小于180度.

class Solution:
    def angleClock(self, hour: int, minutes: int) -> float:
        h = ((hour + minutes / 60) / 12) * 360
        m = minutes * 6
        return abs(h - m) if abs(h - m) < 180 else 360 - abs(h-m)

算法复杂度:O(1), n为数组长度, 空间复杂度:O(1)

5314. 跳跃游戏 IV

题目描述

给你一个整数数组 arr ,你一开始在数组的第一个元素处(下标为 0)。
每一步,你可以从下标 i 跳到下标:

  • i + 1 满足:i + 1 < arr.length
  • i - 1 满足:i - 1 >= 0
  • j 满足:arr[i] == arr[j]i != j
    请你返回到达数组最后一个元素的下标处所需的 最少操作次数
    注意:任何时候你都不能跳到数组外面。

B
最少操作次数 , 一般使用BFS(宽度优先搜索), 这题也不例外, 不过这题难点在于按组进行BFS, 如果按照元素BFS, 会超出时间限制.

首先使用map(int, list)将相同元素的下标记录下来, 然后按照规则进行BFS即可.

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr) == 1: return 0
        memo = {}
        for i, v in enumerate(arr):
            if v in memo: memo[v].append(i)
            else: memo[v] = [i]
        step, q, stat = 1, collections.deque([0]), [True] * len(arr)
        stat[0] = False
        while q:
            l = len(q)
            for i in range(len(q)):
                top = q.popleft()
                if top + 1 < len(arr) and stat[top+1]:
                    stat[top+1] = False
                    q.append(top + 1)
                    if top + 1 == len(arr) - 1: return step
                if top - 1 > 0 and stat[top - 1]:
                    stat[top - 1] = False
                    q.append(top - 1)
                if arr[top] in memo:
                    for i in memo[arr[top]]:
                    	if stat[i]:
                            stat[i] = False
                            q.append(i)
                            if i == len(arr) - 1: return step
                    del memo[arr[top]]
					'''#如果使用:
                    for i in memo[arr[top]]:
                    	if stat[i]:
                            stat[i] = False
                            q.append(i)
                            if i == len(arr) - 1: return step
                     #则会超时'''
            step += 1
        return -1

算法复杂度:O(n), nlen(arr),统计相同元素出现位置时需遍历一次O(n), DFS每个元素只需要搜索一次O(n) , 空间复杂度: O(n).

5

题解来了。

先说一下所有题的看法。

前三题非常水, 第四题有点难。
T1:
直接按题意模拟即可。

T2:
用类似滑动窗口的方法。 先选择前k个元素, 看和是否满足。 然后每一次用队列入队一个, 出队一个再次判断。因为并不需要保留队列本身, 只需要一个队列首尾指针。 空间复杂度可以优化到常数。

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

T3:
这道题比T2还容易想一点。
时针每一小时转30度, 每一分钟0.5度。 分针每一分钟6度。直接以12点为基准, 算出两根针转动的角度之差就行了。 注意, 大于180度的时候要用360去减(考虑的是劣角)。

T4:
第四题我用了一种非常zz的优化过了。但是应该过不了所有数据。
该方法是 因为连续相同的数字只有首位两个有用(跳到中间数字相同, 却少了选择, 只能花一步跳到同样的数字, 明显劣于两端的数字)。 因此, 每次连续的数字段只保留首尾。
再BFS过了。

考虑以下数据:
n = 49999, arr = [1,2,3] * 16666 + [4]
n = 49999, arr = [1,2,3] * 8333 + [4,5,6] * 8333 + 7
n = 50000, arr = [1,2] * 25000 + [3,4] * 25000

BFS水过的坐等大家真正的题解!

参考评论区的见解, 以下给出真正的做法。

Step 1. 离散化
原题数据范围很大, 离散化后数据范围变小可以直接取下标,比map快(卡常基本技巧之一)。

Step 2. 连续型优化。
如上面所说, 连续的相同数字只保留首尾。

Step 3. 把这个问题考虑成一个图, 相同的数字和下标相邻的数字都有一条边。 则对所有相同的数字形成的子图是完全图。 这样我们在BFS的时候, 只需要判断每个val是否遍历过。 因为这个图的边没有权值。 一旦在BFS过程中, 一条边作为队首,必定会遍历到该值所有的点。

这样就能如大佬所说的优化到线性了。 当然, 排序是更花时间的。

时间复杂度O(nlogn)
空间复杂度O(n)

3

过于着急的 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

将数字变成 0 的操作次数

思路

  1. 模拟

答题

int numberOfSteps (int num)
{
    int ans = 0;
    while (num != 0)
    {
        num = (num % 2 == 0) ? num / 2 : num - 1;
        ans++;
    }
    return ans;
}

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

思路

  1. 平均值可以转换成和,然后就可以用上前缀和了

答题

int numOfSubarrays(vector<int>& arr, int k, int threshold) 
{
    int ans = 0;
    int sum = k * threshold;

    vector<int> a;
    partial_sum(arr.begin(), arr.end(), back_inserter(a));
    for (auto i = 0; i < a.size() - k + 1; i++)
    {
        if (i == 0 && a[i + k - 1] < sum) continue;
        if (i != 0 && a[i + k - 1] - a[i - 1] < sum) continue;
        ans++;
    }
    return ans;
}

时钟指针的夹角

思路

百度一下:
时针和分针夹角的度数的计算公式:
设12时的刻度线为0度,作为角度起点线,
任意时刻X时Y分时的两针位置,
因为分针每分钟转360/60=6度,
时针每分钟转360/(12*60)=0.5度,
时针每1小时转360/12=30度,
所以,
在X时Y分时,时针与0度起点线的夹角(转过角)是:30X+0.5Y,
在X时Y分时,分针与0度起点线的夹角(转过角)是:6Y,
时针和分针夹角 θ的计算公式是:
θ=|6Y-(30X+0.5Y)|=|5.5Y-30X|,单位是度(°);
习惯上,超过180°的角度一般用它的小于180°的角度(360°-|5.5Y-30X|)表示它们的夹角.

答题

double angleClock(int hour, int minutes) 
{
    double c1 = 30 * hour + 0.5 * minutes;
    double c2 = 6 * minutes;
    double ans = abs(c1 - c2);
    return ans < 180.0 ? ans : 360 - ans;
}

跳跃游戏 IV

思路

  1. 使用 bfs
  2. 根据 j 满足:arr[i] == arr[j] 且 i != j 这个条件
  3. 需要对数据进行处理,使用 unordered_map<int, vector<int>> same 把值相同的索引整理到一起
  4. bfs 时,先向左向右,再向 same 里的跳

用例

Input: [7,7,7, ... 7,11] (4999  7)
Output: 2

没想那么多,结果这个用例超时了。
不能让 bfs 里要把 same 全都跳一遍,所以要把连续的 7 中间都删掉。

答题

int minJumps(vector<int>& arr) 
{
    unordered_map<int, vector<int>> same;
    int pre_i = 0;
    int pre_val = arr[0];
    same[pre_val].push_back(pre_i);
    for (size_t i = 1; i < arr.size(); i++)
    {
        int val = arr[i];
        if (val == pre_val && i != arr.size() - 1)
        {
            pre_i = i;
            continue;
        }
        same[pre_val].push_back(pre_i);
        pre_i = i;
        pre_val = val;
        same[pre_val].push_back(pre_i);
    }

    vector<int> vi(arr.size(), 0);
    queue<int> que;
    que.push(0);
    vi[0] = 1;

    while (!que.empty())
    {
        auto q = que.front();
        que.pop();
        if (q == arr.size() - 1) break;

        if (q != 0 && vi[q - 1] == 0)
        {
            que.push(q - 1);
            vi[q - 1] = vi[q] + 1;
        }
        if (q != arr.size() - 1 && vi[q + 1] == 0)
        {
            que.push(q + 1);
            vi[q + 1] = vi[q] + 1;
        }
        auto s = same[arr[q]];
        for (size_t i = s.size() - 1; i < s.size(); i--)
        {
            if (vi[s[i]] != 0) continue;
            que.push(s[i]);
            vi[s[i]] = vi[q] + 1;
        }
    }

    return vi[arr.size() - 1] - 1;
}

致谢

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

这次又是压哨过的,数学不好是硬伤啊

4

跳跃游戏 IV

给你一个序列,初始位于位置 00

当位于位置 xx 的时候可以:

  • 跳到 x+1x + 1, 满足 x+1<nx + 1 < n
  • 跳到 x1x - 1, 满足 x10x - 1 \geq 0
  • 跳到 jj, 满足 arr[x]=arr[j]arr[x] = arr[j]

问到达位置 n1n - 1 的最少步数。

分析

十分明显的 BFS,暴力做法为按照题目中的三种走法建边跑 BFS。

但是这样复杂度在最坏情况下将会退化成 O(n2)O(n^2) 的,如果一个数组内有 nn 个数字且每个数字都相同,BFS 的过程中,对于第三种操作,nn 数字都将检查 n1n-1 次,导致超时。

但是,我们可以发现第三种操作没有必要连续使用,比如跳跃路径 23->23->23,那么何不从一开始的 23 跳到最后一个第三个 23 呢?为了防止第三种操作连续使用,我们在 BFS 同时维护一个 Flag 数组,如果一个数字是通过第三种操作到达的,就给 Flag 相应位置置 11,否则置 00。这样如果一个数字对应的 Flag 为 11,那么就不适用第三种操作,否则才可以使用。

至于,第三种操作中,检查一个数字可以去哪些位置,可以使用 map<int, vector<int>> 来暴力维护之。

时间复杂度:O(nlogn+n)=O(nlogn)O(nlogn + n) = O(nlogn)

const int MAXN = 5e4 + 50;

int dist[MAXN], flag[MAXN];
map<int, vector<int>> edge;
queue<int> que;
class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        
        for (int i = 0; i <= n; i++) dist[i] = -1, flag[i] = 0;
        edge.clear();
        while(!que.empty()) que.pop();
        
        for (int i = 0; i < n; i++) edge[arr[i]].push_back(i);
        
        que.push(0);
        dist[0] = 0;
        flag[0] = 0;
        
        while(!que.empty()){
            int x = que.front(); que.pop();
            
            if (x + 1 < n && dist[x + 1] == -1){
                que.push(x + 1);
                dist[x + 1] = dist[x] + 1;
                flag[x + 1] = 0;
            }
            
            if (x - 1 >= 0 && dist[x - 1] == -1){
                que.push(x - 1);
                dist[x - 1] = dist[x] + 1;
                flag[x - 1] = 0;
            }
            
            if (flag[x] == 0){
                for (auto v: edge[arr[x]]){
                    if (dist[v] == -1){
                        que.push(v);
                        dist[v] = dist[x] + 1;
                        flag[v] = 1;
                    }
                }
            }
        }
        
        // for(int i = 0; i < n; i++) printf("%d ", dist[i]); printf("\n");
        return dist[n - 1];
    }
};
2

分享下我四道题的代码和思路
第一题很简单,就不具体说明了

class Solution:
    def numberOfSteps (self, num: int) -> int:
        step = 0
        while num:
            step += 1
            if num & 1:
                num -= 1
            else:
                num >>= 1
        return step

第二题,我竟然花了很长时间在理清题目意思上。
我开始以为子数组是可以不连续的,所以看example1有点看不懂。后来想到说“最大子数组之和”那道题,子数组就是连续的,才搞明白。
然后我又陷入了新的迷思:遍历一遍是O(n),如果用二分只要O(logn)。用二分写了一大半后,发现数组不是sorted!那光是sort就要O(nlogn)了。
然后很快用正确的方法写出来了。
好吧,教训就是要认真读题目,不要盲目敲代码。

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        answer = 0
        sum_value = sum(arr[:k])
        if sum_value >= k * threshold:
            answer += 1
        for i in range(len(arr) - k):
            sum_value += arr[i+k] - arr[i]
            if sum_value >= k * threshold:
                answer += 1
        return answer

第三题很简单,简单到不像第三题的难度。

class Solution:
    def angleClock(self, hour: int, minutes: int) -> float:
        mi = minutes / 60 * 360
        hr = (hour + minutes / 60) / 12 * 360
        temp = abs(hr - mi)
        if temp <= 180:
            return temp
        else:
            return 360 - temp

第四题说难不算很难,我一上来就想用bfs,也确实用bfs做出来的。但说简单也不算很简单,有一些细节的地方要注意,并且我一直超时,折腾了很久。直到找到了那个貌似不起眼的错误。

第四题的思路就是把每一步可以达到的所有点给找出来。第1步可以到的就是起点,第2步可以到的是起点的前一位(不存在)、后一位和所有值相同的其他位置,第3步就是第2步所有点的前一位、后一位和所有值相同的其他位置……以此类推

为了求值相同的位置,我们用一个词典把值作为key,把数组的index装在一个set或者list里作为value。

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # 建立字典,用set类型或者list类型都是可以的
        mapping = defaultdict(set)
        for i, num in enumerate(arr):
            mapping[num].add(i)

        # 判断特例:数组只有一个元素的情况
        if len(arr) == 1:
            return 0

        # 然后是常规的bfs写法,count记录第几步,queue记录每一步所有的位置,开始当然只有[0],new_queue表示下一步有哪些位置
        count = 0
        queue = [0]
        while queue:
            count += 1
            new_queue = []
            # 对queue里的每一个值,都可以走到3个地方,前一位、后一位和值相同的其他位置
            for i in queue:
                # 情况一:值相同的其他位置。这里有个小技巧就是如果处理过某个值,就把字段里的这个值的key-value对删掉,以后就不要重复处理了。当然另一个做法是你可以设一个visited集合,放处理过的值。我觉得删key-value比设visited集合要好一些,开销更小。
                if arr[i] in mapping:
                    for j in mapping[arr[i]]:
                        if j == len(arr) - 1:
                            return count
                        new_queue.append(j)
                    # !!!我的问题就是漏写了这句,导致一直超时。注意是值相同的“其它”位置,要把原位置去掉
                    new_queue.remove(i)
                    del mapping[arr[i]]
                # 情况二:前一位。
                if i + 1 < len(arr) and arr[i+1] in mapping:
                    if i + 1 == len(arr) - 1:
                        return count
                    new_queue.append(i+1)
                # 情况三:后一位。
                if i - 1 >= 0 and arr[i-1] in mapping:
                    new_queue.append(i-1)
                # 还有个小技巧是,情况二和情况三要写在情况一后面,这样的话如果当前位置的前一位/后一位和当前位置值相同,你就不会在new_queue里重复记录。因为在情况一的时候已经del mapping[arr[i]]了。当然如果把情况一写在后面,也不影响结果正确性,无非时间开销大一点,并且也能提交成功,属于很微小的影响。
                # 当然如果你用的是设visited集合的方法,就没有这个问题,也不需要这个小技巧。


            queue = new_queue
2

为什么你们都这么强,为什么就我做不出来。。。。T T

1

请问第四题能不能用递归做啊,递归可以剪枝吗?

1