【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]);
    }
}

目录
相关文章
|
7天前
|
安全 Android开发 Kotlin
Android经典面试题之Kotlin延迟初始化的by lazy和lateinit有什么区别?
**Kotlin中的`by lazy`和`lateinit`都是延迟初始化技术。`by lazy`用于只读属性,线程安全,首次访问时初始化;`lateinit`用于可变属性,需手动初始化,非线程安全。`by lazy`支持线程安全模式选择,而`lateinit`适用于构造函数后初始化。选择依赖于属性特性和使用场景。**
22 5
Android经典面试题之Kotlin延迟初始化的by lazy和lateinit有什么区别?
|
19小时前
|
SQL Java Unix
Android经典面试题之Java中获取时间戳的方式有哪些?有什么区别?
在Java中获取时间戳有多种方式,包括`System.currentTimeMillis()`(毫秒级,适用于日志和计时)、`System.nanoTime()`(纳秒级,高精度计时)、`Instant.now().toEpochMilli()`(毫秒级,ISO-8601标准)和`Instant.now().getEpochSecond()`(秒级)。`Timestamp.valueOf(LocalDateTime.now()).getTime()`适用于数据库操作。选择方法取决于精度、用途和时间起点的需求。
10 3
|
4天前
|
SQL 安全 Java
Android经典面试题之Kotlin中object关键字实现的是什么类型的单例模式?原理是什么?怎么实现双重检验锁单例模式?
Kotlin 单例模式概览 在 Kotlin 中,`object` 关键字轻松实现单例,提供线程安全的“饿汉式”单例。例如: 要延迟初始化,可使用 `companion object` 和 `lazy` 委托: 对于参数化的线程安全单例,结合 `@Volatile` 和 `synchronized`
15 6
|
6天前
|
XML Android开发 数据格式
Android面试题之DialogFragment中隐藏导航栏
在Android中展示全屏`DialogFragment`并隐藏状态栏和导航栏,可通过设置系统UI标志实现。 记得在布局文件中添加内容,并使用`show()`方法显示`DialogFragment`。
17 2
|
10天前
|
Android开发 Kotlin
Android面试题之kotlin中怎么限制一个函数参数的取值范围和取值类型等
在Kotlin中,限制函数参数可通过类型系统、泛型、条件检查、数据类、密封类和注解实现。例如,使用枚举限制参数为特定值,泛型约束确保参数为Number子类,条件检查如`require`确保参数在特定范围内,数据类封装可添加验证,密封类限制为一组预定义值,注解结合第三方库如Bean Validation进行校验。
22 6
|
10天前
|
Android开发
Android面试题之自定义View注意事项
在Android开发中,自定义View主要分为四类:直接继承View重写onDraw,继承ViewGroup创建布局,扩展特定View如TextView,以及继承特定ViewGroup。实现时需注意:支持wrap_content通过onMeasure处理,支持padding需在onDraw或onMeasure/onLayout中处理。避免在View中使用Handler,使用post系列方法代替。记得在onDetachedFromWindow时停止线程和动画以防止内存泄漏。处理滑动嵌套时解决滑动冲突,并避免在onDraw中大量创建临时对象。
16 4
|
8天前
|
Android开发
Android面试题之View的invalidate方法和postInvalidate方法有什么区别
本文探讨了Android自定义View中`invalidate()`和`postInvalidate()`的区别。`invalidate()`在UI线程中刷新View,而`postInvalidate()`用于非UI线程,通过消息机制切换到UI线程执行`invalidate()`。源码分析显示,`postInvalidate()`最终调用`ViewRootImpl`的`dispatchInvalidateDelayed`,通过Handler发送消息到UI线程执行刷新。
17 1
|
11天前
|
Android开发 Kotlin
Android面试题之 Kotlin中退出迭代器的方式有哪些
在Android和Kotlin中,遍历集合时可使用迭代器结合`break`提前终止循环。例如,使用`while`和迭代器,或用`forEach`配合`return@forEach`来中断遍历。若需退出外层函数,可定义自定义标签。在遍历并删除元素时,这些技巧尤其有用。
16 3
|
12天前
|
算法 Java
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
21 1
|
5天前
|
Android开发 Kotlin
Android经典面试题之Kotlin中Lambda表达式有哪些用法
Kotlin的Lambda表达式是匿名函数的简洁形式,常用于集合操作和高阶函数。基本语法是`{参数 -&gt; 表达式}`。例如,`{a, b -&gt; a + b}`是一个加法lambda。它们可在`map`、`filter`等函数中使用,也可作为参数传递。单参数时可使用`it`关键字,如`list.map { it * 2 }`。类型推断简化了类型声明。
8 0