題目

有n個囚犯圍成一圈從1到n編號梯嗽，并從1開始報數(shù)齿尽。每當報到k，這個囚犯就會被執(zhí)行死刑灯节。接著從下一個人開始循头，剩下的囚犯繼續(xù)從1開始報數(shù)并重復(fù)這個過程。直到所有囚犯的數(shù)目加起來小于k炎疆。問給定n和k卡骂，初始站在什么位置的囚犯能活下來？（k > 1 && k <=n)磷雇。

Analysis

對于這道題目偿警，首先我們應(yīng)該明確當k輸入非法的情況（既k<=1或k>n的情況，這兩種情況下要么囚犯全部無法存活要么全部存活）唯笙。在這種情況下程序拋出異常以表示輸入非法螟蒸。

對于其余的情況盒使，我們可以模擬整個循環(huán)報數(shù)的過程直到滿足囚犯數(shù)目小于k為止。此時剩下的編號即為我們要求的編號七嫌∩侔欤考慮到這種循環(huán)遍歷且需要移除某個位置的元素的問題，LinkedList這種數(shù)據(jù)結(jié)構(gòu)是比較適合的诵原。因為我們在循環(huán)報數(shù)的過程中英妓，一定是按順序遍歷的。所以只要利用LinkedList的next指針即可绍赛。同時考慮到移除當前元素后當前元素的前一個元素的next指針需要指向當前元素的后面一個元素蔓纠，使用DoubleLinkedList能夠大大簡化這一過程的實現(xiàn)。同時考慮到這些囚犯是圍成一個環(huán)吗蚌，所以我們需要讓鏈表的頭尾相連形成一個環(huán)狀鏈表腿倚。

事實上不使用循環(huán)鏈表而使用Queue的FIFO特性也可以實現(xiàn)這一模擬的過程。

時間復(fù)雜度

考慮到我們需要不斷循環(huán)整個鏈表蚯妇，且每報k個數(shù)殺掉一個囚犯敷燎，且由于使用了雙向鏈表，移除一個元素的時間為O(1)箩言。因此每移除一個元素需要的時間為k*O(1)=O(k)硬贯。要循環(huán)到整個鏈表只剩k-1個元素，即刪除了n-（k-1)個元素陨收，那么總時間復(fù)雜度為O(k)*(n-k+1)=O(nk)饭豹。

實現(xiàn)如下：

public class JosephProblem {
    private static class Node {
        Node next;
        Node prev;
        int val;
        
        Node(int val) {
            this.val = val;
        }
    }
    public static List<Integer> josephSurviver(int n, int k) throws IllegalArgumentException {
        if (k <= 1 || k > n) {
            throw new IllegalArgumentException("k out of boundary!");
        }
        
        int size = n; 
        Node head = new Node(1);
        Node curr = head;
        for (int i = 1; i < n; i++) {
            curr.next = new Node(i + 1);
            curr.next.prev = curr;
            curr = curr.next;
        }
        // make the LinkedList a circle
        curr.next = head;
        head.prev = curr;
        curr = head;
        
        while (size >= k) {
            // Count off
            for (int i = 1; i <= k - 1; i++) {
                curr = curr.next;
            }
            
            // Remove the kth element
            curr.prev.next = curr.next;
            curr.next.prev = curr.prev;
            size--;
            
            // Start from next person next time.
            curr = curr.next;
        }
        
        List<Integer> ret = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            ret.add(curr.val);
            curr = curr.next;
        }
        
        return ret;
    }
}