[292] Nim Game (2019 年 3 月 12 日, E)
有一堆石头, 游戏规则是每次可以从里面拿 1-3 颗石头, 拿到最后的石头的人赢. 你和你的对手都 optimal 的玩这个游戏, 问先手 (也就是你) 能不能赢得这个比赛.
题解: 我本来写的是 dfs + memo, 但是没想到这个题数字太大了. 容易爆栈. 后来通过看 discuss 和观察, 发现, 这个题, 只要不是 4 的倍数, 先手都能赢得比赛.
- class Solution {
- public:
- bool canWinNim(int n) {
- return n % 4 != 0;
- }
- };
[375] Guess Number Higher or Lower II
[464] Can I Win(2019 年 2 月 20 日, 谷歌 tag,M)
给了一个 1-100 的游戏, 游戏规则是, 两个选手, player1 每次从 1-100 中抽取一个数字, player2 每次也从 1-100 中抽取一个数字, 不能重复抽取相同的数字. 直到某个 player 抽取到一个数, 所有轮次中每个 player 抽取的数字加和大于等于 target(target 是提前给定的). 问 player1 能不能赢这个游戏.
本题的题目意思是把 100 换成一个变量叫做 maxChoosableInteger. 问 player1 能不能赢这个游戏.
题解: 这是一棵博弈树的问题. 解空间如下图:
裸的 dfs 搜索方法如下: 对于当前的局面, 我们尝试用一个没有用过的数作为当前的解, 然后 dfs 到下一个局面.
如果下个局面返回了 false, 就是对手不能赢, 那我肯定非常高兴的马上返回了 true, 因为这个局面我能赢.(注意返回的时候要把当前局面用过的数字清空. 回溯. 不能忘.)
但是如果下个局面返回了 true, 我就会认真反思自己, 然后后悔当前局面的走法 (是的, 就是这么的无赖) 去换一种新的走法.
那么对于当前局面的前一个局面来说, 对手看到我返回了 true, 那他也可以反悔啊, 他内心 os: 老子也不这么走了, 我也要换一个走法. 于是他就继续遍历他解空间的下一个解, 直到他在当前空间找到了一个解, 这个解能让他在当前空间赢, 或者他找遍了所有的可能解, 都赢不了, 他只好认输,"我在当前空间赢不了, 我返回 false".
- class Solution {
- public:
- bool canIWin(int maxChoosableInteger, int desiredTotal) {
- if (desiredTotal <= 0) {return true;}
- if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 <desiredTotal) {return false;}
- string used(maxChoosableInteger, '0');
- int sum = 0;
- return canIWin(maxChoosableInteger, desiredTotal, sum, used);
- }
- bool canIWin(int maxChoosableInteger, int desiredTotal, int sum, string& used) {
- if (sum>= desiredTotal) {return false;}
- for (int i = 1; i <= maxChoosableInteger; ++i) {
- if (used[i-1] == '1') { continue; } // 如果当前的数用过了, 那么就换下一个能用的数
- used[i-1] = '1';
- if (canIWin(maxChoosableInteger, desiredTotal, sum + i, used) == false) {
- // 到这里需要回溯. 如果下一个局面为 false 的话, 就说明当前局面能赢.
- // 但是你想象一下如果你是一个玩家, 当对手告诉你这个局面对手能赢的时候, 你会怎么做,
- // 肯定是返回到一个有一个解 - 对手不能赢的层次, 然后去 dfs 那个解空间.
- used[i-1] = '0';
- return true;
- }
- used[i-1] = '0';
- }
- return false;
- }
- };
- View Code
再加上可以记忆化或者状态压缩的技巧. 用个 memo.
- class Solution {
- public:
- bool canIWin(int maxChoosableInteger, int desiredTotal) {
- if (desiredTotal <= 0) {return true;}
- if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 <desiredTotal) {return false;}
- string used(maxChoosableInteger, '0');
- int sum = 0;
- return canIWin(maxChoosableInteger, desiredTotal, sum, used, 0);
- }
- unordered_map<string, bool> memo;
- bool canIWin(int maxChoosableInteger, int desiredTotal, int sum, string& used, int player) {
- if (sum>= desiredTotal) {return false;}
- if (memo.find(used) != memo.end()) {return memo[used];}
- string key = used;
- memo[key] = false;
- for (int i = 1; i <= maxChoosableInteger; ++i) {
- if (used[i-1] == '1') { continue; }
- used[i-1] = '1';
- if (canIWin(maxChoosableInteger, desiredTotal, sum + i, used, 1 - player) == false) {
- memo[key] = true;
- used[i-1] = '0';
- return true;
- }
- used[i-1] = '0';
- }
- return false;
- }
- };
- View Code
[486] Predict the Winner
[843] Guess the Word(2019 年 3 月 12 日, google tag)
给了一个 wordlist 猜单词, 给了一个 API , 叫做 int guess(string Word), 返回我们的 target 单词有多少个位置和 Word match.
For each test case, you have 10 guesses to guess the Word. At the end of any number of calls, if you have made 10 or Less calls to master.guess and at least one of these guesses was the secret, you pass the testcase.
题解: 这道题不难, 其实主要是这种交互式的问题在 leetcode 上第一次出现.
intuition: 我们先随机选一个单词 Word, 然后利用返回值 x, 如果 target 和 Word match 的有 x, 那么我们只需要选择在 list 中和 Word match x 个位置的单词, 这个作为我们下次选择的集合.
这么做能 ac.
但是可以优化: 如果说我们随机选一个单词, 但是如果 返回值 x == 0 的话, 那么其实剩下的解可能很多. 我们试图找一个单词, 与这个单词有 0 个 match 的单词解的集合最小就行了.
- /**
- *// This is the Master's API interface.
- *// You should not implement it, or speculate about its implementation
- * class Master {
- * public:
- * int guess(string Word);
- * };
- */
- class Solution {
- public:
- void findSecretWord(vector<string>& wordlist, Master& master) {
- for (int t = 0; t <10; ++t) {
- int n = wordlist.size();
- unordered_map<string, int> mp;
- for (int i = 0; i <n; ++i) {
- for (int j = i + 1; j < n; ++j) {
- if (calMatch(wordlist[i], wordlist[j]) == 0) {
- mp[wordlist[i]]++;
- }
- }
- }
- pair<string, int> minmax = make_pair(wordlist[0], 1000);
- for (auto& p : mp) {
- if (p.second <minmax.second) {minmax = p;}
- }
- int x = master.guess(minmax.first);
- if (x == 6) {return;}
- vector<string> list2;
- for (auto& w : wordlist) {
- if (calMatch(w, minmax.first) == x) {
- list2.push_back(w);
- }
- }
- wordlist = list2;
- }
- }
- int calMatch(string& s, string& t) {
- int match = 0;
- for (int i = 0; i < s.size(); ++i) {
- if (s[i] == t[i]) {match++;}
- }
- return match;
- }
- };
- View Code
[913] Cat and Mouse
来源: http://www.bubuko.com/infodetail-2985417.html