【Android面试】使用Java,有n个人(编号1~n围成一圈),从编号为1的开始报数,从1报数到m,报到m的人出去,下一个人继续从1开始报数,通过算法求最后一个留下的人的编号为多少

简介: 比如n=3,m=4有3个人,从1报到4第一次出队:1号第二次出队:3号最后留下:2号

比如n=3,m=4

有3个人,从1报到4

第一次出队:1号

第二次出队:3号

最后留下:2号

使用链表来做最方便。


import java.util.Scanner;
public class LastOneStanding {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入人数n和报数范围m:");
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] nums = new int[n]; // 存储每个人的编号
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        int lastIdx = 0; // 最后一个留下的人的编号初始化为0
        while (nums.length > 1) { // 当链表长度大于1时,继续循环
            int startIdx = 0; // 从哪个位置开始报数
            if (lastIdx == nums.length - 1) { // 如果上一个人是最后一个离开的人,从头开始报数
                startIdx = 0;
            } else { // 否则从上一个人的下一个位置开始报数
                startIdx = lastIdx + 1;
            }
            for (int i = startIdx; i < nums.length; i++) { // 从指定位置开始报数
                if (i == m) { // 如果报到m的人出去了,更新链表头指针和剩余人数
                    int nextIdx = nums[i % nums.length];
                    nums[0] = nextIdx;
                    lastIdx = 0;
                    if (nums.length == 1) { // 如果链表长度为1,说明只剩下一个人了,输出他的编号
                        System.out.println(nums[0]);
                        break;
                    }
                    nums[1] = nums[nums.length - 1]; // 将尾节点接在头节点后面,形成一个单节点的循环链表
                    nums[nums.length - 1] = 0; // 将尾节点置为0,表示已经删除掉该节点
                    nums[0] = i + 1; // 将新节点的编号设为i+1,表示该节点是新的头节点
                } else { // 如果没有报到m的人,将当前节点的编号加入到剩余人数中,并更新链表头指针和剩余人数
                    lastIdx++;
                }
            }
        }
        System.out.println("最后留下的人的编号为:" + nums[0]);
    }
}

目录
相关文章
|
21天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
57 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
1天前
|
存储 缓存 Oracle
Java I/O流面试之道
NIO的出现在于提高IO的速度,它相比传统的输入/输出流速度更快。NIO通过管道Channel和缓冲器Buffer来处理数据,可以把管道当成一个矿藏,缓冲器就是矿藏里的卡车。程序通过管道里的缓冲器进行数据交互,而不直接处理数据。程序要么从缓冲器获取数据,要么输入数据到缓冲器。
Java I/O流面试之道
|
19天前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
22天前
|
存储 安全 算法
Java面试题之Java集合面试题 50道(带答案)
这篇文章提供了50道Java集合框架的面试题及其答案,涵盖了集合的基础知识、底层数据结构、不同集合类的特点和用法,以及一些高级主题如并发集合的使用。
58 1
Java面试题之Java集合面试题 50道(带答案)
|
10天前
|
存储 Java 程序员
Java面试加分点!一文读懂HashMap底层实现与扩容机制
本文详细解析了Java中经典的HashMap数据结构,包括其底层实现、扩容机制、put和查找过程、哈希函数以及JDK 1.7与1.8的差异。通过数组、链表和红黑树的组合,HashMap实现了高效的键值对存储与检索。文章还介绍了HashMap在不同版本中的优化,帮助读者更好地理解和应用这一重要工具。
29 5
|
9天前
|
存储 Java
[Java]面试官:你对异常处理了解多少,例如,finally中可以有return吗?
本文介绍了Java中`try...catch...finally`语句的使用细节及返回值问题,并探讨了JDK1.7引入的`try...with...resources`新特性,强调了异常处理机制及资源自动关闭的优势。
14 1
|
13天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
18天前
|
Java 程序员
Java 面试高频考点:static 和 final 深度剖析
本文介绍了 Java 中的 `static` 和 `final` 关键字。`static` 修饰的属性和方法属于类而非对象,所有实例共享;`final` 用于变量、方法和类,确保其不可修改或继承。两者结合可用于定义常量。文章通过具体示例详细解析了它们的用法和应用场景。
22 3
|
18天前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
22天前
|
Java
Java面试题之cpu占用率100%,进行定位和解决
这篇文章介绍了如何定位和解决Java服务中CPU占用率过高的问题,包括使用top命令找到高CPU占用的进程和线程,以及使用jstack工具获取堆栈信息来确定问题代码位置的步骤。
59 0
Java面试题之cpu占用率100%,进行定位和解决