【LeetCode】2103. 环和杆
2103. 环和杆
难度:简单
题目
总计有 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 开始计数)
个人题解
- 遍历环,会有三种情况,此时先增加一个统计杆集齐环全部颜色的变量默认为0,
- 还没有对应杆,此时创建杆,并将环的颜色加入到杆中
- 有杆,且杆中不包含该环颜色,则将环的颜色加入到杆中,且统计该杆的个数是否到达3,到达3则表示该杆集齐了全部颜色,统计数加1
- 有杆,且杆中已有环颜色,忽略即可
- 最后返回统计数即得到答案
class Solution {public int countPoints(String rings) {HashMap<Character, HashSet<Character>> map = new HashMap<>();int ans = 0;for (int i = 0; i < rings.length(); i += 2) {if (!map.containsKey(rings.charAt(i + 1))) {HashSet<Character> set = new HashSet<>();set.add(rings.charAt(i));map.put(rings.charAt(i + 1), set);} else if (!map.get(rings.charAt(i + 1)).contains(rings.charAt(i))) {map.get(rings.charAt(i + 1)).add(rings.charAt(i));if (map.get(rings.charAt(i + 1)).size() == 3) {ans++;}}}return ans;}
}
官方题解
方法一:维护每根杆的状态
思路与算法
我们可以遍历字符串中的每个颜色位置对,来模拟套环的过程。
对于每个杆,我们只在意它上面有哪些颜色的环,而不在意具体的数量。因此我们可以用一个大小为 10×3 的二维数组来维护十个杆子的状态,不妨把它命名为 state。在数组的第二维,下标 0,1,2 的数值分别表示是否有红、绿、蓝颜色的环,值为 111 则表示有,值为 000 则表示没有。
每次遇到一个环,就修改对应杆相应颜色的状态为 111。最后遍历所有的杆,统计三个颜色状态都为 111 的杆的个数,并返回该个数作为答案。
class Solution {static final int POLE_NUM = 10;static final int COLOR_NUM = 3;public int countPoints(String rings) {int[][] state = new int[POLE_NUM][COLOR_NUM];int n = rings.length();for (int i = 0; i < n; i += 2) {char color = rings.charAt(i);int poleIndex = rings.charAt(i + 1) - '0';state[poleIndex][getColorId(color)] = 1;}int res = 0;for (int i = 0; i < POLE_NUM; i++) {boolean flag = true;for (int j = 0; j < COLOR_NUM; j++) {if (state[i][j] == 0) {flag = false;break;}}if (flag) {res++;}}return res;}public int getColorId(char color) {if (color == 'R') {return 0;} else if (color == 'G') {return 1;}return 2;}
}
方法二:状态压缩优化
思路与算法
我们也可以用一个 3 位二进制整数来表示每个杆的状态。具体的,在二进制表示中,从低到高的第 0,1,2 位分别表示是否有红、绿、蓝色。每一位为 1 则表示当前杆上有对应颜色的环,为 0 则表示没有。
因此当遇到一个在 3 号杆,颜色为红色的环时,需要将 state[3] 的第 0 位置为 1。在代码中,将 state[3] 与 1 做位或运算即可(因为 2^0 =1)。
最后,遍历 state,统计状态值为 (111)2=7 的个数,并返回该个数作为答案。
class Solution {static final int POLE_NUM = 10;public int countPoints(String rings) {int[] state = new int[POLE_NUM];int n = rings.length();for (int i = 0; i < n; i += 2) {char color = rings.charAt(i);int poleIndex = rings.charAt(i + 1) - '0';if (color == 'R') {state[poleIndex] |= 1;} else if (color == 'G') {state[poleIndex] |= 2;} else {state[poleIndex] |= 4;}}int res = 0;for (int i = 0; i < POLE_NUM; i++) {res += state[i] == 7 ? 1 : 0;}return res;}
}
作者:力扣官方题解
链接:https://leetcode.cn/problems/rings-and-rods/solutions/1153686/huan-he-gan-by-leetcode-solution-88xj/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。