双周赛 – 19

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

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

样例

示例 1:

输入:num = 14
输出:6
解释:
步骤 1) 14 是偶数,除以 2 得到 7 。
步骤 2) 7 是奇数,减 1 得到 6 。
步骤 3) 6 是偶数,除以 2 得到 3 。
步骤 4) 3 是奇数,减 1 得到 2 。
步骤 5) 2 是偶数,除以 2 得到 1 。
步骤 6) 1 是奇数,减 1 得到 0 。

示例 2:

输入:num = 8
输出:4
解释:
步骤 1) 8 是偶数,除以 2 得到 4 。
步骤 2) 4 是偶数,除以 2 得到 2 。
步骤 3) 2 是偶数,除以 2 得到 1 。
步骤 4) 1 是奇数,减 1 得到 0 。

示例 3:

输入:num = 123
输出:12

提示

  • 0 <= num <= 10^6

代码

viv丑陋版

太简单啦,直接按照题目暴力模拟就好。

class Solution {
public:
    int numberOfSteps (int num) {
        int ans = 0;
        while(num) {
            if(num & 1) num--;
            else num /= 2;
            ans++;
        }
        return ans;
    }
};

zz美丽版

没啥美丽的,形式主义的写一下。

class Solution {
public:
    int numberOfSteps (int num) {
        int ans = 0;
        while(num > 0) {
            ++ans;
            if(num & 1) num -= 1;
            else num /= 2;
        }
        return ans;
    }
};

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

给你一个整数数组 arr 和两个整数 k 和 threshold 。
请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

样例

示例 1:

输入:arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
输出:3
解释:子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4,5 和 6 。其他长度为 3 的子数组的平均值都小于 4 (threshold 的值)。

示例 2:

输入:arr = [1,1,1,1,1], k = 1, threshold = 0
输出:5

示例 3:

输入:arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
输出:6
解释:前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。

示例 4:

输入:arr = [7,7,7,7,7,7,7], k = 7, threshold = 7
输出:1

示例 5:

输入:arr = [4,4,4,4], k = 4, threshold = 1
输出:1

提示

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^4
  • 1 <= k <= arr.length
  • 0 <= threshold <= 10^4

代码

viv丑陋版

理论上我用的是滑动窗口,但其实写的时候根本没想到这个名词,就直接凭直觉写了。
窗口大小为$k$,初始化的时候将$arr$前$k$个数字放进去。
之后的每次向后移动,$sum$减去移出去的一个数字,加上移进来的一个数字。
在移动过程中不断比较平均值和阈值,记录答案。

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

zz美丽版

一模一样啦。

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int n = arr.size(), sum = 0, ans = 0;
        threshold *= k;

        for(int i=0; i<k; i++) sum += arr[i];
        if(sum >= threshold) ++ans;

        for(int i=k; i<n; i++) {
            sum = sum - arr[i-k] + arr[i];
            if(sum >= threshold) ++ans;
        }
        return ans;
    }
};

3. 时钟指针的夹角

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

样例

示例 1:

输入:hour = 12, minutes = 30
输出:165

示例 2:

输入:hour = 3, minutes = 30
输出;75

示例 3:

输入:hour = 3, minutes = 15
输出:7.5

示例 4:

输入:hour = 4, minutes = 50
输出:155

示例 5:

输入:hour = 12, minutes = 0
输出:0

提示

  • 1 <= hour <= 12
  • 0 <= minutes <= 59
  • 与标准答案误差在 10^-5 以内的结果都被视为正确结果。

代码

viv丑陋版

前几天帮麻麻做初一试卷刚做到原题……
暴力算就可以,注意要求的是锐角,如果是钝角要处理一下。

class Solution {
public:
    double angleClock(int hour, int minutes) {
        double h = (hour * 30) % 360 + minutes * 0.5;
        double m = minutes * 6;
        double ans =  fabs(h - m);
        if(ans - 180 > 1e-5) ans = 360.0 - ans; 
        return ans;
    }
};

zz美丽版

几乎一模一样,无非就是我的取模是多余的因为$1≤hour≤12$。
然后zz在浮点数的处理方面比我谨慎。

class Solution {
public:
    double angleClock(int hour, int minutes) {
        double h_ang = 30.0 * hour + 30.0 / 60.0 * minutes;
        double m_ang = 360.0 / 60.0 * minutes;
        double ans = abs(h_ang - m_ang);
        if(ans > 180.0) ans = 360 - ans;
        return ans;
    }
};

4. 跳跃游戏 IV

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

  • i + 1 满足:i + 1 < arr.length
  • i – 1 满足:i – 1 >= 0
  • j 满足:arr[i] == arr[j] 且 i != j
    请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

注意:任何时候你都不能跳到数组外面。

样例

示例 1:

输入:arr = [100,-23,-23,404,100,23,23,23,3,404]
输出:3
解释:那你需要跳跃 3 次,下标依次为 0 –> 4 –> 3 –> 9 。下标 9 为数组的最后一个元素的下标。

示例 2:

输入:arr = [7]
输出:0
解释:一开始就在最后一个元素处,所以你不需要跳跃。

示例 3:

输入:arr = [7,6,9,6,9,6,9,7]
输出:1
解释:你可以直接从下标 0 处跳到下标 7 处,也就是数组的最后一个元素处。

示例 4:

输入:arr = [6,1,9]
输出:2

示例 5:

输入:arr = [11,22,7,7,7,7,7,7,7,22,13]
输出:3

提示

  • 1 <= arr.length <= 5 * 10^4
  • -10^8 <= arr[i] <= 10^8

代码

viv丑陋版

看到跳跃游戏,条件反射——DP。
然后我想了很久,还是不知道该怎么DP,因为转移又可以往前又可以往后又可以随便跳,怎么想都觉得不对劲。问了zz,他说没有序的关系,无法DP。
大脑稍微绕了个弯,自己草稿纸上的手算过程不是明摆着的BFS嘛TAT,相当于最短路问题。
以最后一个数字为起点开始BFS,每一个数字都有到达前一个/后一个/相同大小的数字的三条路径,最后求出最后一个数字到第一个数字的距离即为答案。
需要处理的一个点在于,用map<int, vector<int>>来记录数字元素对应的序号。
[scode type=”yellow”]注意,用相同大小数字转移过来的数字不用再进行相同大小数字的转移。因为,在相同数字上转移了两次肯定不如第一次直接转移的距离短,但需要额外判断该数字是否vis过,退化成$O(n^2)$。TLE*1,后来临时加了一个flag数组变量处理。
另外,还贡献了一发MLE。
代码中这个语句。

mp[arr[i]].push_back(i);

我原来是这么写的。

vector<int> tmp = mp[arr[i]];
tmp.push_back(i);
mp[arr[i]] = tmp;

就MLE了,减少不必要的内存空间。
[/scode]

class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();

        map<int, vector<int>> mp;
        for(int i=0; i<n; i++) mp[arr[i]].push_back(i);
        
        queue<int> que; que.push(n-1);
        bool vis[n]; memset(vis, false, sizeof(vis)); vis[n-1] = true;
        bool flag[n]; memset(flag, false, sizeof(flag)); 
        int dist[n]; memset(dist, 0, sizeof(dist));

        while(!que.empty()) {
            int x = que.front(); que.pop();
            vis[x] = true;
            if(x+1<n && !vis[x+1]) {
                que.push(x+1);
                vis[x+1] = true;
                dist[x+1] = dist[x] + 1;
            }
            if(x-1>=0 && !vis[x-1]) {
                que.push(x-1);
                vis[x-1] = true;
                dist[x-1] = dist[x] + 1;
            }
            if(flag[x]) continue;
            vector<int> now = mp[arr[x]];
            int m = now.size();
            for(int i=0; i<m; i++) {
                if(!vis[now[i]]) {
                    que.push(now[i]);
                    vis[now[i]] = true;
                    dist[now[i]] = dist[x] + 1;
                    flag[now[i]] = true;
                }
            }
        }
        return dist[0];
    }
};

zz美丽版

思路一样,两个优化。
第一是将dist数组初始化为-1就可以免去vis数组,减少内存消耗。
第二仍然是auto写法,这样就不用每次开辟一个now的vector,我那么写没有再次MLE是万幸。

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.empty();

        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;
                    }
                }
            }
        } 
        return dist[n-1];
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇