LeetCode 数值的整数次方/递归乘法[递归]

这是我参与更文挑战的第 7 天，活动详情查看： 更文挑战

数值的整数次方（剑指 Offer 16）

题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
复制代码

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100
复制代码

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
复制代码

提示

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31-1
• -10^4 <= xn <= 10^4

思路分析

题目要求不能使用库函数，我们可以考虑使用递归来实现该问题，因为 n 既有正数也有负数。先考虑正数，正数为奇数时，${x^n = x^(n/2) * x^(n/2) * x}$，为偶数时${x^n = x^(n/2) * x^(n/2) }$。这样我们可以一步步分解，直到 n = 0 时，pow = 1，作为终止条件。

代码展示

解法一：时间复杂度是${O(logn)}$，空间复杂度是${O(1)}$。

    public double myPow(double x, int n) {
        if (n >= 0){
            return rPow(x,n);
        } else {
            return 1/(rPow(x,-(n+1)) * x); //整数的最大值和负数的最小值不是对称的  -231 <= n <= 231-1
        }
    }

    public double rPow(double x, int n){
        if (n == 0){
            return 1;
        }
        double rPow = rPow(x,n/2);
        if (n % 2 == 0){
            return rPow * rPow;
        } else {
            return rPow * rPow * x;
        }
    }
复制代码

递归乘法（面试题 08.05）

题目描述

递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

示例 1：

输入：A = 1, B = 10
输出：10
复制代码

示例 2：

 输入：A = 3, B = 4
 输出：12
复制代码

提示

• 保证乘法范围不会溢出

思路分析

题目要求我们不能使用乘法，而且尽量较少加号，减号，位移的使用，所以我们也不应该写出那种一直递归重复的加一个数的那种写法，本地同上面求数值的整数次方题目很类似，只不过这里是加法。B 为奇数时，${A * B =A * (B/2) * A * (B/2) * B}$。为偶数时，${A * B =A * (B/2) * A * (B/2)}$。B 不断减小，直到 B=1 时为终止条件。同时这里还有个小优化，找出 A 和 B 中的最小值，把最小值作为加的次数，最大值作为每次加的值，这样加的次数会减少。

代码展示

解法一：时间复杂度是${O(logn)}$，空间复杂度是${O(1)}$。

    public int multiply(int A, int B) {

//        if (A == 1){
//            return B;
//        }
//        int value = multiply(A/2,B);
//        if (A % 2 == 0){
//            return value + value;
//        } else {
//            return value + value + B;
//        }
        //优化
        int max = Math.max(A,B);
        int min = Math.min(A,B);
        if (min == 1){
            return max;
        }

        int value = multiply(min/2,max);
        if (min % 2 == 0){
            return value + value;
        } else {
            return value + value + max;
        }
    }
复制代码

总结

这两道题的重点是掌握奇数和偶数是如何分解的，掌握这一点，使用递归就不难求了。