[問題] leetcode 464 can i win
看板Prob_Solve (計算數學 Problem Solving)作者powertodream (The Beginning)時間7年前 (2017/05/16 18:08)推噓3(3推 0噓 0→)留言3則, 2人參與討論串1/4 (看更多)
https://leetcode.com/problems/can-i-win/#/description
是兩個人互相取數字, 當第一個人取的數字超過目標, 就return true
原本的想法是, player 1 挑全部沒選過的number, 然後 呼叫secondPlayerWin的
function
去判斷是不是有存在secondPlayer win的, 只要有存在A 選的這個number就是不行的
不過寫不太好的吃了個wrong answer,
偷看看討論串解答
看了很多的作法, 都是做類似
!helper(desiredTotal - i)
的遞迴,
想半天仍然不太懂... 有版友有興趣一起研究研究嗎?
這個是原作者的解釋, 但是我仍然不懂他的意思, 為什麼code要寫成那樣
**
The strategy is we try to simulate every possible state. E.g. we let this
player choose any unchosen number at next step and see whether this leads to
a win. If it does, then this player can guarantee a win by choosing this
number. If we find that whatever number s/he chooses, s/he won't win the
game, then we know that s/he is guarantee to lose given such a state.
// try every unchosen number as next step
for(int i=1; i<used.length; i++){
if(!used[i]){
used[i] = true;
// check whether this lead to a win, which means
helper(desiredTotal-i) must return false (the other player lose)
if(!helper(desiredTotal-i)){
map.put(key, true);
used[i] = false;
return true;
}
used[i] = false;
}
}
map.put(key, false);
--
If people do not believe that mathematics is simple,
it is because they do not realize how complicated life is.
-- John Louis von Neumann
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.152.192
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1494929293.A.486.html
推
05/16 20:51, , 1F
05/16 20:51, 1F
推
05/17 00:23, , 2F
05/17 00:23, 2F
推
05/17 16:18, , 3F
05/17 16:18, 3F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
