【LEETCODE】模拟面试-294.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 twoconsecutive "++" 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.

input: a string with only + and - two kinds of characters output: for a given input, based on the game rule, return whether there is one strategy that can make the first player win, if yes, return true, if there is none, return false corner: when the string if null, return false

We will first change the string to a character array.

And apply Backtracking algorithm to solve it.

The starting point of the first player will iterate from 0 to arr.length - 2, when he finds two consecutive ++, he will soon change it into --.

Then the second player will do the same thing, so we pass current changed array to the second player, and he will receive a result: boolean otherWin = helper(arr);

If the second player will win, means he will return a true to upper level, the first player should recover his current strategy by change the -- to original ++, and keep moving i to next step, so that he can find other strategy that will make himself finally win the game, as long as there is just one strategy make it happen, the final result will be true, otherwise, it will be false.

public class Solution{
    public boolean canWin(String s){
        //corner
        if ( s == null || s.length() == 0 ){
            return false;
        }
        
        return helper(s.toCharArray());
    }
    
    public boolean helper(char[] arr){
        for ( int i = 0; i < arr.length; i++ ){
            if ( arr[i] == '+' && arr[i + 1] == '+' ){
                arr[i] = '-';
                arr[i + 1] = '-';
                
                boolean otherWin = helper(arr);         //2人轮流
                
                arr[i] = '+';               //返回到upper level后恢复+号
                arr[i + 1] = '+';
                
                if ( !otherWin ){           //另一人false时走这一步,另一人true时,要继续遍历++对
                    return true;            //直到找到某一种走法可以让另一人false,最终整体返回的值为true,此时第一人赢
                }
            }
        }
        
        return false;           //如果遍历到头没有++对了,而且几种走法都一直找不到赢的走法了,第一人就最终false
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ImportSource

厕读:每日一题,面试无忧

2. 下面关于java.lang.Exception类的说法正确的是() A 继承自Throwable B Serialable CD 不记...

36350
来自专栏谦谦君子修罗刀

程序员面试闪充--Block

1、介绍 Block是OC中非常重要的一种技术手段 ? 2、从c函数和oc函数的区别来定义block C函数写法:int add(int num1, int n...

29880
来自专栏老付的网络博客

Java反射超越泛型

在一次使用BeanUtils.copyProperties的方法是,莫名其妙的报错,产生的代码分解如下:

8510
来自专栏java学习

面试题59(关于数据结构之栈的理解)

面试题59 2018年1月11日 本期题目 (单选题)编号为123456789的火车经过如图11-1所示的轨道,从左边入口处移到右边出口处(每车必须且只能进临...

30640
来自专栏walterlv - 吕毅的博客

C#/.NET 匿名函数会捕获变量,并延长对象的生命周期

发布于 2018-01-05 01:26 更新于 2018-09...

10210
来自专栏工科狗和生物喵

【计算机本科补全计划】指令:计算机的语言(MIPS) --计算机组成原理

正文之前 今天的主题就是,重新学一次汇编语言,不过总感觉跟单片机的汇编语言没啥差别,不过就是地址变宽,然后一些限制多了不少,因为计算机要进行大量的运算,所以更加...

85970
来自专栏Java面试笔试题

简述一下你了解的设计模式

所谓设计模式,就是一套被反复使用的代码设计经验的总结(情境中一个问题经过证实的一个解决方案)。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠...

11240
来自专栏斑斓

Scala的面向对象与函数编程

很难说FP和OO孰优孰劣,应该依场景合理选择使用。倘若从这个角度出发,Scala就体现出好处了,毕竟它同时支持了OO和FP两种设计范式。 从设计角度看,我认为O...

31850
来自专栏大壮

iOS直播(基础篇)-rtmpdefine NALU_TYPE_SLICE 1define NALU_TYPE_DPA 2define NALU_TYPE_DPB 3define NALU_TYPE_

16720
来自专栏我的小碗汤

为什么在Go语言中要慎用interface{}

在掘金上看到一篇从java转Go思想上的变化以及对go语言思考的文章,写的很透彻,我也推敲了一遍。这里也分享给大家,或许对将要或者已经学习golang的同学有所...

15920

扫码关注云+社区

领取腾讯云代金券