数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++ Zuma游戏
让我们考虑一下Zuma游戏。假设桌面上有一排球，这些球的颜色为红色(R)、黄色(Y)、蓝色(B)、绿色(G)和白色(W)。我们也有一些球。
现在，每次我们可以选择一个我们手里的球，并将它插入到这一排球中。然后，如果有一组3个或更多相同颜色的球相邻，则将其移除。重复此过程，直到无法再移除任何球。
我们必须找到移除桌面上所有球所需的最小球数。如果我们无法移除所有球，则返回-1。
因此，如果输入为“WRRBBW”，而我们有“RBW”，则答案为3。我们可以在RR之后添加R，(WRR[R]BBW)，移除后，序列将变为(WBBW)，然后添加B，(WBB[B]W)，移除后将变为(WW)，然后添加W，序列将变为(WW[W])。这将移除所有球。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数`findMinStep()`，它将接收s和hand作为参数。
- s := s + "#"
- 定义一个大小为26的数组v
- for i := 0 to size of hand -1 do −
- v[hand[i] - 'A'] ++
- ret := solve(s, v)
- return ret >= INF ? -1 : ret
- 定义一个函数`solve()`，它将接收s和数组v作为参数。
- if s == "#", then −
- return 0
- ret := INF
- for i := 0, j := 0 to size of s - 1 do −
- if s[i] == s[j], then −
- 跳过本次迭代
- need := 3 - (j - i)
- x := s[i]
- if need <= v[x - 'A'], then −
- v[x - 'A'] -= need
- ret := min(ret, need + solve(s.substring(0, i) + s.substring(j), v))
- v[x - 'A'] += need
- i := j
- if s[i] == s[j], then −
- process(s)
- if s == "#", then −
- return 0
- for i := 0, j := 0 to size of s - 1 do −
- if s[i] == s[j], then −
- 跳过本次迭代
- need := 3 - (j - i)
- x := s[i]
- if need <= v[x - 'A'], then −
- v[x - 'A'] -= need
- ret := min(ret, need + solve(s.substring(0, i) + s.substring(j), v))
- v[x - 'A'] += need
- i := j
- if s[i] == s[j], then −
- return ret
- 定义一个函数`process()`，它将接收s作为参数。
- for i := 0, j := 0 to size of s - 1 do −
- if s[i] == s[j], then −
- 跳过本次迭代
- if (j - i) >= 3, then −
- 从s中删除i到j之间的字符
- j := i - 1
- 否则
- i := j
- if s[i] == s[j], then −
- 使用两个字符串调用`findMinStep()`来获取答案
让我们看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
class Solution {
public:
int findMinStep(string s, string hand) {
s += "#";
vector <int> v(26);
for(int i = 0; i < hand.size(); i++){
v[hand[i] - 'A']++;
}
int ret = solve(s, v);
return ret >= INF ? -1 : ret;
}
int solve(string s, vector <int>& v){
if(s == "#") return 0;
int ret = INF;
for(int i = 0, j = 0; j < s.size(); j++){
if(s[i] == s[j]) continue;
int need = 3 - (j - i);
char x = s[i];
if(need <= v[x - 'A']){
v[x - 'A'] -= need;
ret = min( ret, need + solve(s.substr(0,i) + s.substr(j , s.size() - j), v));
v[x - 'A'] += need;
}
i = j;
}
process(s);
if(s == "#") return 0;
for(int i = 0, j = 0; j < s.size(); j++){
if(s[i] == s[j]) continue;
int need = 3 - (j - i);
char x = s[i];
if(need <= v[x - 'A']){
v[x - 'A'] -= need;
ret = min( ret, need + solve(s.substr(0,i) + s.substr(j , s.size() - j), v));
v[x - 'A'] += need;
}
i = j;
}
return ret;
}
void process(string& s){
for(int i = 0, j = 0; j < s.size(); j++){
if(s[i] == s[j]) continue;
if((j - i) >= 3){
s.erase(i, j - i);
j = i - 1;
} else i = j;
}
}
};
main(){
Solution ob;
cout << (ob.findMinStep("WRRBBW", "RBW"));
}输入
"WRRBBW", "RBW"
输出
3
更新于：2020年6月1日
672 次浏览
广告