约瑟夫环问题

题目

在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一种自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，报数到 3 的人就自杀，然后再由下一个人重新报 1，报数到 3 的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表得出最终存活的人的编号

思路

首先读懂题目的意思，从第一个开始报数，报到指定间隔的数就把该序号的人移除环形链表，如此反复循环，直到只剩下一个，举个形象的例子如下：

如果，现在有 7 个人围成一条环形链表，第一个开始，数到 3 ，就把对应的该位置的人移出去，假设移除的位置，用？来代替，则有：

[1, 2, 3, 4, 5, 6, 7]，剩下 7 个
- 当前指针指向序号 1，移除第 3 个，剩下 [1, 2, ?, 4, 5, 6, 7]
[1, 2, ?, 4, 5, 6, 7]，剩下 6 个
- 当前指针指向序号 4，移除第 3 个，剩下 [1, 2, ?, 4, 5, ?, 7]
[1, 2, ?, 4, 5, ?, 7]，剩下 5 个
- 当前指针指向序号 7，移除第 3 个，剩下 [1, ?, ?, 4, 5, ?, 7]
[1, ?, ?, 4, 5, ?, 7]，剩下 4 个
- 当前指针指向序号 4，移除第 3 个，剩下 [1, ?, ?, 4, 5, ?, ?]
[1, ?, ?, 4, 5, ?, ?]，剩下 3 个
- 当前指针指向序号 1，移除第 3 个，剩下 [1, ?, ?, 4, ?, ?, ?]
[1, ?, ?, 4, ?, ?, ?]，剩下 2 个
- 当前指针指向序号 1，移除第 3 个，剩下 [?, ?, ?, 4, ?, ?, ?]
最后，剩下序号 4 存活

然而，实际上，每次在链表删除指定节点后，就没有 "?" 来顶替原来的位置

因此，如何能知道下一个相对的应该删除的位置是哪个？

思路一：模拟

模拟环中下一次要删除的位置

每次要从当前位置前进 m 个位置，如果知道上一个移动的位置 cur，那么用 cur + m 再对环的大小 size 取模，就是真正的要删除的位置

也就是，curPosition = ((curPosition - 1) + m) % size，这里 size 每次删除减一，所以前面位置 curPosition 相对于下一次也要减一才能对应上，例如 1 2 3 4 5 6 7，每次 3 格，第一次删除了 3，则下一次的相对位置应该从 2 这个数字开始数，也就是 3 - 1

public class Main {
    public static void main(String[] args) throws IOException {
        josephRing();
    }
    private static void josephRing() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] nums = bf.readLine().split(" ");
        int n = Integer.parseInt(nums[0]); //count of number
        int m = Integer.parseInt(nums[1]); //count of space
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        int currentPos = 0; //position
        while (list.size() > 1) {
            currentPos = ((currentPos - 1) + m) % list.size(); //because size - 1
            list.remove(currentPos);
        }
        System.out.println(list.peek());
    }
}

总结

牛客有两道约瑟夫环，第一道超时，第二道可以通过，好久没写，今天公司比赛，直接凉凉，需要平时多理解，多复习这个思想