-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.java
More file actions
35 lines (30 loc) · 1.2 KB
/
Solution.java
File metadata and controls
35 lines (30 loc) · 1.2 KB
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
package leetCode_464;
import java.util.HashMap;
/**
* @author dimdark
* @date 2017-09-25
* @time 9:51 PM
*/
public class Solution {
private boolean calculateResult(int currentState, int maxNumber, int desiredTotal,
HashMap<Integer, Boolean> statesMap) {
if (statesMap.containsKey(currentState)) return statesMap.get(currentState);
for (int i = 0; i < maxNumber; ++i) {
if ((currentState & (1 << i)) == 0) { // not contain
int nextState = currentState | 1 << i;
if ((i + 1) >= desiredTotal || !calculateResult(nextState, maxNumber,
desiredTotal - (i + 1), statesMap)) {
statesMap.put(currentState, true);
return true;
}
}
}
statesMap.put(currentState, false);
return false;
}
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
if (desiredTotal <= 0) return true;
if (maxChoosableInteger * (maxChoosableInteger + 1) >> 1 < desiredTotal) return false;
return calculateResult(0, maxChoosableInteger, desiredTotal, new HashMap<Integer, Boolean>());
}
}