牛牛和牛妹的取球游戏

[编程题]牛牛和牛妹的取球游戏

热度指数：218 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛和牛妹在玩一个取球游戏，有若干个球放置在一个竖直透明的圆柱体中，圆柱体的横截面积恰好与每个球的横截面积相同。这些球只有两种颜色，一种是红色，一种是黑色。

轮到每个人的回合时，每次可以取出其中的两个球，但是需要满足每次取出时只能拿走相邻的两个不同颜色的球。因为这两个球被取出，其他球可能会由于重力的作用而下落。

每次游戏牛牛都是先手，而牛妹是后手。两人交替取球，如果轮到某个人在自己的回合内无法取球，那么判定那个人输。牛牛和牛妹都不想输，所以他们每一步都会采取最优策略。

为了简化该问题，给定你一串由R和B组成的字符串，分别代表红球和黑球，字符串的排列顺序与圆柱体从下往上的排列一致，请你写一个程序，来判定谁会获得胜利，如果牛牛获得胜利，返回"niuniu"，反之，返回"niumei"。

示例1

输入

"BBBB"

输出

"niumei"

说明

牛牛先手，但是在他的回合内无法取球，所以牛妹胜利。

示例2

输入

"RRBB"

输出

"niumei"

说明

牛牛先手，拿走了"RB"，然后牛妹也拿走了"RB"，这时该字符串为空，牛牛在他的回合内无法取球，所以牛妹胜利。

备注:

算法知识视频讲解

Java

苏沐沐橙

public String getBall (String s) {
        // write code here
        Stack<Character> stack = new Stack<>();
        int count = 0;
        for(char ch : s.toCharArray()){
            if(!stack.isEmpty() && stack.peek() != ch){
                stack.pop();
                count ++;
            }else{
                stack.push(ch);
            }
        }
        return count % 2 == 0 ? "niumei" : "niuniu";
    }

发表于 2021-07-14 20:33:06 回复(0)