はじめに
LeetCodeの問題を解答します。
なるべく、問題の和訳と詳細なコメントを書いています。
余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。
様々なカテゴリの問題をランダムにあたる方法も良いですが、
二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。
テーマごとに問題を分類しました。
LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。
また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。
はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。
ポイント
詳細
問題
原文
In the world of Dota2, there are two parties: the Radiant and the Dire.
The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:
- Ban one senator’s right: A senator can make another senator lose all his rights in this and all the following rounds.
- Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.
Given a string
senate
representing each senator’s party belonging. The character'R'
and'D'
represent the Radiant party and the Dire party. Then if there aren
senators, the size of the given string will ben
.The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.
Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be
"Radiant"
or"Dire"
.
Example 1:
123456 Input: senate = "RD"Output: "Radiant"Explanation:The first senator comes from Radiant and he can just ban the next senator's right in round 1.And the second senator can't exercise any rights anymore since his right has been banned.And in round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.Example 2:
1234567 Input: senate = "RDD"Output: "Dire"Explanation:The first senator comes from Radiant and he can just ban the next senator's right in round 1.And the second senator can't exercise any rights anymore since his right has been banned.And the third senator comes from Dire and he can ban the first senator's right in round 1.And in round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.
Constraints:
n == senate.length
1 <= n <= 104
senate[i]
is either'R'
or'D'
.
内容(和訳)
Dota2の世界には、RadiantとDireの2つの党があります。
Dota2の上院は、2つの政党からなる上院議員で構成されています。現在、上院はDota2ゲームの変更を決定しようとしています。この変更の投票は、ラウンドをベースにした手順です。各ラウンドで、各上院議員は次の2つの権利のいずれかを行使できます。
- 上院議員は、別の上院議員の権利を禁止することができます。上院議員は、このラウンドと次のすべてのラウンドすべてですべての権利を失うようにすることができます。
- 勝利を宣言する:この上院議員は、まだ投票する権利を持っている上院議員がすべて同じ政党からのものである場合、勝利を宣言し、ゲームの変更を決定することができます。
各上院議員の所属政党を表す文字列senateが与えられます。文字’R’と’D’はRadiant党とDire党を表します。次に、上院議員がn人いる場合は、与えられた文字列のサイズはnになります。
ラウンドをベースにした手順は、指定された順序で最初の上院議員から最後の上院議員まで開始されます。この手順は、投票が終了するまで続きます。手順中、権利を失った上院議員はすべてスキップされます。
すべての上院議員が賢く、自分の党のために最善の戦略を実行すると仮定します。最終的に勝利を宣言し、Dota2ゲームを変更する党を予測してください。出力は「Radiant」または「Dire」です。
簡潔にまとめなおしてみる。
Radiant党とDire党があり、どちらかの勝利を決める。
各党員は以下のどちらかを行うことができる。
・相手チームを1人永遠に行動不能にする
・相手チームが0人だったら勝利宣言を行う
全員の行動が終わったら残っているチームメンバーで第二、第三ラウンドと繰り返す。
なので、相手チームのメンバーを全員行動不能にすることを考える。
※Bardによる翻訳
解答
解答1:Python, キュー, iterative
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
class Solution: def predictPartyVictory(self, senate: str) -> str: #キューsenatorsにsenateを入れる senators = deque(senate) #banの権利が使われた回数を保持する変数 r_banned_count = 0 d_banned_count = 0 #RとDの数(両党の党員数)を保持する変数 r = 0 d = 0 #RとDの数を数えてr,dに保持 for i in range(len(senate)): if senate[i] == "R": r += 1 if senate[i] == "D": d += 1 #権利行使可能な党員がいる限り繰り返す #一度権利行使した後も、再度キューsenatorsの最後尾に入ることで2,3ラウンド目へ進む while senators: #Radiant党員が0になったらDireを返す if r==0: return "Dire" #Dire党員が0になったらRadiantを返す if d==0: return "Radiant" #キューの先頭を取得して変数voterに保持 voter = senators.popleft() #voter(今回の権利行使者)がRなら if voter == "R": #Dire党員が行使したbanの権利が残っている場合 if r_banned_count > 0: #Radiant党員の残り人数をデクリメント r -= 1 #Dire党員に使われたbanの権利をデクリメント r_banned_count -= 1 #Dire党員が行使したbanの権利が0の場合 else: #Dire党員をbanする権利を使う d_banned_count += 1 #自分自身(voter)はキューの最後尾に入って次のラウンドを待つ senators.append(voter) #voterがDなら if voter == "D": #Radiant党員が行使したbanの権利がある場合 if d_banned_count > 0: #Dire党員の数を1減らす d -= 1 #Radiant党員が行使したbanの権利の数を1減らす d_banned_count -= 1 #Radiant党員が行使したbanの権利がない場合 else: #Radiant党員をbanする権利を使う r_banned_count += 1 #自分自身(voter)はキューの最後尾に入って次のラウンドを待つ senators.append(voter) |
終わりに
補足・参考・感想
問題を分類しました。テーマごとに集中して問題を解くことができます。
LeeetCodeの問題をアルゴリズムとデータ構造による分類
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。
他の問題もどうぞ
前:1207. Unique Number of Occurrences
コメント