資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中配對鏈的最大長度
假設在 Dota2 的世界中，有兩個陣營——天輝和夜魘。Dota2 議會由來自這兩個陣營的議員組成。現在，議會希望對 Dota2 遊戲進行一些修改。對這些修改的投票是一個基於輪次的程式。在每一輪中，每個議員可以行使以下兩種權利之一：
禁止一名議員的權利——一名議員可以使另一名議員在此輪及所有後續輪次中失去所有權利。
宣佈勝利——如果這名議員發現仍然有權投票的議員都來自同一陣營，他可以宣佈勝利並做出關於遊戲修改的決定。
給定一個字串，表示每個議員所屬的陣營。字元 'R' 和 'D' 分別代表天輝陣營和夜魘陣營。然後，如果有 n 名議員，則給定字串的長度將為 n。
基於輪次的程式從給定順序中的第一名議員到最後一名議員開始。此程式將持續到投票結束。所有失去權利的議員都將在程式中被跳過。
假設每個議員都足夠聰明，並且可以為自己的陣營採取最佳策略，您需要預測哪個陣營最終將宣佈勝利並對 Dota2 遊戲進行修改。輸出應為天輝或夜魘。
因此，如果輸入類似於“RDD”，則輸出將為夜魘。這是因為第一名議員來自天輝，他可以在第 1 輪中禁止下一名議員的權利。第二名議員將無法再行使任何權利，因為他的權利已被禁止。之後，第三名議員來自夜魘，他可以在第 1 輪中禁止第一名議員的權利。現在在第 2 輪中，第三名議員可以宣佈勝利，因為他是在議會中唯一可以投票的人。
為了解決這個問題，我們將遵循以下步驟：
建立一個佇列 q1、q2，n := 字串的長度。對於所有 R，將其插入 q1，對於所有 D，將其插入 q2。
當兩個佇列都不為空時
如果 q1 的前部元素 < q2 的前部元素，則
將 n 插入 q1，從 q2 和 q1 中刪除
否則，將 n 插入 q2，從 q2 和 q1 中刪除
將 n 加 1
如果佇列為空，則返回夜魘，否則返回天輝
示例（C++）
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string predictPartyVictory(string s) {
queue <int> q1, q2;
int n = s.size();
for(int i = 0; i < s.size(); i++){
if(s[i] == 'R'){
q1.push(i);
} else {
q2.push(i);
}
}
while(q1.size() && q2.size()){
if(q1.front() < q2.front()){
q1.push(n);
q2.pop();
q1.pop();
} else {
q2.push(n);
q2.pop();
q1.pop();
}
n++;
}
return q1.empty()? "Dire" : "Radiant";
}
};
main(){
Solution ob;
cout <<(ob.predictPartyVictory("RDD"));
}輸入
"RDD"
輸出
Dire
101 次檢視
