Re: [問題] leetcode 464 can i win

作者: cutekid (可愛小孩子)   2017-05-17 17:19:19
Retrograde Method: http://codepad.org/i3CsFKnT (Perl)
不知道有沒有寫錯
還請各位幫我看看
※ 引述《powertodream (The Beginning)》之銘言:
: 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);
作者: powertodream (The Beginning)   2017-05-18 00:58:00
看不懂 可以分享想法嗎?

Links booklink

Contact Us: admin [ a t ] ucptt.com