跳转至

2103. 环和杆

来源第 271 场周赛 Q1难度简单分数1257

题目描述

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

解法

方法一：位运算

思考

每根杆只需知道红、绿、蓝是否都出现过。若对 \(10\) 根杆各扫描整串 \(\textit{rings}\) 再分别判断三种颜色，重复遍历过多，且字符串长度为偶数、颜色与杆号成对出现，适合一次扫描完成。

三种颜色是互不重叠的布尔标记，可用三位二进制分别表示。将 'R','G','B' 映射为 \(1,2,4\)，对第 \(j\) 根杆做按位或，则集齐三色当且仅当掩码为 \(7\)。

为此用长度为 \(10\) 的数组 \(\textit{mask}\) 按对读取 \(\textit{rings}\)，最后统计值为 \(7\) 的杆数。

我们可以用一个长度为 \(10\) 的数组 \(\textit{mask}\) 来表示每根杆上的环的颜色情况，其中 \(\textit{mask}[i]\) 表示第 \(i\) 根杆上的环的颜色情况，如果第 \(i\) 根杆上有红色、绿色、蓝色的环，那么 \(\textit{mask}[i]\) 的二进制表示为 \(111\)，即 \(\textit{mask}[i] = 7\)。

我们遍历字符串 \(\textit{rings}\)，对于每个颜色位置对 \((c, j)\)，其中 \(c\) 表示环的颜色， \(j\) 表示环所在的杆的编号，我们将 \(\textit{mask}[j]\) 对应的二进制位进行置位，即 \(\textit{mask}[j] |= d[c]\)，其中 \(d[c]\) 表示颜色 \(c\) 对应的二进制位。

最后我们统计 \(\textit{mask}\) 中值为 \(7\) 的元素的个数，即为集齐全部三种颜色环的杆的数目。

时间复杂度 \(O(n)\)，空间复杂度 \(O(|\Sigma|)\)。其中 \(n\) 表示字符串 \(\textit{rings}\) 的长度，而 \(|\Sigma|\) 表示字符集的大小。

1
2
3
4
5
6
7
8
9
class Solution:
    def countPoints(self, rings: str) -> int:
        mask = [0] * 10
        d = {"R": 1, "G": 2, "B": 4}
        for i in range(0, len(rings), 2):
            c = rings[i]
            j = int(rings[i + 1])
            mask[j] |= d[c]
        return mask.count(7)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int countPoints(String rings) {
        int[] d = new int['Z'];
        d['R'] = 1;
        d['G'] = 2;
        d['B'] = 4;
        int[] mask = new int[10];
        for (int i = 0, n = rings.length(); i < n; i += 2) {
            int c = rings.charAt(i);
            int j = rings.charAt(i + 1) - '0';
            mask[j] |= d[c];
        }
        int ans = 0;
        for (int x : mask) {
            if (x == 7) {
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int countPoints(string rings) {
        int d['Z']{['R'] = 1, ['G'] = 2, ['B'] = 4};
        int mask[10]{};
        for (int i = 0, n = rings.size(); i < n; i += 2) {
            int c = rings[i];
            int j = rings[i + 1] - '0';
            mask[j] |= d[c];
        }
        return count(mask, mask + 10, 7);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func countPoints(rings string) (ans int) {
    d := ['Z']int{'R': 1, 'G': 2, 'B': 4}
    mask := [10]int{}
    for i, n := 0, len(rings); i < n; i += 2 {
        c := rings[i]
        j := int(rings[i+1] - '0')
        mask[j] |= d[c]
    }
    for _, x := range mask {
        if x == 7 {
            ans++
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function countPoints(rings: string): number {
    const idx = (c: string) => c.charCodeAt(0) - 'A'.charCodeAt(0);
    const d: number[] = Array(26).fill(0);
    d[idx('R')] = 1;
    d[idx('G')] = 2;
    d[idx('B')] = 4;
    const mask: number[] = Array(10).fill(0);
    for (let i = 0; i < rings.length; i += 2) {
        const c = rings[i];
        const j = rings[i + 1].charCodeAt(0) - '0'.charCodeAt(0);
        mask[j] |= d[idx(c)];
    }
    return mask.filter(x => x === 7).length;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
impl Solution {
    pub fn count_points(rings: String) -> i32 {
        let mut d: [i32; 90] = [0; 90];
        d['R' as usize] = 1;
        d['G' as usize] = 2;
        d['B' as usize] = 4;

        let mut mask: [i32; 10] = [0; 10];

        let cs: Vec<char> = rings.chars().collect();

        for i in (0..cs.len()).step_by(2) {
            let c = cs[i] as usize;
            let j = (cs[i + 1] as usize) - ('0' as usize);
            mask[j] |= d[c];
        }

        mask.iter().filter(|&&x| x == 7).count() as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int countPoints(char* rings) {
    int d['Z'];
    memset(d, 0, sizeof(d));
    d['R'] = 1;
    d['G'] = 2;
    d['B'] = 4;

    int mask[10];
    memset(mask, 0, sizeof(mask));

    for (int i = 0, n = strlen(rings); i < n; i += 2) {
        int c = rings[i];
        int j = rings[i + 1] - '0';
        mask[j] |= d[c];
    }

    int ans = 0;
    for (int i = 0; i < 10; i++) {
        if (mask[i] == 7) {
            ans++;
        }
    }

    return ans;
}

方法二：暴力枚举

思考

方法一已经线性扫过整串。若只关心实现是否直观，也可以按杆号 \(0\) 到 \(9\) 枚举，用子串查找判断该杆是否同时出现过 'B'、'R'、'G'。

查找本身仍是线性扫描，常数略大，但杆数固定为 \(10\)，复杂度同阶。本题将其作为对照实现。

枚举杆号 \(0\) 到 \(9\)，用字符串查找判断该杆是否同时出现过蓝、红、绿三种颜色。

时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。其中 \(n\) 为字符串 \(\textit{rings}\) 的长度。

1
2
3
4
5
6
7
function countPoints(rings: string): number {
    let c = 0;
    for (let i = 0; i <= 9; i++) {
        if (rings.includes('B' + i) && rings.includes('R' + i) && rings.includes('G' + i)) c++;
    }
    return c;
}

评论