Ex1_3_37 Josephus问题

  1. import edu.princeton.cs.algs4.StdIn;
  2. import edu.princeton.cs.algs4.StdOut;
  3. //使用由循环单链表实现的队列完成
  4. public class Ex1_3_37_Josephus<Item> {
  5.     private class Node{
  6.         Item item;
  7.         Node next;
  8.     }
  9.     private int size;
  10.     private Node last;
  12.     public boolean isEmpty(){ return size == 0; }//last.next不可用
  13.     public int size(){ return size; }
  15.     public void enqueue(Item item){
  16.         Node oldLast = last;
  17.         last = new Node();
  18.         last.item = item;
  19.         if(isEmpty()) last.next = last;
  20.         else{
  21.             last.next = oldLast.next;
  22.             oldLast.next = last;
  23.         }
  24.         size++;
  25.     }
  26.     public Item dequeue() {
  27.         Item item = last.next.item;
  28.         size--;
  29.         if (isEmpty()) last = null;
  30.         else {
  31.             last.next = last.next.next;
  32.         }
  33.         return item;
  34.     }
  36.     //测试用例
  37.     public static void main(String[] args){
  38.         Ex1_3_37_Josephus Queue = new Ex1_3_37_Josephus();
  39.         int N = Integer.parseInt(args[0]);
  40.         int M = Integer.parseInt(args[1]);
  41.         for(int i = 0; i < N; i++){ Queue.enqueue(i); }
  42.         for(int i = 0; i < N; i++){
  43.             Ex1_3_37_Josephus.Node node = Queue.last.next;
  44.             for(int j = 0; j < M-2; j++){
  45.                 node = node.next;
  46.             }
  47.             Queue.last = node;
  48.             StdOut.println(Queue.dequeue());
  49.         }
  50.     }//当N=7, M=2时输出1 3 5 0 4 2 6, 6号位最后一个
  51. }

要点

  1. Queue除了使用有first和last节点的链表实现,还可以使用只有last节点的循环链表实现
  2. 这种实现中,isEmpty()不能使用last.next == null判断,因为dequeue()和enqueue()中last.next开始总等于null
  3. 实现思路:每次需要删除规定位次的结点,只能动态改变头结点(尾节点)引用的指向
  1. for(int i = 0; i < N; i++){
  2.             CircleLinkList.Node node = linkList.last.next;//找出当前头结点
  3.             for(int j = 0; j < M-2; j++){//根据规定的位次找到当前头结点下规定位次节点
  4.                 node = node.next;
  5.             }
  6.             linkList.last = node;//为方便删除,让被找出节点成为头节点(实际上找出尾节点,头结点自动形成)
  7.             StdOut.println(linkList.dequeue());//删除并打印
  8.         }