题目描述
2023.11.2 每日一题
$2103.$ 环和杆
总计有$ n $个环,环的颜色可以是红、绿、蓝中的一种。这些环分别穿在 $10$ 根编号为 $0$ 到 $9$ 的杆上。
给你一个长度为 $2n$ 的字符串 $rings$ ,表示这 $n$ 个环在杆上的分布。$rings$ 中每两个字符形成一个颜色位置对 $ , $ 用于描述每个环:
第 $i$ 对中的第一个字符表示第$ i $个环的颜色(’R’、’G’、’B’)。
第 $i$ 对中的第二个字符表示第 $i$ 个环的 位置,也就是位于哪根杆上($‘0’$ 到 $‘9’$)。
例如,$”R3G2B1”$ 表示:共有 $n == 3$ 个环,红色的环在编号为 $3$的杆上,绿色的环在编号为$ 2$ 的杆上,蓝色的环在编号为 $1$ 的杆上。
找出所有集齐全部三种颜色环的杆,并返回这种杆的数量。
样例
输入
rings = "B0B6G0R6R0R6G9"
输出
1
哈希
时间复杂度 $O(n)$
C++
typedef struct color{
bool B;
bool R;
bool G;
int tag;
color(){
B=false;
R=false;
G=false;
tag=3;
}
}color;
class Solution {
public:
int countPoints(string rings) {
int n=rings.length(),cnt=0;
vector<color> mem(10);
for(int i=0;i<n;i+=2){
switch(rings[i]){
case 'R':
if(mem[rings[i+1]-'0'].R==false) {
mem[rings[i+1]-'0'].tag--;mem[rings[i+1]-'0'].R=true;
if(!mem[rings[i+1]-'0'].tag) cnt++;
}
break;
case 'G':
if(mem[rings[i+1]-'0'].G==false) {
mem[rings[i+1]-'0'].tag--;mem[rings[i+1]-'0'].G=true;
if(!mem[rings[i+1]-'0'].tag) cnt++;
}
break;
case 'B':
if(mem[rings[i+1]-'0'].B==false) {
mem[rings[i+1]-'0'].tag--;mem[rings[i+1]-'0'].B=true;
if(!mem[rings[i+1]-'0'].tag) cnt++;
}
break;
}
}
return cnt;
}
};
Java
class Solution {
public int countPoints(String rings) {
int n=rings.length(),cnt=0;
String[] pole = new String[10];
for (int i = 0; i < n; i+=2) pole[rings.charAt(i+1)-'0']+=String.valueOf(rings.charAt(i));
for (int i = 0; i < 10; i++)
if(pole[i]==null) continue;//必须加这个,因为什么环都没套的杆为空
else if (pole[i].contains("R") && pole[i].contains("G") && pole[i].contains("B")) cnt++;
return cnt;
}
}
二进制存储状态
自己写的标记过于繁琐,。查看题解时看到了用二进制存储杆的状态,于是对原代码格式做了优化(这样改运行内存并没优化,不太清楚为什么)
|= 按位或并赋值
C++
class Solution {
public:
int countPoints(string rings) {
int pole[10]={0},res=0,n=rings.length();
for(int i=0;i<n;i+=2){
switch(rings[i]){
case 'R':
pole[rings[i+1]-'0']|=1; break;
case 'G':
pole[rings[i+1]-'0']|=2; break;
case 'B':
pole[rings[i+1]-'0']|=4; break;
}
}
for(int i=0;i<10;i++) res+=pole[i]==7?1:0;
return res;
}
};