LeetCode 题解工作台
环和杆
总计有 n 个环，环的颜色可以是红、绿、蓝中的一种。这些环分别穿在 10 根编号为 0 到 9 的杆上。 给你一个长度为 2n 的字符串 rings ，表示这 n 个环在杆上的分布。 rings 中每两个字符形成一个 颜色位置对 ，用于描述每个环： 第 i 对中的 第一个 字符表示第 i 个环的 颜…
2
题型
7
代码语言
3
相关题
当前训练重点
简单 · 哈希·表·结合·string
答案摘要
我们可以用一个长度为 的数组 来表示每根杆上的环的颜色情况，其中 表示第 根杆上的环的颜色情况，如果第 根杆上有红色、绿色、蓝色的环，那么 的二进制表示为 ，即 $mask[i] = 7$。 我们遍历字符串 ，对于每个颜色位置对 $(c, j)$，其中 表示环的颜色， 表示环所在的杆的编号，我们将 对应的二进制位进行置位，即 $mask[j] |= d[c]$，其中 表示颜色 …
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·表·结合·string 题型思路
题目描述
总计有 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 * n1 <= n <= 100- 如
i是 偶数 ，则rings[i]的值可以取'R'、'G'或'B'（下标从 0 开始计数） - 如
i是 奇数 ，则rings[i]的值可以取'0'到'9'中的一个数字（下标从 0 开始计数）
解题思路
方法一：位运算
我们可以用一个长度为 的数组 来表示每根杆上的环的颜色情况，其中 表示第 根杆上的环的颜色情况，如果第 根杆上有红色、绿色、蓝色的环，那么 的二进制表示为 ，即 。
我们遍历字符串 ，对于每个颜色位置对 ，其中 表示环的颜色， 表示环所在的杆的编号，我们将 对应的二进制位进行置位，即 ，其中 表示颜色 对应的二进制位。
最后我们统计 中值为 的元素的个数，即为集齐全部三种颜色环的杆的数目。
时间复杂度 ，空间复杂度 ，其中 表示字符串 的长度，而 表示字符集的大小。
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)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) where n is the number of rings, since each pair is processed once. Space complexity is O(1) because there are at most 10 rods and 3 colors, so the hash table size is constant. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Tracking colors per rod efficiently using a hash table.
- question_mark
Iterating over string pairs correctly without skipping or overlapping indices.
- question_mark
Counting rods with all colors correctly after mapping.
常见陷阱
外企场景- error
Misinterpreting color-position pairs and swapping indices.
- error
Forgetting to check all three colors when counting rods.
- error
Using nested loops unnecessarily and increasing time complexity.
进阶变体
外企场景- arrow_right_alt
Count rods that contain exactly two colors instead of all three.
- arrow_right_alt
Allow rods to have multiple rings of the same color and count distinct color occurrences.
- arrow_right_alt
Extend rods from 10 to m rods with dynamic labeling, adjusting the hash table accordingly.