求助,为什么10 40 的case 结果是false?


  • -3
    B

    想请问一下大家10 40的结果是返回true 还是FALSE啊?谢谢啦


  • 2
    D

    因为数字是不能重复使用的,我估计你是用的可重复使用来做的吧。。


  • 0
    Z

    @bingkunyang See the code below. I marked the line, which will cause your problem if commented. I made the same mistake.

    class Solution {
    public:
        bool canIWin(int maxChoosableInteger, int desiredTotal) {
            int n = maxChoosableInteger, tar = desiredTotal, sum = 0;
            for (int i = 1; i <= n; ++i) sum += i;
            if (tar > sum) return false;
            unordered_map<int, bool> dp;
            vector<int> used(n, 1);
            return helper(used, dp, 0, tar);
        }
    private:
        bool helper(vector<int>& used, unordered_map<int, bool>& dp, int key, int tar) {
            int n = used.size();
            if (dp.count(key)) return dp[key];
            for (int i = n-1; i >= 0; --i) {
                if (used[i]) {
                    if (i+1 >= tar) {
                        dp[key] = true;
                        return true;
                    }
                    used[i] = 0;
                    if (!helper(used, dp, key|(1<<i), tar-i-1)) {
                        dp[key] = true;
                        // if next line commented, it won't pass test case (10, 40) 
                        used[i] = 1;
                        return true;
                    }
                    used[i] = 1;
                }
            }
            dp[key] = false;
            return false;
        }
    };
    

  • 0
    B

    @bingkunyang 直接拿7的话,对手会拿4,你就不能再拿7了。简单地说。very tricky here.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.