Easy

题目描述

总共有 n 个环，每个环的颜色可以是红、绿、蓝中的一种。这些环分布在编号为 0 到 9 的 10 根杆子上。

给你一个长度为 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
  • rings[i] 当 i 为偶数时是 ‘R’、‘G’ 或 ‘B’
  • rings[i] 当 i 为奇数时是 ‘0’ 到 ‘9’ 的数字

解题思路

这道题的核心思路是统计每根杆子上有哪些颜色的环，然后计算同时拥有三种颜色的杆子数量。

方法一：哈希表 + 集合

  • 使用哈希表，键为杆子编号（0-9），值为该杆子上颜色的集合
  • 遍历字符串，每两个字符为一组，第一个是颜色，第二个是杆子编号
  • 将颜色添加到对应杆子的集合中
  • 最后统计集合大小为3的杆子数量

方法二：位运算优化

  • 使用数组存储每根杆子的颜色状态，用位掩码表示：R=1, G=2, B=4
  • 当一根杆子的状态为7（1+2+4）时，说明它拥有所有三种颜色
  • 这种方法在空间和时间上都更优化

两种方法的时间复杂度都是O(n)，推荐使用位运算方法，代码更简洁且效率更高。

代码实现

class Solution {
public:
    int countPoints(string rings) {
        vector<int> rods(10, 0);
        
        for (int i = 0; i < rings.length(); i += 2) {
            char color = rings[i];
            int rod = rings[i + 1] - '0';
            
            if (color == 'R') rods[rod] |= 1;
            else if (color == 'G') rods[rod] |= 2;
            else if (color == 'B') rods[rod] |= 4;
        }
        
        int count = 0;
        for (int mask : rods) {
            if (mask == 7) count++;
        }
        
        return count;
    }
};

class Solution:
    def countPoints(self, rings: str) -> int:
        rods = [0] * 10
        
        for i in range(0, len(rings), 2):
            color = rings[i]
            rod = int(rings[i + 1])
            
            if color == 'R':
                rods[rod] |= 1
            elif color == 'G':
                rods[rod] |= 2
            elif color == 'B':
                rods[rod] |= 4
        
        return sum(1 for mask in rods if mask == 7)

public class Solution {
    public int CountPoints(string rings) {
        int[] rods = new int[10];
        
        for (int i = 0; i < rings.Length; i += 2) {
            char color = rings[i];
            int rod = rings[i + 1] - '0';
            
            if (color == 'R') rods[rod] |= 1;
            else if (color == 'G') rods[rod] |= 2;
            else if (color == 'B') rods[rod] |= 4;
        }
        
        int count = 0;
        foreach (int mask in rods) {
            if (mask == 7) count++;
        }
        
        return count;
    }
}

var countPoints = function(rings) {
    const rods = {};
    
    for (let i = 0; i < rings.length; i += 2) {
        const color = rings[i];
        const rod = rings[i + 1];
        
        if (!rods[rod]) {
            rods[rod] = new Set();
        }
        rods[rod].add(color);
    }
    
    let count = 0;
    for (const rod in rods) {
        if (rods[rod].size === 3) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历一次字符串，n为环的数量
空间复杂度O(1)只使用固定大小的数组（10个元素）

相关题目