LeetCode基础算法题第151篇:除数游戏

LeetCode基础算法题第151篇:除数游戏

首页休闲益智鲍勃的云竞赛更新时间:2024-04-18

技术提高是一个循序渐进的过程,所以我讲的leetcode算法题从最简单的level开始写的,然后> 到中级难度,最后到hard难度全部完。目前我选择C语言,Python和Java作为实现语言,因为这三种语言还是比较典型的。由于篇幅和> 精力有限,其他语言的实现有兴趣的朋友请自己尝试。

如果有任何问题可以在文章后评论或者私信给我。

如果有朋友希望我讲些其他话题,请在评论区留言或者私信给我。

持续分享,敬请关注。

LeetCode 1025. 除数游戏(Divisor Game)

问题描述:

爱丽丝和鲍勃在轮流玩一种游戏,爱丽丝首先开始。游戏是:

在黑板上有一个数字N,在每一回合中,玩家可以:

请写出一个函数判断爱丽丝是否会赢的比赛。假设爱丽丝和鲍勃一样聪明。

注: 1 <= N <= 1000。

示例:

C语言实现:

先看代码。

你没看错,就是一行。这是小学二年级的思维题。

我看到过一个类似的题目:

"有两盒数量相等的棋子,两人轮流拿棋子,每次只能从同一盒子里拿若干枚棋子,拿到最后一枚的就获胜。两人足够聪明,如果某人先拿,他数输还是赢?"

答案是输。

解这类题的关键是理解"一样聪明"的含义。它是指,A如果选择数字x,B也同样选数字x,不会选其他的数值。

再来分析N的取值。

我们将N分成如下两种情况。

第一种:N==1。

因为无法找到满足条件的x,爱丽丝会输;

第二种:1 < N <=1000。

这里面存在很多质数,如果一定要找到满足条件的x,那么x只能取1,这样对任何N都是满足的。

如果爱丽丝选择1,鲍勃一样聪明,也会选择1,那么这个过程就是N在不断的按1递减,最终会等于1,等到谁拿到变为1的N,谁就会输。

这就像我们给两个人分糖果,你一个他一个这样分。所以这是一个数的奇偶问题:

当N取偶数的时候,因为爱丽丝是先手,所以鲍勃总是最后拿到变为1的N。

当N取奇数的时候,因为爱丽丝是先手,最后还是爱丽丝会拿到变为1的N。

Java语言实现:

Java 的实现和C语言的实现一致,不再撰述。代码如下:

Python语言实现:

Python 的实现和C语言的实现一致,不再撰述。代码如下:

查看全文
大家还看了
也许喜欢
更多游戏

Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved