關鍵字：“貪心”、“隊列模擬”、“詳細分析”
題目描述
詳情見：
LeetCode-Dota2參議院
分析
- 對于一名參議員來說，當投票時，要禁止對方參議員的權力。
- 當一方參議員全部被禁止后，另一方獲勝。
要模擬這個投票過程，問題在于每個參議員如何選擇其要禁止的敵對方參議員。那么，如何選擇呢？
貪心：選擇在自己投票后首先會進行投票的對方參議員。
如何證明這一點呢？
這里先給出幾個例子，直觀的認識到順序的重要性。再對該貪心策略的正確性進行直觀分析、理論證明。
幾個例子
| 例子 | 結果 |
|---|---|
| "RD" | R |
| "RRDDD" | R |
第一個例子說明，禁止能力的順序對結果的影響很大，"RD"與"DR"的結果不同。
第二個例子說明，參議員個數更多(超過半數)不一定會贏得最終結果。
分析
就一輪來說，聯(lián)想：類比于打牌（單升等），假設有同一花色1-13的紙牌，雙方分別不放回的抽了數張，如果互相知道彼此的手牌是什么，假設雙方分別用、
表示，對于
，其打出的手牌
壓過
手牌中面值小于
的最大值的手牌。
在本題中，一方為R，一方為D，R的目前打出的最大牌（先投票的參議員）希望將D的最大牌（D的接下來最先投票的參議員）壓過（禁止）。
證明
這里想要證明的是：選擇禁止對方下一個最先投票的參議員是最優(yōu)選擇。
假設對方下一個最先投票的參議員的順序(index)為，如果不選擇禁止該參議員，而選擇禁止順序在其后的另一參議院，設其順序(index)為
。則其他情況不變，會導致己方順序在
到
之間的參議員有了被禁止發(fā)言的威脅。
解題思路
使用隊列來存儲各方參議員的投票順序。每方參議員按照這個貪心的思想禁止對方參議員。最后一方參議員被全部禁止就結束，得出投票結果。
算法
INPUT: string
OUTPUT: winner
// init R與D的存儲結構queue
for i <- 0 to string.size :
if string[i] == 'R'
R_queue.push(i)
else
D_queue.push(i)
// 模擬整個過程的情況
for R_queue not empty ans D_queue not empty :
//對于每輪的投票
R_next, D_next <- [],[]
while R_queue not empty or D_queue not empty :
if R_queue not empty and D_queue not empty //當兩者都有item時
if R_queue.front() < D_queue.front() // R的參議員先投票
D_queue.pop()
R_next.push( R_queue.front() )
R_queue.pop()
else
D_queue.pop()
R_next.push( R_queue.front() )
R_queue.pop()
continue
while R_queue not empty :
if D_next not empty
D_next.pop()
R_next.push( R_queue.front() )
R_queue.pop()
while D_queue not empty :
if R_next not empty
R_next.pop()
D_next.push( D_queue.front() )
D_queue.pop()
R_queue <- R_next
D_queue <- D_next
// 當某一方為空后，投票結束
return (R_queue.empty()) ? "R" : "D"
數據結構
在上邊的討論中，只需要用到隊列的相關功能。
代碼實現(xiàn)
class Solution {
public:
string predictPartyVictory(string senate) {
queue<int> R_curr ;
queue<int> D_curr ;
// 數據統(tǒng)計
for ( int i = 0 ; i < senate.size() ; ++i ){
if ( senate[i]=='R' ){
R_curr.push(i) ;
}else{
D_curr.push(i) ;
}
}
while ( !R_curr.empty() && !D_curr.empty() ) {
queue<int> R_next ;
queue<int> D_next ;
while ( !R_curr.empty() || !D_curr.empty() ){
if ( !R_curr.empty() && !D_curr.empty() ){
if ( R_curr.front() < D_curr.front() ){
cout << "R" ;
D_curr.pop() ;
R_next.push( R_curr.front() ) ;
R_curr.pop() ;
}else{
cout << "D" ;
R_curr.pop() ;
D_next.push( D_curr.front() ) ;
D_curr.pop() ;
}
continue ;
}
//一個為空
while ( !D_curr.empty() ){
if ( !R_next.empty() )
R_next.pop() ;
D_next.push( D_curr.front() );
D_curr.pop() ;
}
while ( !R_curr.empty() ){
if ( !D_next.empty() )
D_next.pop() ;
R_next.push( R_curr.front() );
R_curr.pop() ;
}
}
cout << endl ;
R_curr = R_next ;
D_curr = D_next ;
}
cout << D_curr.empty() << " " << D_curr.size() << endl ;
cout << R_curr.size() << endl ;
return R_curr.empty() ? "Dire" : "Radiant" ;
}
};
解題思路改良
改進思路
對于一個排名靠前的參議員，進行本輪禁止他人的投票后，由于對方“貪心”，所以不會被禁止。因此一定會進入下一輪的投票中，可以將多輪合并，看成是新加入一個排名靠后（比當前所有參議員的排名都靠后）的參議員。
算法
INPUT: string
OUTPUT: winner
// init R與D的存儲結構queue
for i <- 0 to string.size :
if string[i] == 'R'
R_queue.push(i)
else
D_queue.push(i)
// 模擬整個過程的情況
for R_queue not empty ans D_queue not empty:
if R_queue.front() < D_queue.front():
D_queue.pop()
R_queue.push( R_queue.front()+string.size )
R_queue.pop()
else:
R_queue.pop()
D_queue.push( D_queue.front()+string.size )
D_queue.pop()
// 判斷最終哪方為空
return (R_queue.empty()) ? "R" : "D"
代碼
class Solution {
public:
string predictPartyVictory(string senate) {
queue<int> R ;
queue<int> D ;
int size = senate.size() ;
// 數據統(tǒng)計
for ( int i = 0 ; i < size ; ++i ){
if ( senate[i]=='R' ){
R.push(i) ;
}else{
D.push(i) ;
}
}
// 模擬，直到有一方所有參議員被禁止
while ( !R.empty() && !D.empty() ){
if ( R.front() < D.front() ){
D.pop() ;
R.push( R.front()+size ) ; // 投票后再次放進隊列中
R.pop() ;
}else{
R.pop() ;
D.push( D.front()+size ) ;
D.pop() ;
}
}
return R.empty() ? "Dire" : "Radiant" ;
}
};
相關問題
待補充
PS.
相比較于其他已有的leetcode刷題筆記，我希望能夠提供相關的解題分析和部分相關問題的鏈接，使得大家能獲得一個較好的分析與相關問題的比較。
偶爾會進行類似題目的總結工作，有需要的讀者可以對這份工作進行關注。
如果你發(fā)現(xiàn)有相關的錯誤或者表述不當不清晰的地方，請進行評論，我會盡快進行核對勘正。
