本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖
面試題62：圓圈中最后剩下的數(shù)字
題目要求：
0，1筐钟，2...n-1這n個(gè)數(shù)字拍成一個(gè)圓圈皮服，從數(shù)字0開(kāi)始牢裳，每次從這個(gè)圓圈里刪除第m個(gè)數(shù)字坯苹，求剩下的最后一個(gè)數(shù)字隆檀。例如0，1粹湃，2恐仑，3，4這5個(gè)數(shù)字組成的圈为鳄，每次刪除第3個(gè)數(shù)字裳仆，一次刪除2，0济赎，4，1记某，因此最后剩下的是3司训。
解題思路：
最直接的思路是用環(huán)形鏈表模擬圓圈，通過(guò)模擬刪除過(guò)程液南，可以得到最后剩下的數(shù)字壳猜，那么這道題目就變成了刪除鏈表中某一個(gè)節(jié)點(diǎn)。假設(shè)總節(jié)點(diǎn)數(shù)為n滑凉，刪除一個(gè)節(jié)點(diǎn)需要走m步统扳，那么這種思路的時(shí)間復(fù)雜度為o(mn)，空間復(fù)雜度o(n)畅姊。
思路2比較高級(jí)咒钟，較難理解，可遇不可求若未。將圓圈表示成一個(gè)函數(shù)表達(dá)式朱嘴，將刪除節(jié)點(diǎn)的過(guò)程表示成函數(shù)映射的變化，時(shí)間復(fù)雜度o(n)，空間復(fù)雜度o(1)!有興趣的話(huà)可以搜素”約瑟夫環(huán)“去詳細(xì)了解萍嬉。
package chapter6;
import structure.ListNode;
/**
* Created with IntelliJ IDEA
* Author: ryder
* Date : 2017/8/20
* Time : 16:20
* Description:圓圈中最后剩下的數(shù)字
* n=5,m=3,從0,1,2,3,4組成的圓中刪除第3個(gè)數(shù)字
* 依次刪除3,0,4,1乌昔，最終剩下的是3
**/
public class P300_LastNumberInCircle {
public static int lastRemaining(int n,int m){
if(n<1||m<1)
return -1;
ListNode<Integer> head = new ListNode<>(0);
ListNode<Integer> cur = head;
for(int i=1;i<n;i++){
ListNode<Integer> node = new ListNode<>(i);
cur.next = node;
cur = cur.next;
}
cur.next = head;
cur = head;
while (true){
//長(zhǎng)度為1結(jié)束循環(huán)
if(cur.next==cur)
return cur.val;
//向后移動(dòng)
for(int i=1;i<m;i++)
cur=cur.next;
//刪除當(dāng)前節(jié)點(diǎn)
cur.val = cur.next.val;
cur.next = cur.next.next;
//刪除后，cur停在被刪節(jié)點(diǎn)的后一節(jié)點(diǎn)處
}
}
//另一個(gè)思路分析過(guò)程較復(fù)雜壤追，不強(qiáng)求了磕道。可搜約瑟夫環(huán)進(jìn)行了解行冰。
public static void main(String[] args){
System.out.println(lastRemaining(5,3)); //3
System.out.println(lastRemaining(6,7)); //4
System.out.println(lastRemaining(0,7)); //-1
}
}
運(yùn)行結(jié)果
3
4
-1
