1.什么是约瑟夫问题？
2.约瑟夫问题的解决方式
通过单向循环链表解决，具体思路如下：
/**
* @author shengjk1
* @date 2020-02-06
*/
public class Josephus {
public static void main(String[] args) {
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoys(5);
circleSingleLinkedList.show();
// circleSingleLinkedList.countBoy(5);
circleSingleLinkedList.countBoy(1, 2, 5);
}
}
//先创建一个 单向循环列表类
class CircleSingleLinkedList {
private Boy first = null;
private Boy firstPre = null;
private int nums;
//设置这个列表中添加多少个小孩
public void addBoys(int nums) {
if (nums < 1) {
System.out.println("nums 值不正确 ！");
return;
}
this.nums = nums;
Boy curBoy = null;
for (int i = 1; i <= nums; i++) {
if (i == 1) {
first = new Boy(i);
first.setNext(first);
curBoy = first;
} else {
Boy boy = new Boy(i);
curBoy.setNext(boy);
curBoy = boy;
curBoy.setNext(first);
}
firstPre = curBoy;
}
}
/*
1.创建一个辅助指针 helper，事先应该指向环形链表的最后一个节点
2.当小孩报数时，让 first 和 helper 指针同时移动 m-1 次
3.这时就可以将 first 指向的小孩节点出圈
first=first.next
helper.next=first
*/
//偷懒的方式，借助 firstPre(helper)，简易版的,或者直接通过循环找到 firstPre(helper)
public void countBoy(int m) {
while (true) {
for (int i = 1; i < m; i++) {
first = first.getNext();
firstPre = firstPre.getNext();
}
System.out.println("移除 " + first.getNo());
first = first.getNext();
firstPre.setNext(first);
if (firstPre == first) {
System.out.println("移除 " + first.getNo());
break;
}
}
}
/**
* 复杂版，逻辑与简易版类似
*
* @param startNo 表示从第几个小孩开始数数
* @param countNum 表示数几下
* @param nums 表示最初有多少个小孩在权重
*/
public void countBoy(int startNo, int countNum, int nums) {
if (first == null || startNo < 1 || startNo > this.nums || nums > this.nums) {
System.out.println("参数有误，请重新输入！");
return;
}
Boy helper = first;
while (true) {
//直接移动到 startNo
if (helper.getNext().getNo() == startNo) {
break;
}
helper = helper.getNext();
}
first = helper.getNext();
while (true) {
if (helper == first) {
System.out.println("最后留在圈中的小孩是 " + first.getNo());
break;
}
for (int i = 1; i < countNum; i++) {
first = first.getNext();
helper = helper.getNext();
}
System.out.println("移除小孩 " + first.getNo());
first = first.getNext();
helper.setNext(first);
}
}
//展示所有的小孩编号
public void show() {
if (first == null) {
System.out.println("单向循环链表表为 null");
return;
} else {
Boy curBoy = first;
while (true) {
System.out.println("boy num " + curBoy.getNo());
curBoy = curBoy.getNext();
if (curBoy == first) {
break;
}
}
}
}
}
class Boy {
private int no;
private Boy next;
public Boy(int no) {
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}
3.单向循环链表的使用场景
- 网易云音乐等音乐 APP 中的循环播放
- kafka 的时序( 具体是否为单向循环链表需要确定，肯定使用的循环链表)
4.关于单向循环链表的面试题
- 约瑟夫问题