LeetCode 294. Flip Game II
原题链接在这里:https://leetcode.com/problems/flip-game-ii/
题目:
You are playing the following Flip Game with your friend: Given a string that contains only these two characters: +
and -
, you and your friend take turns to flip two consecutive "++"
into "--"
. The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to determine if the starting player can guarantee a win.
For example, given s = "++++"
, return true. The starting player can guarantee a win by flipping the middle "++"
to become "+--+"
.
Follow up:
Derive your algorithm's runtime complexity.
题解:
若是有一段"++", 剩下的段和"--"组合 can not win, 那么返回true.
从头到尾试遍了没找到这么一段"++", 返回false.
Time Complexity: exponential.
T(n) = (n-2) * T(n-2) = (n-2) * (n-4) * T(n-4) = O(n!!)
AC Java:
public class Solution {
public boolean canWin(String s) {
for(int i = 1; i<s.length(); i++){
if(s.charAt(i) == '+' && s.charAt(i-1) == '+' && !canWin(s.substring(0, i-1) + "--" + s.substring(i+1))){
return true;
}
}
return false;
}
}
类似Flip Game.
最新文章
- Windows Store App 全球化:应用中设置语言选项
- 根据不同分辨率加载不同 css 样芪表
- fir.im Weekly - 从零开始创建 Android 新项目
- SharePoint 2013 Installation and Configuration Issues
- Linux Linux程序练习七
- input子系统分析
- bzoj 1501: [NOI2005]智慧珠游戏 Dancing Link
- 176. [USACO Feb07] 奶牛聚会
- StoryBoard 加入一个自定义View
- Javascript 学习 笔记一
- JavaScript 中的事件流和事件处理程序(读书笔记思维导图)
- [HMLY]12.iOS中的Protocol
- JavaBean,List,Map,json格式之间转化方式
- 关于web资金系统提现安全保护,防止极快的重复并发请求导致重复提现的解决思路
- 【ASP.NET Core快速入门】(七)WebHost的配置、 IHostEnvironment和 IApplicationLifetime介绍、dotnet watch run 和attach到进程调试
- C++题解:Matrix Power Series ——矩阵套矩阵的矩阵加速
- Failure to transfer org.apache.maven:maven-archiver:pom:2.5 from https://repo.maven.apache.org/maven2 was cached in the local repository, resolution will not be reattempted until the update interval o
- ruby安装及升级
- Redis学习---Redis操作之Hash
- hive 日志