环和杆

标签: 哈希表 字符串

难度: Easy

总计有 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 开始计数）

Submission

运行时间: 19 ms

内存: 15.9 MB

class Solution:
    def countPoints(self, rings: str) -> int:
        res = 0
        n = int(len(rings) / 2)
        dic = dict()
        for i in range(10):
            dic[i] = ''
        for j in range(n):
            dic[int(rings[2*j + 1])] += rings[2*j]
        for key in dic.keys():
            if dic[key].count('R') >= 1 and dic[key].count('G') >= 1 and dic[key].count('B') >= 1:
                res += 1
        return res

Explain

此题解采用了一个字典来记录每根杆上的环的颜色集合。首先，初始化一个字典，键为杆的编号（0到9），值为一个空字符串，用来追踪每根杆上的环颜色。遍历输入字符串，每两个字符视为一对，第一个是颜色，第二个是杆的编号。将每个环的颜色追加到对应编号杆的字符串中。之后，检查每根杆的字符串，如果包含至少一个红色、绿色和蓝色环，则该杆满足条件。最后，统计满足条件的杆的数量。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def countPoints(self, rings: str) -> int:
        res = 0  # 结果变量，用来计数满足条件的杆数
        n = int(len(rings) / 2)  # 环的总数
        dic = dict()  # 初始化字典来存储每根杆上的环颜色
        for i in range(10):
            dic[i] = ''  # 每个杆的编号初始化为空字符串
        for j in range(n):
            # 将环的颜色加到对应杆的字符串中
            dic[int(rings[2*j + 1])] += rings[2*j]
        for key in dic.keys():
            # 检查每根杆是否满足所有三种颜色至少各有一个环
            if dic[key].count('R') >= 1 and dic[key].count('G') >= 1 and dic[key].count('B') >= 1:
                res += 1  # 如果满足条件，结果加一
        return res

Explore

使用字典来存储杆上环的颜色信息，可以直接通过杆的编号作为键来快速访问和更新对应的环颜色集合。这种方式相比列表，可以避免使用复杂的索引逻辑，并且相对于集合，字典允许我们累积颜色信息而不仅仅是存储是否存在某种颜色。此外，字典提供了高效的键值对应，这在处理具体编号的杆时更直观和方便。

在此题解中，的确会将相同颜色的环重复添加到同一根杆的字符串中。然而，这并不影响最终的判断逻辑，因为算法的目标是检查每根杆是否至少包含一次红色、绿色和蓝色环。即使一个颜色被重复记录，使用`count`函数检查的时候，只要确认每种颜色的数量大于或等于1即可。

使用`count`函数可以直接统计字符串中各个颜色环的数量，这种方法编码简单直观。然而，它的主要缺点是效率问题，因为每次调用`count`时都会重新遍历整个字符串，这在字符串较长时会增加算法的时间复杂度。对于每种颜色，都要进行一次全字符串的遍历，这使得时间复杂度为O(n)，其中n是字符串的长度。更高效的方法可能是使用一次遍历就统计所有颜色的次数。

如果输入字符串`rings`为空，算法将直接返回0，因为没有环可以处理。如果输入的字符串不符合规定的格式，比如颜色和位置对不匹配或者字符串长度不是偶数，算法可能会引发错误或产生不正确的结果。当前的算法实现没有专门处理这种格式错误的逻辑，因此在实际应用中可能需要先验证输入数据的格式是否正确，以避免运行时错误或逻辑错误。