您的位置:首页 > 房产 > 家装 > 华为OD机试 - 报数问题 - 约瑟夫环(Java 2024 E卷 100分)

华为OD机试 - 报数问题 - 约瑟夫环(Java 2024 E卷 100分)

2024/12/23 6:32:18 来源:https://blog.csdn.net/guorui_java/article/details/142286032  浏览:    关键词:华为OD机试 - 报数问题 - 约瑟夫环(Java 2024 E卷 100分)

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中,刷题点这里

专栏导读

本专栏收录于《华为OD机试(JAVA)真题(E卷+D卷+A卷+B卷+C卷)》。

刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加入华为OD刷题交流群,每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景,发现新题目,随时更新,全天CSDN在线答疑。

一、题目描述

有n个人围成一圈,顺序排号为1~n。

从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。

二、输入描述

输入人数n(n < 1000)

三、输出描述

输出最后留下的是原来第几号

四、测试用例

测试用例1:

1、输入

2

2、输出

2

3、说明

报数序号为1的人最终报3,因此序号1的人退出圈子,最后剩下序号为2的那位

测试用例2:

1、输入

5

2、输出

4

3、说明

按照上述规则,最后剩下的人的编号为 4。

五、解题思路

1、约瑟夫环

这个问题是经典的“约瑟夫环”问题。在这个问题中,n 个人站成一圈,每个人按照顺序报数,报到 3 的人退出圈子,直到只剩下一个人为止。要解决这个问题,我们可以使用数组或链表模拟这个过程,也可以使用数学方法直接找到最后剩下的人的位置。

核心算法是从第一个人开始,顺序报数。每次移除报数到 3 的人,然后继续报数。通过一个索引变量和模运算来模拟环形的报数过程。

模运算处理循环:index = (index + 2) % size 的模运算用于处理圆圈结构,使得报数可以循环进行,即在列表末尾后又从头开始。

2、具体步骤

  1. 初始化圈子:将 n 个人的编号加入到一个数据结构中,形成一个环形队列,方便按照顺序报数和移除元素。
  2. 模拟报数过程:
    • 从第一个人开始报数,每数到 3 的人退出圈子。
    • 移除报数到 3 的人后,继续从下一个人开始报数,直到只剩下一个人。
    • 我们使用一个索引变量来记录当前报数的位置,利用模运算 (%) 来处理环形报数。
  3. 输出结果:循环结束后,列表中只剩下一个人,输出该人的编号。

3、时间复杂度

每次移除一个人,最多需要花费 O(n) 的时间,因为在最坏情况下需要遍历整个列表(比如在使用数组或链表时需要寻找并移除第 k 个元素)。

总共需要进行 n-1 次移除操作,因此时间复杂度是 O(n * n) = O(n^2)。

4、空间复杂度

O(n),因为需要存储 n 个人的编号。所有算法和数据结构(列表、链表)都需要占用线性空间来存储这些元素。

六、Java算法源码

public class OdTest01 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();  // 输入人数sc.close();// 调用解决约瑟夫环问题的函数int lastPerson = findLastPerson(n);System.out.println(lastPerson);}// 解决约瑟夫环问题,返回最后留下的人的编号public static int findLastPerson(int n) {LinkedList<Integer> circle = new LinkedList<>();// 初始化圈子,将1到n编号加入列表for (int i = 1; i <= n; i++) {circle.add(i);}int index = 0;  // 当前报数的位置// 模拟报数过程,直到只剩一个人while (circle.size() > 1) {// 找到要移除的人的位置,报数到3的人退出index = (index + 2) % circle.size();  // +2 是因为要报到3(报数从0开始计数)circle.remove(index);}// 返回最后剩下的人的编号return circle.get(0);}
}

七、效果展示

1、输入

7

2、输出

4

3、说明

模拟报数过程,最后剩下的人的编号为 4。

在这里插入图片描述


🏆下一篇:华为OD机试 - 简易内存池 - 逻辑分析(Java 2024 E卷 200分)

🏆本文收录于,华为OD机试(JAVA)真题(E卷+D卷+A卷+B卷+C卷)

刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加入华为OD刷题交流群,每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景,发现新题目,随时更新,全天CSDN在线答疑。

在这里插入图片描述

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com