LC 2103. 环和杆

题目描述

这是 LeetCode 上的 2103. 环和杆 ，难度为 简单。

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

这些环分别穿在 $10$ 根编号为 $0$ 到 $9$ 的杆上。

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

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

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

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

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

示例 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 \times n$
• $1 <= n <= 100$
• 如 i 是 偶数 ，则 rings[i] 的值可以取 'R'、'G' 或 'B'（下标从 0 开始计数）
• 如 i 是 奇数 ，则 rings[i] 的值可以取 '0' 到 '9' 中的一个数字（下标从 0 开始计数）

---

位运算 - 统计环

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

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

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

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

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

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

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

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

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 \times K)$，其中 $n$ 为字符串长度，$C = 10$ 为杆的数量，$K = 3$ 为环类型
• 空间复杂度：$O(K)$

---

位运算 - 统计杆

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

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

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

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

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

• 编号为 $0$ 的杆：三种颜色均出现过，其数值为 $cnt[0] = (…111)_2$，从低位到高位，分别代表 RGB
• 编号为 $6$ 的杆：R 和 B 出现过，其数值为 $cnt[6] = (…101)_2$
• 编号为 $9$ 的杆：G 出现过，其数值为 $cnt[9] = (…010)_2$
• 其他编号的杆：没有任何颜色出现过，其数值为 $cnt[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 \times K + C)$，其中 $n$ 为字符串长度，$C = 10$ 为杆的数量，$K = 3$ 为环类型。
  注：这里为什么不是 $O(n + C)$，在首个循环中，环的类型决定了分支数量，因此首个循环复杂度为 $O(n \times K)$
• 空间复杂度：$O(C)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.2103 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。