LeetCode 294. 翻转游戏 II（记忆化递归）

Michael阿明

发布于 2021-02-19 10:20:47

5810

发布于 2021-02-19 10:20:47

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

你和朋友玩一个叫做「翻转游戏」的游戏，游戏规则：给定一个只有 + 和 - 的字符串。你和朋友轮流将 连续的两个 "++" 反转成 "--"。当一方无法进行有效的翻转时便意味着游戏结束，则另一方获胜。

请你写出一个函数来判定起始玩家是否存在必胜的方案。

示例：
输入: s = "++++"
输出: true 
解析: 起始玩家可将中间的 "++" 翻转变为 "+--+" 从而得胜。
延伸：
请推导你算法的时间复杂度。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/flip-game-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

class Solution {
	unordered_map<string,bool> m;
public:
    bool canWin(string s) {
        if(s.size() <= 1) return false;
    	if(m.count(s)) return m[s];
    	string t;
    	for(int i = 0; i < s.size()-1; ++i)
    	{
    		if(s[i]=='+' && s[i+1]=='+')
    		{
    			t = s;
    			t[i]=t[i+1]='-';
    			if(!canWin(t))
    			{
    				m[s] = true;
                    return true;
    			}
    		}
    	}
        m[s] = false;
    	return false;
    }
};

40 ms 11.8 MB

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/07/24 ，如有侵权请联系 cloudcommunity@tencent.com 删除

游戏