圆圈中最后剩下的数字

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

这道题就是有名的约瑟夫环问题，下面介绍两种介绍，第一种是使用链表模拟该环，第二种方法是使用动态规划。

对于使用环形链表模拟环，可以很快的写出这样的代码

public static int lastRemaining(int n, int m) {
    List<Integer> list = new LinkedList<>();
    // 将 0 ~ n-1 共 n 个数字添加到链表中
    for (int i = 0; i < n; i++) {
        list.add(i);
    }
    // 要删除的元素的下标，因为是环形链表，我们要对链表的长度求余
    int currentIndex = (m - 1) % list.size();
    // 当链表中有一个以上的元素
    while (list.size() > 1) {
        // 删除元素
        list.remove(currentIndex);
        // 更新下一次要删除的元素的下标
        currentIndex = (currentIndex + m - 1) % list.size();
    }
    // 返回链表中仅剩的元素
    return list.get(0);
}

而另一种方法就是使用动态规划，我们使用 $f(n, m)$ 表示 $n$ 个数字中删除第 $m$ 个数字剩下来的数字。第一个被删除的数字是 $(m-1) % n$，记为 $k$，还剩下 $n - 1$ 个元素，我们来做一个映射

$x$	$y$
$0$	$k + 1$
$1$	$k+2$
$…$	$…$
$n- k - 2$	$n - 1$
$n- k -1$	$0$
$…$	$…$
$n - 2$	$k - 1$

$y$ 序列是删除了元素 $k$ 剩下的元素排序，我们与一个 $0-(n-2)$ 的元素映射起来，$x$ 与 $y$ 之间的对应关系为 $y = (x + k + 1) % n$。因为 $k = (m - 1) % n$，所以 $(k + 1) % n = m % n$，所以上式的关系进一步更改为 $y = (x + m) % n$。

假设 $y$ 序列最后剩下的数字为 $f^{‘}(n-1, m)$，记为 $u$，设 $x$ 序列最后剩下的值为 $v$，那么有这样的一个关系
$$
f^{‘}(n-1, m) = u = (v + m) % n = (f(n-1, m) + m) % n
$$
又因为
$$
f(n,m) = f^{‘}(n-1, m)
$$
所以们得到了 $f(n,m)$ 与 $f(n-1, m)$ 的递推公式
$$
f(n,m) = f^{‘}(n-1, m) = u = (f(n-1, m) + m) % n
$$
所以们得到了 $f(n,m)$ 与 $f(n-1, m)$ 的递推公式
$$
f(n,m) =
\begin{cases}
0, & n = 1 \\
\left[f(n-1,m) + m \right] % n, & n > 1
\end{cases}
$$
编程如下

public static int lastRemaining(int n, int m) {
    if (n < 1 || m < 1) {
        return 0;
    }
    
    int last = 0;
    for (int i = 2; i <= n; i++) {
        last = (last + m) % n;
    }
    
    return last;
}