本系列導(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á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