leetcode-can-i-win

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/can-i-win/

　　一种博弈游戏，甲乙二人分别从1….n中取数字，要求不重复取，有一个公共的累积和sum，每次两人取完数字之后sum值增加，如果谁某次取完之后sum>=total，那么他赢了。n和total都是题目给定的值。假定二人都是足够的聪明，你是甲作为先手，判断你是否能够取胜。

题目分析

　　记忆化搜索，注意n个数字取或不取的状态要用一个位保存，map中key是sum和s，value是true/false，至于如何保证根据sum和s生成key的唯一性，注意到n不超过20，total不超过300，n和total拼接成的二进制串也不会超过32，因此用位移并拼接就可以了。更详细的步骤可以看下注释。

代码

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
59
60
61
62
63
64
65
public class Solution {
    
    private int s; // 全局状态，每个数字的取法用0/1表示
    private Map<String, Boolean> map;
    
    private String generateKey(int sum, int s) {
        for (int i = 1; i <= 20; i++) {
            sum <<= 1;
        }
        sum = s | sum;
        return String.valueOf(sum);
    }
    
    // 判断先手是否必输，必输返回true，否则返回false
    private boolean dfs(int sum, int maxC, int total) {
        if (total > ((maxC *(maxC + 1)) / 2)) { // 此时连所有可选数的总和都小于total，那么谁都赢不了，因此必输
            return true;
        }
        String key = generateKey(sum, s); // key需要唯一
        if (map.containsKey(key)) {
            return map.get(key);
        }
        // 先手随便选，尽可能找到一种情况非必输，就赢了
        for (int i = 1; i <= maxC; i++) {
            if ((s & (1 << i)) != 0) {
                continue;
            }
            if (sum + i >= total) { //选择的i加上sum大于等于total，直接非必输了
                map.put(key, false);
                return false;
            }
            s = (s | (1 << i));
            boolean ret = true; // 判断本次i是否能赢
            for (int j = 1; j <= maxC; j++) {
            	if ((s & (1 << j)) != 0) {
            		continue;
            	}
                if (sum + i + j >= total) {
                    ret = false;
                    break;
                }
                s = (s | (1 << j));
                boolean tmp = dfs(sum + i + j, maxC, total);
                s = (s & (~(1 << j)));
                if (tmp == true) {
                    ret = false;
                    break;
                }
            }
            s = (s & (~(1 << i)));
            if (ret) { // 如果本次i能赢，直接就返回非必输就可以了
                map.put(key, false);
                return false;
            }
        }
        map.put(key, true);
        return true;
    }
    
    public boolean canIWin(int maxChoosableInteger, int maxChoosableInteger) {
        s = 0;
        map = new HashMap<String, Boolean>();
        return !dfs(0, maxChoosableInteger, desiredTotal); // 题目返回的是先手是否能赢
    }
}

　　时间复杂度：O(maxChoosableInteger^3 * maxChoosableInteger)