On the shoulders of giants.

biweekly-contest-19

将数字变成 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
题解

直接模拟即可。

时间复杂度:\(O(n)\)

class Solution {
public:
    int numberOfSteps (int num) {
        int total = 0;
        while(num) {
            num = (num % 2 ? num - 1 : num / 2);
            total++;
        }
        return total;
    }
};

大小为 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
题解

直接模拟计算,判断是否符合条件。

时间复杂度:\(O(n)\)

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

时钟指针的夹角

给你两个数 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 以内的结果都被视为正确结果。
题解

根据其比例关系,计算出各指针离 12 点位置顺时针多少度,最后做差即可(要做一些转化)。

时间复杂度:\(O(1)\)

class Solution {
public:
    double angleClock(int hour, int minutes) {
        if(hour == 12) hour = 0;
        double ang_hour = 30 * hour + 0.5 * minutes;
        double ang_minu = 6 * minutes;
        double result = fabs(ang_hour - ang_minu);
        if(180.0 < result) result = 360.0 - result;
        return result;
    }
};

跳跃游戏 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
题解

广度优先搜索:根据合法的转移情况,计算出到达终点的最小代价。

第三种转移,我们可以用平衡树来存,键为元素值,值为该元素值出现过的位置。

优化:对于连续且相同的一段,从最左端跳到最右端比最左端跳到中间节点肯定更优,所以我们应该把连续且相同的一段缩成两个端点值。

时间复杂度:\(O(n\log m)\)

class Solution {
public:
    map<int, vector<int>> tree;
    queue<pair<int, int>> q;
    vector<bool> vis;
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        vector<int> num;
        for(int i = 0; i < n; i++) {
            int j = i;
            while(i + 1 < n && arr[j] == arr[i + 1]) i++;
            num.push_back(arr[j]);
            if(i != j) num.push_back(arr[i]);
        }
        n = num.size();
        vis.resize(n);
        for(int i = 0; i < n; i++) {
            tree[num[i]].push_back(i);
        }
        q.push(make_pair(0, 0));
        vis[0] = true;
        while(!q.empty()) {
            pair<int, int> u = q.front(); q.pop();
            if(u.first == n - 1) return u.second;
            if(0 <= u.first - 1 && !vis[u.first - 1]) {
                q.push(make_pair(u.first - 1, u.second + 1));
                vis[u.first - 1] = true;
            } 
            if(u.first + 1 != n && !vis[u.first + 1]) {
                q.push(make_pair(u.first + 1, u.second + 1));
                vis[u.first + 1] = true;
            }
            for(auto e : tree[num[u.first]]) {
                if(vis[e]) continue;
                q.push(make_pair(e, u.second + 1));
                vis[e] = true;
            }
        }
        return -1;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注