1 public class Solution {
2 public boolean canWin(String s) {
3 if (s ==
null || s.length() <= 1
) {
4 return false;
5 }
6 ArrayList<String> validMoves =
getValidMoves(s);
7 if (validMoves.isEmpty()) {
8 return false;
9 }
10 for (String str : validMoves) {
11 if (!
canWin(str)) {
12 return true;
13 }
14 }
15 return false;
16 }
17
18 private ArrayList<String>
getValidMoves(String s) {
19 ArrayList<String> result =
new ArrayList();
20 for (
int i = 0; i < s.length() - 1; i++
) {
21 if (s.charAt(i) == '+' && s.charAt(i + 1) == '+'
) {
22 char[] tmp =
s.toCharArray();
23 tmp[i] = '-'
;
24 tmp[i + 1] = '-'
;
25 result.add(
new String(tmp));
26 }
27 }
28 return result;
29 }
30 }
Google 面经题
之前和聪喵喵复习LinkedIn面经can i win, 同样的思路也可以用在这道题
此类轮流操作的游戏问题也可以使用枚举法解决,关键在于第11行!canWin(str),表示对于当前选择对手必输，那么当前选择为必胜策略
转载于:https://www.cnblogs.com/ilovenaomi/p/4885109.html
