本文最后更新于 339 天前,其中的信息可能已经有所发展或是发生改变。
题目描述:
总计有 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 开始计数)
解法一:位运算
算法思路:
首先,我们创建一个数组 colorValues
来将颜色字符映射到它们对应的值上。例如,‘R’ 的值为 1(二进制 001),‘G’ 的值为 2(二进制 010),‘B’ 的值为 4(二进制 100)。
接下来,我们创建一个数组 rodMask
来存储每个杆子的位掩码。rodMask
数组的索引对应杆子的编号。
遍历字符串 rings
,每次迭代处理一个环。
- 获取环的颜色和所在杆子的编号。
- 使用按位或操作符将环的颜色值与对应杆子的位掩码进行按位或操作,将相应位设置为 1。
处理完所有的环后,我们初始化一个计数器 count
,用于存储具有所有三种颜色的杆子的数量。
我们遍历 rodMask
数组中的元素,对于每个杆子的位掩码,检查它是否等于 7(二进制 111)。如果相等,这意味着该杆子具有所有三种颜色的环,我们将增加计数器 count
的值。
最后,我们返回计数器 count
的值,即具有所有三种颜色的环的杆子的数量。
代码实现:
class Solution {
public int countPoints(String rings) {
int[] colorValues = new int[128]; // Array to map color characters to their corresponding values
colorValues['R'] = 1;
colorValues['G'] = 2;
colorValues['B'] = 4;
int[] rodMask = new int[10]; // Array to store bitmasks for each rod
for (int i = 0; i < rings.length(); i += 2) {
char color = rings.charAt(i);
int rodNumber = rings.charAt(i + 1) - '0';
rodMask[rodNumber] |= colorValues[color];
}
int count = 0; // Variable to store the count of rod that have all three colors
for (int mask : rodMask) {
if (mask == 7) {
count++;
}
}
return count;
}
}
复杂度分析:
时间复杂度: O(n),其中 n 是字符串 rings 的长度。
空间复杂度: O(1)。