[数据结构与算法]【剑指offer】圆圈中最后剩下的数字+构建乘积数组

🔥题目

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

输入：n = 10, m = 3
输出：3

??解析

这个经典的问题叫做【约瑟夫环】。

弗拉维奥·约瑟夫是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。

我们当然可以建立一个循环链表进行模拟，但约瑟夫问题可以在时间O(n)、空间O(1)内解决。

此时有n个人，每次杀掉第m个人，从第0个人开始杀。游戏开始。

游戏开始时，设约瑟夫问题的解为 f(n, m) + 0 ；

杀掉第一个人后，约瑟夫问题的解变为 [f(n - 1, m) + m % n] % n ，即 [f(n - 1, m) + m] % n ；

依此可以递推，直到 f(1, m) = 0 。

所以，我们可以自底向上线性的构建出这个答案（如下面的代码）。

🧊代码

class Solution {
    public int lastRemaining(int n, int m) {
        int res = 0;
        for (int i = 2; i <= n; i++) {
            res = (res + m) % i;
        }
        return res;
    }
}

🌸补充

妙哉妙哉！

?
?
?
?
?

🔥题目

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。

规定：不能使用除法。

输入：[1, 2, 3, 4, 5]
输出：[120, 60, 40, 30, 24]

??解析

最朴素的思路是先求出数组中所有元素的积，然后遍历所有位置，总乘积除以当前位置的值。

可惜，题目不允许我们使用除法。

所以，我们使用 前缀积 的思路，它的原理和 前缀和 类似。

举个例子就能轻易理解这个思路：

🧊代码

class Solution {
    public int[] constructArr(int[] A) {
        int len = A.length;
        int[] B = new int[len];
        int L = 1;
        int R = 1;
        // 前缀积（不包括自己）
        for (int i = 0; i < len; i++) {
            B[i] = L;
            L *= A[i];
        }
        // 后缀积（不包括自己）
        for (int i = len - 1; i >= 0; i--) {
            B[i] *= R;
            R *= A[i];
        }
        return B;
    }
}

🌸补充

妙哉妙哉！