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

package com.company;import java.util.*;class Solution {    // 参考了下面的解法:    // https://discuss.leetcode.com/topic/68773/java-solution    // 开始没有用dp,超时了    // discuss里面解法太牛逼了,用位图来作为key记录    // 用Boolean而不是boolean来做数组,可以充分利用null的初始值    // 其中 ^= 异或也用的非常好,非常到位,返回的时候也很好    Boolean[] gotList;    int m;    int key;    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {        if ((1+maxChoosableInteger)*maxChoosableInteger < desiredTotal) {            return false;        }        m = maxChoosableInteger;        key = 0;        gotList = new Boolean[1 << m];        return win(desiredTotal);    }    private boolean win(int d) {        if (gotList[key] != null) {            return gotList[key];        }        for (int i=0; i
     
      << i;            if ((key & bit) == 0) {                if (i+1 >= d) {                    gotList[key] = true;                    return true;                }                key ^= bit;                boolean tmp = false;                if (!win(d-i-1)) {                    tmp = true;                }                key ^= bit;                if (tmp) {                    gotList[key] = true;                    return true;                }            }        }        gotList[key] = false;        return false;    }}public class Main {    public static void main(String[] args) throws InterruptedException {        System.out.println("Hello!");        Solution solution = new Solution();        // Your Codec object will be instantiated and called as such:        int maxChoosableInteger = 18;        int desiredTotal = 79;        boolean ret = solution.canIWin(maxChoosableInteger, desiredTotal);        System.out.printf("ret:%b\n", ret);        System.out.println();    }}