第8章栈 - 递归 - 《数据结构与算法》

剑指 Offer 16. 数值的整数次方

实现函数 double Power(double base, int exponent)，求 base 的 exponent 次方。不得使用库函数，同时不需要考虑大数问题。

思路：当指数为负数的时候，可以转化为底数取倒数，指数取相反数的情况。
为了避免一次又一次将底数相乘，我们采用这样「偷懒」的策略，比如要计算5^{18}，其实我们只要算出5^9，然后再自己乘自己就好了，这样就可以避免做9次\times 5的运算。（这种思想有点像「记忆化递归」。）

那么有一种机制就能帮助我们找到一个整数的合适的「分解」，那么就是将一个整数看成它的二进制形式。就那上面的例子来说，18的二进制表示为(10010)_2，即：
18 = 1 \times 2^4 + 1\times2^1
那么：
5^{18} = 5^{2^4} \times 5^{2^1}
于是，我们可以把指数 $递归 - 图1$ 做「二进制分解」，在底数不断自身乘以自身的过程中，将最终结果需要的部分保存下来。

例如，求 pow(2, 10)，

i		10	5	2	1	0
product	2	4	16	256	256*256
res	1	1	4	4	1024

10 = 1 \times 2^3 + 1\times2^1
2^{10} = 2^{2^3} \times 2^{2^1}

①分治思想

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if(N < 0) {
            x = 1 / x;
            N = - N;
        }
        double res = 1;
        double product = x;
        for(long i = N; i > 0; i /= 2) {
            if(i % 2 == 1) {
                res = res * product;
            }
            product = product * product;
        }
        return res;
    }
}

②递归写法

class Solution {
    public double myPow(double x, int n) {
        long b = n;
        return myPow(x, b);
    }
    private double myPow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            return 1 / myPow(x, -n);
        }
        if ((n % 2) == 1) {
            return x * myPow(x, n - 1);
        }
        return myPow(x * x, n / 2);
    }
}

剑指 Offer 62. 圆圈中最后剩下的数字

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

思路1：
纯暴力的做法，每次找到删除的那个数字，需要 O(m) 的时间复杂度，然后删除了 n−1 次。但实际上我们可以直接找到下一个要删除的位置的。
假设当前删除的位置是 idx，下一个删除的数字的位置是 idx + m。但是，由于把当前位置的数字删除了，后面的数字会前移一位，所以实际的下一个位置是 idx+m−1。由于数到末尾会从头继续数，所以最后取模一下，就是(idx+m−1)(modn)。

至于这种思路的代码实现，我尝试了下 LinkedList 会超时，我猜是因为 LinkedList 虽然删除指定节点的时间复杂度是 O(1) 的，但是在 remove 时间复杂度仍然是 O(n) 的，因为需要从头遍历到需要删除的位置。那 ArrayList 呢？索引到需要删除的位置，时间复杂度是 O(1)，删除元素时间复杂度是 O(n)（因为后续元素需要向前移位），remove 整体时间复杂度是 O(n) 的。看起来LinkedList 和 ArrayList 单次删除操作的时间复杂度是一样的，但是ArrayList 的 remove 操作在后续移位的时候，其实是内存连续空间的拷贝的。所以相比于LinkedList大量非连续性地址访问，ArrayList的性能是很 OK 的。

执行用时：1100 ms, 在所有 Java 提交中击败了11.66%的用户
内存消耗：41.7 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int lastRemaining(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int idx = 0;
        while (n > 1) {
            idx = (idx + m - 1) % n;
            list.remove(idx);
            n--;
        }
        return list.get(0);
    }
}

思路2：
数学解法，O(n)。
执行用时：7 ms, 在所有 Java 提交中击败了99.98%的用户
内存消耗：36.4 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int lastRemaining(int n, int m) {
        int ans = 0;
        // 最后一轮剩下2个人，所以从2开始反推
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }
}

思路3：
递归。
我们知道，从 f(n - m) 场景下删除的第一个数的序号是 (m - 1) % n，那么 f(n - 1, m) 场景将使用被删除数字的下一个数，即序号 m % n 作为它的 0 序号。

设 f(n - 1, m) 的结果为 x，x 是从 f(n, m) 场景下序号为 m % n 的数字出发所获得的结果，因此，我们可以得出：m % n + x 是该数字在 f (n, m) 场景下的结果序号。即：

f(n, m) = m % n + x
但由于 m % n + x 可能会超过 n 的范围，所以我们再取一次模：

f(n , m) = (m % n + x) % n = (m + x) % n
将 f(n - 1, m) 代回，得到递推公式：
f(n, m) = (m + f(n - 1, m)) % n

执行用时：11 ms, 在所有 Java 提交中击败了49.07%的用户
内存消耗：41.6 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int lastRemaining(int n, int m) {
        return helper(n, m);
    }
    private int helper(int n, int m) {
        if (n == 0) {
            return 0;
        }
        int x = helper(n - 1, m);
        return (m + x) % n;
    }
}

剑指 Offer 64. 求1+2+…+n

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

思路：
递归。

class Solution {
    public int sumNums(int n) {
        int res = n;
        boolean ans = (n > 0) && ((res += sumNums(n-1)) > 0);
        return res;
    }
}