环和杆
难度:
标签:
题目描述
总计有 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 开始计数）
代码结果
运行时间: 19 ms, 内存: 15.9 MB
/*
* 思路：
* 1. 使用Map来存储每个杆及其颜色集合。
* 2. 使用Stream API来遍历rings字符串，按对处理，每对第一个字符表示颜色，第二个字符表示位置。
* 3. 更新Map，将颜色加入对应位置的集合中。
* 4. 最后遍历Map，统计包含所有三种颜色的杆的数量。
*/
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.stream.IntStream;
public class RingsAndRodsStream {
public int countPoints(String rings) {
Map<Character, Set<Character>> rodMap = new HashMap<>();
IntStream.range(0, rings.length() / 2).forEach(i -> {
char color = rings.charAt(2 * i);
char position = rings.charAt(2 * i + 1);
rodMap.computeIfAbsent(position, k -> new HashSet<>()).add(color);
});
return (int) rodMap.values().stream().filter(colors -> colors.contains('R') && colors.contains('G') && colors.contains('B')).count();
}
public static void main(String[] args) {
RingsAndRodsStream solution = new RingsAndRodsStream();
System.out.println(solution.countPoints("B0B6G0R6R0R6G9")); // 输出：1
System.out.println(solution.countPoints("B0R0G0R9R0B0G0")); // 输出：1
System.out.println(solution.countPoints("G4")); // 输出：0
}
}
解释
方法:
此题解采用了一个字典来记录每根杆上的环的颜色集合。首先，初始化一个字典，键为杆的编号（0到9），值为一个空字符串，用来追踪每根杆上的环颜色。遍历输入字符串，每两个字符视为一对，第一个是颜色，第二个是杆的编号。将每个环的颜色追加到对应编号杆的字符串中。之后，检查每根杆的字符串，如果包含至少一个红色、绿色和蓝色环，则该杆满足条件。最后，统计满足条件的杆的数量。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么选择使用字典来存储杆上环的颜色信息而不是使用其他数据结构如列表或集合？
▷🦆
在遍历字符串并更新字典时，有没有考虑到可能会重复添加相同颜色的环到同一根杆上的情况？这会影响最终的判断逻辑吗？
▷🦆
题解中提到对每根杆使用`count`函数来判断是否有三种颜色的环，这种方法在效率上有什么优缺点？
▷🦆
如果输入的字符串`rings`为空或者不符合规定的格式（如颜色和位置对不匹配），这个算法会如何处理？
▷