技术提高是一个循序渐进的过程,所以我讲的leetcode算法题从最简单的level开始写的,然后> 到中级难度,最后到hard难度全部完。目前我选择C语言,Python和Java作为实现语言,因为这三种语言还是比较典型的。由于篇幅和> 精力有限,其他语言的实现有兴趣的朋友请自己尝试。
如果有任何问题可以在文章后评论或者私信给我。
如果有朋友希望我讲些其他话题,请在评论区留言或者私信给我。
持续分享,敬请关注。
LeetCode 1025. 除数游戏(Divisor Game)
问题描述:爱丽丝和鲍勃在轮流玩一种游戏,爱丽丝首先开始。游戏是:
在黑板上有一个数字N,在每一回合中,玩家可以:
请写出一个函数判断爱丽丝是否会赢的比赛。假设爱丽丝和鲍勃一样聪明。
注: 1 <= N <= 1000。
示例:先看代码。
你没看错,就是一行。这是小学二年级的思维题。
我看到过一个类似的题目:
"有两盒数量相等的棋子,两人轮流拿棋子,每次只能从同一盒子里拿若干枚棋子,拿到最后一枚的就获胜。两人足够聪明,如果某人先拿,他数输还是赢?"
答案是输。
解这类题的关键是理解"一样聪明"的含义。它是指,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 的实现和C语言的实现一致,不再撰述。代码如下:
Python 的实现和C语言的实现一致,不再撰述。代码如下:
Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved