大佬复活,暴打空头,两天拉升 180%

admin2024-05-15  0

GME 暴打空头

大家还记得 2021 年,美国散户大战华尔街的新闻吗?

当时在推特上,几位大佬进行号召,吸引了大量散户往里冲,短短一个月,把一家业绩平平的美股公司「游戏驿站(GME)」拉升了 25 倍,暴击了华尔街所有的做空机构。

在击退几乎所有机构之后,大佬们纷纷淡出,GME 也进入长期阴跌的周期中。

后来这事还被拍成了电影,名为《傻钱》:

大佬复活,暴打空头,两天拉升 180%,alt,第1张

而就在前天,当时号召干翻机构的大哥 Roaring Kitty(咆哮猫)突然复活,在推特中发了一张图片:

大佬复活,暴打空头,两天拉升 180%,alt,第2张

一个玩游戏的人突然正坐,变得专注。

要知道这位大佬,上一条推特可是在 2021 年(35 个月前),这不禁让人遐想。

受此影响,当日 GME 盘前上涨超 50%,开盘后多次触发停牌,盘中最大涨幅去到 110%,收盘时涨幅为 74.4%。

大佬复活,暴打空头,两天拉升 180%,alt,第3张

第二天盘前上涨超 100%,开盘后稍有回落,但收盘时仍收涨 60%。

大佬复活,暴打空头,两天拉升 180%,alt,第4张

短短两天,累积涨幅达 179.21%。

大佬复活,暴打空头,两天拉升 180%,alt,第5张

可见,疯狂还没停止,大家猜测这次戏码会往什么方向发展?

...

回归主线。

来一道和「字节跳动」相关的算法题。

题目描述

平台:LeetCode

题号:878

一个正整数如果能被 ab 整除,那么它是神奇的。

给定三个整数 na , b ,返回第 n 个神奇的数字。因为答案可能很大,所以返回答案 对  取模 后的值。

示例 1:

输入:n = 1, a = 2, b = 3

输出:2

示例 2:

输入:n = 4, a = 2, b = 3

输出:6

提示:

数学

提示一 : 从题面分析常见做法,从常见做法复杂度出发考虑其他做法

若不看数据范围,只看题面,容易想到的做法是「多路归并」:起始使用两个指针指向 [a, 2a, 3a, ... ][b, 2b, 3b, ...] 的开头,不断比较两指针所指向的数值大小,从而决定将谁后移,并不断更新顺位计数。

该做法常见,但其复杂度为 ,对于本题 来说并不可行。

确定线性复杂度的做法不可行后,我们考虑是否存在对数复杂度的做法。

提示二 : 如何考虑常见的对数复杂度做法,如何定义二段性

题目要我们求第 个符合要求的数,假设我们想要通过「二分」来找该数值,那么我们需要分析其是否存在「二段性」。

假设在所有「能够被 ab 整除的数」形成的数轴上,我们要找的分割点是 k,我们期望通过「二分」来找到 k 值,那么需要定义某种性质,使得 k 左边的数均满足该性质,k 右边的数均不满足该性质。

不难想到可根据题意来设定该性质:小于 k 的任意数字 x 满足在 范围数的个数不足 k 个,而大于等于 k 的任意数字 x 则不满足该性质。

提示三 : 如何实现高效的 check 函数

当确定使用「二分」来做时,剩下问题转化为:「如何快速得知某个 中满足要求的数的个数。」

容易联想到「容斥原理」:「能被 ab 整除的数的个数 = 能够被 a 整除的数的个数 + 能够被 b 整除的数的个数 - 既能被 a 又能被 b 整除的数的个数」

其中 cab 的最小公倍数。

求解最小公倍数 lcm 需要实现最大公约数 gcd,两者模板分别为:

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
提示四 : 如何确定值域

一个合格的值域只需要确定答案在值域范围即可,因此我们可以直接定值域大小为

或是根据 ab 的取值来大致确定:假设两者中的较大值为 ,此时第 个符合要求的数最大不会超过 ,因此也可以设定值域大小为

Java 代码:

class Solution {
    int n, a, b, c;
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    public int nthMagicalNumber(int _n, int _a, int _b) {
        n = _n; a = _a; b = _b; c = a * b / gcd(a, b);
        long l = 0, r = (long)1e18;
        while (l < r) {
            long mid = l + r >> 1;
            if (check(mid) >= n) r = mid;
            else l = mid + 1;
        }
        return (int)(r % 1000000007);
    }
    long check(long x) {
        return x / a + x / b - x / c;
    }
}

C++ 代码:

class Solution {
public:
    int n, a, b, c;
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    long check(long x) {
        return x / a + x / b - x / c;
    }
    int nthMagicalNumber(int _n, int _a, int _b) {
        n = _n; a = _a; b = _b; c = a * b / gcd(a, b);
        long l = 0, r = 1e18;
        while (l < r) {
            long mid = l + r >> 1;
            if (check(mid) >= n) r = mid;
            else l = mid + 1;
        }
        return (int)(r % 1000000007);
    }
};

Python3 代码:

class Solution:
    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
        def gcd(a, b):
            return a if b == 0 else gcd(b, a % b)
        def check(x):
            return x // a + x // b - x // c
        c = a * b // gcd(a, b)
        l, r = 01e18
        while l < r:
            mid = (l + r) // 2
            if check(mid) >= n:
                r = mid
            else:
                l = mid + 1
        return int(r % 1000000007)

TypeScript 代码:

function nthMagicalNumber(n: number, a: number, b: number): number {
    function gcd(a: number, b: number): number {
        return b == 0 ? a : gcd(b, a % b)
    }
    function check(x: number): number {
        return Math.floor(x / a) + Math.floor(x / b) - Math.floor(x / c)
    }
    const c = Math.floor(a * b / gcd(a, b))
    let l = 0, r = 1e18
    while (l < r) {
        const mid = Math.floor((l + r) / 2)
        if (check(mid) >= n) r = mid
        else l = mid + 1
    }
    return r % 1000000007
}
  • 时间复杂度: ,其中 为值域大小
  • 空间复杂度:

最后

给大伙通知一下 📢 :

全网最低价 LeetCode 会员目前仍可用 ~

📅 年度会员:有效期加赠两个月!!; 季度会员:有效期加赠两周!!

🧧 年度会员:获 66.66 现金红包!!; 季度会员:获 22.22 现金红包!!

🎁 年度会员:参与当月丰厚专属实物抽奖(中奖率 > 30%)!!

专属链接:leetcode.cn/premium/?promoChannel=acoier

我是宫水三叶,每天都会分享算法知识,并和大家聊聊近期的所见所闻。

欢迎关注,明天见。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!