LintCode 硬币排成线题目分析代码

题目

有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币,直到没有硬币为止。拿到最后一枚硬币的人获胜。

请判定 第一个玩家 是输还是赢?

** 样例 ** n = 1, 返回 true.

n = 2, 返回 true.

n = 3, 返回 false.

n = 4, 返回 true.

n = 5, 返回 true.

分析

这道题是典型的博弈论,显然每次我们都是三个三个循环,如果我先拿,我拿一个,对方可以拿两个,我拿两个,对方可以拿一个,所以如果总数是三的倍数的话,肯定是对方获胜,所以答案就出来了,n不能是三的倍数

代码

public class Solution {
    /**
     * @param n: an integer
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int n) {
        // write your code here
        return n%3!=0; 
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开发 & 算法杂谈

凸包问题之GrahamScan解法

当沿着Convex hull逆时针漫游时,总是向左转在极坐标系下按照极角大小排列,然后逆时针方向漫游点集,去除非Convex hull顶点(非左 转点)。

994
来自专栏小樱的经验随笔

浅谈String模块ascii_letters和digits

本文介绍string模块ascii_letters和digits方法,其中ascii_letters是生成所有字母,从a-z和A-Z,digits是生成所有数字...

4337
来自专栏数据结构与算法

7828:最大公约数与最小公倍数

7828:最大公约数与最小公倍数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 两个正整数的最大公约数是G,最小公倍数是...

4638
来自专栏数据结构与算法

牛客NOIP提高组(二)题解

好难啊,$30$分的枚举颜色dp应该比较好想把,$f[i][j]$表示第$i$个位置,填了$j$个颜色,然后先枚举一下$1$的颜色,前缀和优化一下,$O(n a...

1111
来自专栏数据结构与算法

1226 倒水问题

1226 倒水问题 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 有两个无刻...

2866
来自专栏java一日一条

Java8 HashMap实现原理探究

前言:Java8之后新增挺多新东西,在网上找了些相关资料,关于HashMap在自己被血虐之后痛定思痛决定整理一下相关知识方便自己看。图和有些内容参考的这个文章:...

1652
来自专栏欢乐玩转技术

Leetcode 137. 只出现一次的数字 II - 题解

https://leetcode.com/problems/single-number-ii/

8444
来自专栏落影的专栏

程序员进阶之算法练习(二)

前言 看完题目大意,先思考,再看解析;觉得题目大意不清晰,点击题目链接看原文。 A 题目链接 题目大意:n个点,坐标x[i]从小到大,每个点可以选择Le...

3056
来自专栏Python中文社区

Python文档精要研读系列:hash函数

hash(object) Return the hash value of the object (if it has one). Hash values ar...

25210
来自专栏小樱的经验随笔

Codeforces Round #412 (rated, Div. 2, base on VK Cup 2017 Round 3)(A.B.C,3道暴力题,C可二分求解)

A. Is it rated? time limit per test:2 seconds memory limit per test:256 megabyte...

3747

扫码关注云+社区

领取腾讯云代金券