圆圈中最后剩下的数字.md

题目描述

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

约瑟夫环问题

测试用例

• 功能测试（输入的m小于n，比如从最初有5个数字的圆圈中每次删除第2、3个数字；输入的m大于或者等于n，比如从最初有6个数字的圆圈中每次删除第6、7个数字）
• 特殊输入测试（圆圈中有0个数字）
• 性能测试（从最初有400个数字的圆圈中每次删除第997个数字）

题目考点

• 考察应聘者的抽象建模能力。
• 考察应聘者对环形链表的理解及应用能力。
• 考察应聘者的数学功底及逻辑思维能力。

解题思路

解题思路一：利用链表（可以模拟的）来循环遍历

解题思路二：利用数学推导出一个递归公式，见书本。这里就不展示了。

自己解题

最普通的链表（模拟链表）遍历

/**
 * 圆圈中最后剩下的数字
 *
 * @Author rex
 * 2018/9/18
 */
public class Solution {
    /**
     * 环形链表解题
     * @param n
     * @param m
     * @return
     */
    public int lastRemaining_Solution(int n, int m) {
        // 防止特殊输入
        if (n < 0 || m < 1) {
            return -1;
        }
        // 构造链表
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int current = 0;
        while (list.size() > 1) {
            for (int i = 1; i < m; i++) {
                current++;
                if (current == list.size()) {
                    current = 0;
                }
            }
            // 删除之后，注意边界
            list.remove(current);
            if (current > list.size() - 1) {
                current = 0;
            }
        }
        return list.get(current);

    }
}

参考解题

1. 见自己解题
2. 见书本数学推导递归求解