win2008r2 iis配置网站,北仑营销型网站制作,phpcms做双语网站,门店零售管理系统文章目录 Find the Losers of the Circular Game 找出转圈游戏输家问题描述#xff1a;分析代码模拟 Tag Find the Losers of the Circular Game 找出转圈游戏输家
问题描述#xff1a;
n 个朋友在玩游戏。这些朋友坐成一个圈#xff0c;按 顺时针方向 从 1 到 n 编号。从… 文章目录 Find the Losers of the Circular Game 找出转圈游戏输家问题描述分析代码模拟 Tag Find the Losers of the Circular Game 找出转圈游戏输家
问题描述
n 个朋友在玩游戏。这些朋友坐成一个圈按 顺时针方向 从 1 到 n 编号。从第 i 个朋友的位置开始顺时针移动 1 步会到达第 (i 1) 个朋友的位置1 i n而从第 n 个朋友的位置开始顺时针移动 1 步会回到第 1 个朋友的位置。
游戏规则如下
第 1 个朋友接球。
接着第 1 个朋友将球传给距离他顺时针方向 k 步的朋友。然后接球的朋友应该把球传给距离他顺时针方向 2 * k 步的朋友。接着接球的朋友应该把球传给距离他顺时针方向 3 * k 步的朋友以此类推。
换句话说在第 i 轮中持有球的那位朋友需要将球传递给距离他顺时针方向 i * k 步的朋友。
当某个朋友第 2 次接到球时游戏结束。
在整场游戏中没有接到过球的朋友是 输家 。
给你参与游戏的朋友数量 n 和一个整数 k 请按升序排列返回包含所有输家编号的数组 answer 作为答案。 1 k n 50 1 k n 50 1kn50
分析 这个问题是一次周赛的Q1。 这样的问题很讨厌因为它太简单了直接模拟就可以了但是大部分的人潜意识中会被导向约瑟夫环。
没错当时这个问题花了近半小时虽然AC但是代码太挫了。
可能是周赛的影响今天的每日就很流畅。这个模拟需要注意的是它的No.是从1开始到n。而且是一个环所以取模是必然的。
这时候就需要一个长度n的标识数组来记录是否访问过。 所以编号为 i i i的人就会处于数组 i − 1 i-1 i−1的位置上。 那么下一个可以被访问的人 j ( i r ∗ k ) j (ir*k)%n j(ir∗k), i i i和 j j j都是索引。 在不停的访问中一定会终止即某个位置第二次被访问到。 此时把所有未被标记的位置从小到大的记录到结果中.
目前这个问题似乎没有纯数学的思路只能模拟。
代码 模拟
public int[] circularGameLosers(int n, int k) {boolean[] mark new boolean[n];int r 0;//圈数for(int i 0;!mark[i];i (ir*k)%n){mark[i] true;r;}int[] ans new int[n-r];for(int i0,j0;in;i){if(!mark[i]) ans[j] i1;}return ans;}时间复杂度 O ( N ) O(N ) O(N)
空间复杂度 O ( N ) O(N) O(N)
Tag
Array
Hash
