二次元惨遭清仓式抛售 °(°ˊДˋ°) °

阿里减持 B 站

众所周知，一线互联网大厂通常会持有次一线互联网大厂的股票。

这很好理解，背后其实就是一个简单的商业逻辑：既为了实现战略合作、资源共享，也是为了风险分散。

哪天次一线厂起飞了，从市场份额上抢占了更多的蛋糕，那一线大厂也可以在金融领域找补一些回来，做个对冲。

例如以前腾讯持有美团，阿里持有 B 站等等。

阿里总共持有 3000 多万股 B 站，占比超过5%，但就在昨天阿里清仓式减持 B 站，套现约 3.6 亿美元。

那这不难理解，毕竟现在中概互联的复兴看不到希望，大家都先顾自己了，哪还管得了风险对冲，况且后面阿里还有几百亿美元的回购计划，必然是需要先腾钱。

至于和 B 站近期公布的财报有没有直接关系，个人感觉关系不会太大。

阿 B 亏损不是这两年的事，阿里看中的是 B 站高粘度年轻化的社区生态，B 站在这方面的护城河没有动摇，这点财报预期不至于让持股 5% 的大股东清仓式抛售。

今天阿里相关的人士进行的表态也印证了这一点猜测。

财联社发布了阿里方面的声明：此次出售主要基于阿里自身的资本管理目标，不会影响双方业务上的合作，阿里旗下相关业务会继续加强与 B 站在各领域的合作。

...

回归主线。

做一道和「阿里巴巴」社招相关的面试算法原题。

题目描述

平台：LeetCode

题号：2103

总计有 n 个环，环的颜色可以是红、绿、蓝中的一种。

这些环分别穿在 101010 根编号为 000 到 999 的杆上。

给你一个长度为 2n 的字符串 rings，表示这 n 个环在杆上的分布。

rings 中每两个字符形成一个 颜色位置对 ，用于描述每个环：

• 第 i 对中的 第一个 字符表示第 i 个环的 颜色（'R'、'G'、'B'）。
• 第 i 对中的 第二个 字符表示第 i 个环的 位置，也就是位于哪根杆上（'0' 到 '9'）。

例如，"R3G2B1" 表示：共有 n=3n = 3n=3 个环，红色的环在编号为 333 的杆上，绿色的环在编号为 222 的杆上，蓝色的环在编号为 111 的杆上。

找出所有集齐「全部三种颜色」环的杆，并返回这种杆的数量。

示例 1：

输入：rings = "B0B6G0R6R0R6G9"

输出：1

解释：
- 编号 0 的杆上有 3 个环，集齐全部颜色：红、绿、蓝。
- 编号 6 的杆上有 3 个环，但只有红、蓝两种颜色。
- 编号 9 的杆上只有 1 个绿色环。
因此，集齐全部三种颜色环的杆的数目为 1 。

示例 2：

输入：rings = "B0R0G0R9R0B0G0"

输出：1

解释：
- 编号 0 的杆上有 6 个环，集齐全部颜色：红、绿、蓝。
- 编号 9 的杆上只有 1 个红色环。
因此，集齐全部三种颜色环的杆的数目为 1 。

示例 3：

输入：rings = "G4"

输出：0

解释：
只给了一个环，因此，不存在集齐全部三种颜色环的杆。

提示：

• rings.length=2×nrings.length = 2 \times nrings.length=2×n
• 1<=n<=1001 <= n <= 1001<=n<=100
• 如 i 是 偶数 ，则 rings[i] 的值可以取 'R'、'G' 或 'B'（下标从 0 开始计数）
• 如 i 是 奇数 ，则 rings[i] 的值可以取 '0' 到 '9' 中的一个数字（下标从 0 开始计数）

位运算 - 统计环

环的数量不定，但杆的数量就 101010 根。

我们可以从「环」的角度出发，进行统计。

用一个 int 来代表环的统计情况，根据题意，共有 RGB 三种颜色的环，共需要 333 个 int 数（为了方便，代码直接开了大小为 128128128 的数组）。

对于一个代表环的数值 xxx 而言，从低位往高位数，若第 kkk 位为 111，代表编号为 kkk 的杆包含该颜色的环。

用示例 111 来举个 🌰，rings = "B0B6G0R6R0R6G9"

• 红色：在 0 和 6 中出现过，对应数值 x=(0001000001)2x = (0001000001)_2x=(0001000001)2​
• 蓝色：在 0 和 6 中出现过，对应数值 x=(0001000001)2x = (0001000001)_2x=(0001000001)2​
• 绿色：在 9 中出现过，对应数值 x=(100000000)2x = (100000000)_2x=(100000000)2​

在代表三种颜色的数值中，相同位均为 111，假设为第 kkk 位，则代表三种颜色均在第 kkk 杆中出现过。

最后，统计 101010 根杆中有多少满足要求即可。

Java 代码：

class Solution {
    public int countPoints(String s) {
        int n = s.length(), ans = 0;
        int[] map = new int[128];
        for (int i = 0; i < n; i += 2) map[s.charAt(i) - 'B'] |= 1 << (s.charAt(i + 1) - '0');
        for (int i = 0; i < 10; i++) {
            int tot = 0;
            for (char c : new char[]{'R', 'G', 'B'}) tot += (map[c - 'B'] >> i) & 1;
            if (tot == 3) ans++;
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int countPoints(string s) {
        int n = s.size(), ans = 0;
        vector<int> map(128, 0);
        for (int i = 0; i < n; i += 2) map[s[i] - 'B'] |= 1 << (s[i + 1] - '0');
        for (int i = 0; i < 10; i++) {
            int tot = 0;
            for (char c : {'R', 'G', 'B'}) tot += (map[c - 'B'] >> i) & 1;
            if (tot == 3) ans++;
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def countPoints(self, s: str) -> int:
        n, ans = len(s), 0
        map = [0] * 128
        for i in range(0, n, 2):
            map[ord(s[i]) - ord('B')] |= 1 << (int(s[i + 1]) - int('0'))
        for i in range(10):
            tot = 0
            for c in ['R', 'G', 'B']:
                tot += (map[ord(c) - ord('B')] >> i) & 1
            ans += 1 if tot == 3 else 0
        return ans

TypeScript 代码：

function countPoints(s: string): number {
    let n = s.length, ans = 0;
    const map = new Array(128).fill(0);
    for (let i = 0; i < n; i += 2) {
        map[s.charCodeAt(i) - 'B'.charCodeAt(0)] |= 1 << (s.charCodeAt(i + 1) - '0'.charCodeAt(0));
    }
    for (let i = 0; i < 10; i++) {
        let tot = 0;
        for (const c of ['R', 'G', 'B']) tot += ((map[c.charCodeAt(0) - 'B'.charCodeAt(0)]) >> i) & 1;
        if (tot == 3) ans++;
    }
    return ans;
};

• 时间复杂度：O(n+C×K)O(n + C \times K)O(n+C×K)，其中 nnn 为字符串长度，C=10C = 10C=10 为杆的数量，K=3K = 3K=3 为环类型
• 空间复杂度：O(K)O(K)O(K)

位运算 - 统计杆

虽然环的数量不定，但我们只关心其在某根杆上是否出现过，而不关心其出现次数。

因此，我们也可以从「杆」的角度出发，进行统计。

创建一个大小为 101010 的整型数组 cnt，其中 cnt[k]=xcnt[k] = xcnt[k]=x 代表第 kkk 根杆的统计情况为 xxx。

从低位到高位，我们对三种颜色 RGB 的出现与否进行统计，使用 0 和 1 分别代表「没出现」和「出现」两种情况。

用示例 111 来举个 🌰，rings = "B0B6G0R6R0R6G9"

• 编号为 000 的杆：三种颜色均出现过，其数值为 cnt[0]=(...111)2cnt[0] = (...111)_2cnt[0]=(...111)2​，从低位到高位，分别代表 RGB
• 编号为 666 的杆：R 和 B 出现过，其数值为 cnt[6]=(...101)2cnt[6] = (...101)_2cnt[6]=(...101)2​
• 编号为 999 的杆：G 出现过，其数值为 cnt[9]=(...010)2cnt[9] = (...010)_2cnt[9]=(...010)2​
• 其他编号的杆：没有任何颜色出现过，其数值为 cnt[i]=0cnt[i] = 0cnt[i]=0

Java 代码：

class Solution {
    public int countPoints(String s) {
        int n = s.length(), ans = 0;
        int[] cnt = new int[10];
        for (int i = 0; i < n; i += 2) {
            char c = s.charAt(i);
            int idx = -1, t = s.charAt(i + 1) - '0';
            if (c == 'R') idx = 0;
            else if (c == 'G') idx = 1;
            else idx = 2;
            cnt[t] |= 1 << idx;
        }
        for (int i = 0; i < 10; i++) {
            if (cnt[i] == (1 << 3) - 1) ans++;
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int countPoints(string s) {
        int n = s.size(), ans = 0;
        vector<int> cnt(10, 0);
        for (int i = 0; i < n; i += 2) {
            int idx = -1, t = s[i + 1] - '0';
            if (s[i] == 'R') idx = 0;    
            else if (s[i] == 'G') idx = 1;
            else idx = 2;
            cnt[t] |= 1 << idx;
        }
        for (int i = 0; i < 10; i++) {
            if (cnt[i] == (1 << 3) - 1) ans++;
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def countPoints(self, s: str) -> int:
        n, ans = len(s), 0
        cnt = [0] * 10
        for i in range(0, n, 2):
            idx, t = -1, int(s[i + 1])
            if s[i] == 'R':
                idx = 0
            elif s[i] == 'G':
                idx = 1
            else:
                idx = 2
            cnt[t] |= 1 << idx
        for i in range(10):
            ans += 1 if cnt[i] == (1 << 3) - 1 else 0
        return ans

TypeScript 代码：

function countPoints(s: string): number {
    let n = s.length, ans = 0;
    const cnt = new Array(10).fill(0);
    for (let i = 0; i < n; i += 2) {
        let idx = -1, t = parseInt(s[i + 1]);
        if (s[i] == 'R') idx = 0;
        else if (s[i] == 'G') idx = 1;
        else idx = 2;
        cnt[t] |= 1 << idx;
    }
    for (let i = 0; i < 10; i++) {
        if (cnt[i] == (1 << 3) - 1) ans++;
    }
    return ans;
};

• 时间复杂度：O(n×K+C)O(n \times K + C)O(n×K+C)，其中 nnn 为字符串长度，C=10C = 10C=10 为杆的数量，K=3K = 3K=3 为环类型。 注：这里为什么不是 O(n+C)O(n + C)O(n+C)，在首个循环中，环的类型决定了分支数量，因此首个循环复杂度为 O(n×K)O(n \times K)O(n×K)
• 空间复杂度：O(C)O(C)O(C)

最后

给大伙通知一下 📢 ：

全网最低价 LeetCode 会员目前仍可用，快来薅羊毛！！！

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

🧧 年度会员：获 66.66 现金红包！！; 季度会员：获 22.22 现金红包！！

🎁 年度会员：参与当月丰厚专属实物抽奖（中奖率 > 30%)！！

专属链接：leetcode.cn/premium/?pr…

更多详情请戳 这里 。

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

欢迎关注，明天见。

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