Question

2103. 环和杆

English Version

题目描述

总计有 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$ 的数组 $mask$ 来表示每根杆上的环的颜色情况，其中 $mask[i]$ 表示第 $i$ 根杆上的环的颜色情况，如果第 $i$ 根杆上有红色、绿色、蓝色的环，那么 $mask[i]$ 的二进制表示为 $111$，即 $mask[i] = 7$。

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

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

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

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)

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;
  }
}

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);
  }
};

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
}

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;
}

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
  }
}

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;
}

方法二

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;
}