← 返回目录

编号为 1-n 的循环报 1-3,报道 3 的出列,求最后一人的编号

第 5 / 9 卷日期:

uniqueInstance 采用 volatile 关键字修饰也是很有必要的, uniqueInstance = new Singleton(); 这段代码其实是分为三步执行:

  1. 为 uniqueInstance 分配内存空间
  2. 初始化 uniqueInstance
  3. 将 uniqueInstance 指向分配的内存地址

但是由于 JVM 具有指令重排的特性,执行顺序有可能变成 1->3->2。指令重排在单线程环境下不会出现问题,但是在多线程环境下会导致一个线程获得还没有初始化的实例。例如,线程 T1 执行了 1 和 3,此时 T2 调用

getUniqueInstance () 后发现 uniqueInstance 不为空,因此返回 uniqueInstance,但此时 uniqueInstance 还未被初始化。

这种方式实现起来较麻烦,但同样线程安全,支持延时加载。

推荐阅读:Java 并发常见面试题总结(中)。

编号为 1-n 的循环报 1-3,报道 3 的出列,求最后一人的编号

标准的约瑟夫环问题。有 n 个人围成一个圈,从某个人开始报数,报到某个特定数字(本题中为 3)时该人出圈,直到只剩下一个人为止。

解决约瑟夫环问题,可以分两种情况:

  1. 我们要求出最后留下的那个人的编号(本题要求)。
  2. 求全过程,即要算出每轮出局的人。

有多种方法可以解决约瑟夫环问题,其中一种是使用递归的方式。

本题的约瑟夫环问题的公式为: (f(n - 1, k) + k - 1) % n + 1。f(n,k) 表示 n 个人报数,每次报数报到 k 的人出局,最终最后一个人的编号。

假设 n 为 10,k 为 3,逆推过程如下:

f(1, 3) = 1(当 n = 1 时,只有一个人,最后一人的编号就为 1);

f(2,3) =(f(1,3) + 3 -1)%2 + 1 = 3%2 + 1 = 2(当 n = 2 时,最后一人的编号为 2);

f(3,3) = (f(2,3) + 3 - 1))%3 + 1 = 4%3 + 1 = 2(当 n = 3 时,最后一人的编号为 2);

f(4,3) = (f(3,3) + 3 - 1) % 4 + 1 = 4%4 + 1 = 1(当 n = 4 时,最后一人的编号为 1);

...

f(10,3) = 3(当 n = 10 时,最后一人的编号为 4);

全站分卷索引 · 9 卷
  1. 1非技术问题
  2. 2自我介绍
  3. 3讲一下实习经历以及遇到的难点
  4. 4说一下自己以后的发展发向(就像更倾向于技术还是业务理解)
  5. 5编号为 1-n 的循环报 1-3,报道 3 的出列,求最后一人的编号
  6. 6写两个线程打印 1-n,一个线程打印奇数,一个线程打印偶数
  7. 7技术问题
  8. 8GET 和 POST 的区别
  9. 9如何优化 MySQL 查询