資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告