【剑指Offer 45】圆圈中最后剩下的数字(约瑟夫环问题)

题目：0, 1, … , n-1 这n个数字排成一个圈圈，从数字0开始每次从圆圏里删除第m个数字。求出这个圈圈里剩下的最后一个数字。

代码如下：

package demo;

import java.util.LinkedList;
import java.util.List;

/**
 * 圆圈中最后剩下的数字（约瑟夫环问题）
 * 
 * @author xiangdonglee
 *
 */
public class Test45 {
    /**
     * 经典解法：用环形链表模拟圆圈。 创建一个共有n个结点的环形链表，然后每次在这个链表中删除第m个结点。
     * 
     * @param n
     * @param m
     * @return
     */
    public static int lastRemaining(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        // 要删除元素的位置
        int index = 0;
        // 开始计数的位置
        int start = 0;
        while (list.size() > 1) {
            // 只要移动m-1次就可以移动到下一个要删除的元素上
            for (int i = 1; i < m; i++) {
                index = (index + 1) % list.size(); // [A]
            }
            list.remove(index);
            /**
             * 确保index指向每一轮的第一个位置
             * 
             * [A]已结能够保证其正确性了，因此下面这3行可以不用写
             */
            // if(index==list.size()) {
            // index=0;
            // }
        }
        return list.get(0);
    }

    /**
     * 数学分析法
     * 
     * @param n
     * @param m
     * @return
     */
    public static int lastRemaining2(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }
        int last = 0;
        for (int i = 2; i <= n; i++) {
            last = (last + m) % i;
        }
        return last;
    }

    public static void main(String[] args) {
        test1();
        System.out.println();
        test2();
    }

    private static void test1() {
        System.out.println(lastRemaining(5, 3));
        System.out.println(lastRemaining(5, 2));
        System.out.println(lastRemaining(6, 7));
        System.out.println(lastRemaining(6, 6));
        System.out.println(lastRemaining(0, 0));
    }

    private static void test2() {
        System.out.println(lastRemaining2(5, 3));
        System.out.println(lastRemaining2(5, 2));
        System.out.println(lastRemaining2(6, 7));
        System.out.println(lastRemaining2(6, 6));
        System.out.println(lastRemaining2(0, 0));
    }
}

运行结果

来源：http://blog.csdn.net/derrantcm/article/details/46798717