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

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

image.png

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

展开讨论
力扣 (LeetCode)发起于 2020-02-08

将数字变成 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
展开全部 14 讨论