python leetcodeブラシ問題(41):1025.除数ゲーム
1568 ワード
タイトルの説明:
アリスはボブと一緒にゲームをして、彼らは流行しています.アリスが先頭に立った.
最初、黒板にはNという数字がありました.各プレイヤーのラウンドにおいて、プレイヤーは以下の操作を行う必要があります.
いずれかのxを選択し、0アリスがゲームで勝利した時だけTrueに戻る.そうしないとfalseに戻る.両方のプレイヤーが最適な状態でゲームに参加すると仮定します.
例1:
入力:2出力:true解釈:アリスは1を選択し、ボブは操作できません.例2:
入力:3出力:false解釈:アリスは1を選択し、ボブも1を選択し、アリスは操作できません.
ヒント:
1 <= N <= 1000
解題プロセス:
Nが奇数であれば、奇数の全ての因数が奇数であるため、Nが一度N−xの操作を行うと必ず偶数になるので、aが奇数を取った場合、bの番になったとき、bが偶数になるに違いない.このときbは-1を行い、aに奇数を返すだけで、このようにbはずっと偶数を取って、最後のbが必ず最小偶数2を取って、aは負けてしまう.
だから、ゲームが始まるとアリスがNを奇数にしたら、彼女は必ず負けます.つまりfalseです.Nを偶数にすると、彼女は-1だけでbobに奇数を取らせ、最後にbobは必ず負けて、結果はtrueです.
コメントエリアを見ると、動的な計画方法、基本的な考え方も使用できます.
N以下のすべての解を探し出し,前のものに基づいて後ろのものを繰り返す.
状態遷移:iの約数の中にFalseである(すなわち負ける場合)がある場合、現在のiはTrueであるべきである.ない場合はFalseです.
アリスはボブと一緒にゲームをして、彼らは流行しています.アリスが先頭に立った.
最初、黒板にはNという数字がありました.各プレイヤーのラウンドにおいて、プレイヤーは以下の操作を行う必要があります.
いずれかのxを選択し、0
例1:
入力:2出力:true解釈:アリスは1を選択し、ボブは操作できません.例2:
入力:3出力:false解釈:アリスは1を選択し、ボブも1を選択し、アリスは操作できません.
ヒント:
1 <= N <= 1000
解題プロセス:
Nが奇数であれば、奇数の全ての因数が奇数であるため、Nが一度N−xの操作を行うと必ず偶数になるので、aが奇数を取った場合、bの番になったとき、bが偶数になるに違いない.このときbは-1を行い、aに奇数を返すだけで、このようにbはずっと偶数を取って、最後のbが必ず最小偶数2を取って、aは負けてしまう.
だから、ゲームが始まるとアリスがNを奇数にしたら、彼女は必ず負けます.つまりfalseです.Nを偶数にすると、彼女は-1だけでbobに奇数を取らせ、最後にbobは必ず負けて、結果はtrueです.
class Solution:
def divisorGame(self, N: int) -> bool:
return N%2==0
コメントエリアを見ると、動的な計画方法、基本的な考え方も使用できます.
N以下のすべての解を探し出し,前のものに基づいて後ろのものを繰り返す.
状態遷移:iの約数の中にFalseである(すなわち負ける場合)がある場合、現在のiはTrueであるべきである.ない場合はFalseです.
class Solution:
def divisorGame(self, N: int) -> bool:
target = [0 for i in range(N+1)]
target[1] = 0 # 1，
if N<=1:
return False
else:
target[2] = 1 # 2，
for i in range(3,N+1):
for j in range(1,i//2):
# j i target[i-j] （0） ， （1）
if i%j==0 and target[i-j]==0:
target[i] = 1
break
return target[N]==1