約瑟夫問題（丟手絹問題）
Josephu(約瑟夫)問題
約瑟夫問題，有時也稱為約瑟夫斯置換，是一個電腦科學和數學中的問題。在電腦編程的演算法中，類似問題又稱為約瑟夫環。又稱「丟手絹問題」。
Josephu問題起源
Josephu問題描述
丟手絹
設編號為1，2，… n的n個人圍坐一圈，約定編號為k（1<=k<=n）的人從1開始報數，數到 m 的那個人出列，它的下一位又從1開始報數，數到 m 的那個人又出列，依次類推，直到所有人出列為止，由此產生一個出隊編號的序列。
演算法實現（數據結構）
用一個不帶頭結點的循環鏈表來處理Josephu 問題：先構成一個有n個結點的單循環鏈表，然後由k結點起從1開始計數，計到m時，對應結點從鏈表中刪除，然後再從被刪除結點的下一個結點又從1開始計數，直到最後一個結點從鏈表中刪除演算法結束。
程式碼實現：
package com.ruoli;
public class Josephu {
public static void main(String[] args) {
// 測試一把看看構建環形鏈表和遍歷是否ok
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5); // 加入5個小孩節點
circleSingleLinkedList.show();
// 測試一把小孩出圈是否正確
circleSingleLinkedList.boyCount(1, 2, 5); // 2->4->1->5->3
}
}
//小孩結點類
class Boy{
private int val;
private Boy next;
public Boy(int val) {
this.val = val;
}
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}
//環型單鏈表類（模擬孩子圍成的圈）
class CircleSingleLinkedList{
// 創建一個first節點,當前沒有編號
Boy first = null;
// 添加小孩節點，構建成一個環形的鏈表
public void addBoy(int num) {
if (num < 1) {
return;
}
Boy curBoy = null;
for (int i = 1; i <= num; i++) {
Boy boy = new Boy(i);
if (i == 1) {
first = boy; // first:第一個結點
first.setNext(first); // 構成環
curBoy = first; // 讓curBoy指向第一個小孩
}else {
curBoy.setNext(boy);
boy.setNext(first); // 構成環
curBoy = boy;
}
}
}
// 遍歷當前的環形鏈表
public void show() {
// 判斷鏈表是否為空
if (first == null) {
System.out.println("此時還沒有小孩。。。");
return;
}
// 因為first不能動，因此我們仍然使用一個輔助指針完成遍歷
Boy curBoy = first;
while (true) {
System.out.printf("小孩的編號：%d \n", curBoy.getVal());
if (curBoy.getNext() == first) { // 說明已經遍歷完畢
break;
}
curBoy = curBoy.getNext();
}
}
// 根據用戶的輸入，計算出小孩出圈的順序
/**
*
* @param startVal：表示從第幾個小孩開始數數
* @param count：表示數幾下
* @param nums：表示最初有多少小孩在圈中
* @return
*/
public void boyCount(int start, int count, int nums) {
// 先對數據進行校驗
if (first == null || start < 1 || start > nums) {
System.out.println("參數輸入有誤， 請重新輸入");
return;
}
// 創建輔助指針,幫助完成小孩出圈
Boy helper = first;
// 創建的輔助指針(變數) helper , 事先應該指向環形鏈表的最後這個節點
while (true) {
if (helper.getNext() == first) {
break;
}
helper = helper.getNext();
}
// 小孩報數前，先讓 first 和 helper 移動 start - 1次
for (int i = 0; i < start - 1; i++) {
first = first.getNext();
helper = helper.getNext();
}
// 當小孩報數時，讓first 和 helper 指針同時 的移動 m - 1 次, 然後出圈
// 這裡是一個循環操作，知道圈中只有一個節點
while (true) {
if (helper == first) { // 說明圈中只有一個節點
break;
}
// 讓 first 和 helper 指針同時 的移動 count - 1
for (int i = 0; i < count - 1; i++) {
first = first.getNext();
helper = helper.getNext();
}
// 這時first指向的節點，就是要出圈的小孩節點
System.out.printf("小孩%d出圈\n", first.getVal());
// 這時將first指向的小孩節點出圈
first = first.getNext();
helper.setNext(first);
}
System.out.printf("最後留在圈中的小孩編號%d \n", first.getVal());
}
}
運行結果：
我們所見的面試題，一般會要求我們找到最後一個出隊的人，即返回最後一個出隊的人的編號。本文只提供一種解決問題的思路和具體的演算法實現，如果大家能把上述的演算法搞懂，那麼在其上稍微修改一下，就能輕鬆的解決所遇到的面試題了。
參考資料：
尚矽谷數據結構課程
演算法實現（數學求解）
用鏈表來模擬小孩子圍圈圈，是可以解決問題，但實現起來有點費事，在一些情況下，我們並沒有充足的時間來慢慢的實現鏈表。這時，我們可以用簡單一點的方法，這兒只說一種比較好的的方法，還有其他有趣的方法，大家可自行了解。
話不多說，來看求解思路：
我們從最後剩下的 3 倒著看，我們可以反向推出這個數字在之前每個輪次的位置：
最後剩下的 3 的下標是 0。
第四輪反推，補上 m 個位置，然後模上當時的數組大小 2，位置是(0 + 3) % 2 = 1。
第三輪反推，補上 m 個位置，然後模上當時的數組大小 3，位置是(1 + 3) % 3 = 1。
第二輪反推，補上 m 個位置，然後模上當時的數組大小 4，位置是(1 + 3) % 4 = 0。
第一輪反推，補上 m 個位置，然後模上當時的數組大小 5，位置是(0 + 3) % 5 = 3。
所以，最終剩下的數字的下標就是3。因為數組是從0開始的，所以最終的答案就是3。
總結一下：
反推的過程就是 (當前index + m) % 上一輪剩餘數字的個數。
程式碼實現：
public class Test {
public static void main(String[] args) {
int n = 5;
int m = 3;
int result = lastRemaining(n, m);
System.out.println("最後剩下的人是：" + result + "號");
}
public static int lastRemaining(int n, int m) {
int ans = 0;
// 最後一輪淘汰有2個人，所以從2開始反推
for (int i = 2; i <= n; i++) {
ans = (ans + m) % i;
}
return ans;
}
}
運行結果：
這種方法要比用鏈表來模擬效率高的多，但我們刷題的時候，用鏈表來模擬提交會出現超時，但用這種方法時間複雜度和空間複雜度都小的多，LeetCode提交結果如下：
參考資料：
小姐姐的題解。
