LeetCode题练习与总结：超级次方--372

标签：myPow 函数递归 -- 复杂度 1337 372 LeetCode superPowHelper

一、题目描述

你的任务是计算 a^b 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

示例 1：

输入：a = 2, b = [3]
输出：8

示例 2：

输入：a = 2, b = [1,0]
输出：1024

示例 3：

输入：a = 1, b = [4,3,3,8,5,2]
输出：1

示例 4：

输入：a = 2147483647, b = [2,0,0]
输出：1198

提示：

1 <= a <= 2^31 - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b 不含前导 0

二、解题思路

首先，我们可以利用模运算的性质：(x * y) % p = [(x % p) * (y % p)] % p。这意味着我们可以将大数幂分解成多个小数幂，然后逐步取模。
对于非常大的正整数 b，我们可以将 b 看作是一个大数的每一位数字。例如，如果 b = [1, 0]，则它表示数字 10。我们可以将问题分解为计算 a^10 的模。
我们可以使用递归的方法来解决这个问题。递归的基本思路是：如果 b 是一个一位数，那么我们直接计算 a^b % 1337；如果 b 是多位数，我们可以将其分解为两部分：b 的最后一位数字和 b 去掉最后一位数字的部分。例如，对于 b = [1, 0]，我们可以将其分解为 b 的最后一位数字 0 和 b 去掉最后一位数字的部分 [1]。
我们可以使用以下递归公式来计算 a^b % 1337：
- 如果 b 的长度为 1，返回 a^b[0] % 1337。
- 否则，返回 (a^b[0] % 1337) * (a^(b 去掉最后一位数字) % 1337) % 1337。
注意，由于 b 可能非常大，我们需要在每一步计算中都对结果取模，以避免整数溢出。

三、具体代码

class Solution {
    public int superPow(int a, int[] b) {
        if (b == null || b.length == 0) {
            return 1;
        }
        return superPowHelper(a, b, b.length - 1);
    }

    private int superPowHelper(int a, int[] b, int index) {
        if (index < 0) {
            return 1;
        }
        int part1 = myPow(a, b[index]);
        int part2 = myPow(superPowHelper(a, b, index - 1), 10);
        return (part1 * part2) % 1337;
    }

    private int myPow(int x, int n) {
        if (n == 0) {
            return 1;
        }
        x %= 1337;
        int result = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                result = (result * x) % 1337;
            }
            x = (x * x) % 1337;
            n >>= 1;
        }
        return result;
    }
}

在这段代码中，superPow 是主函数，它调用递归函数 superPowHelper 来计算结果。myPow 函数用于计算 x 的 n 次幂并对 1337 取模。递归函数 superPowHelper 使用递归公式来计算结果。

四、时间复杂度和空间复杂度

1. 时间复杂度

myPow 函数的时间复杂度：在 myPow 函数中，我们使用了一个循环，其中循环的次数取决于 n 的二进制表示中的位数。n 的二进制位数是 O(log n)。在每次循环中，我们执行常数时间的操作（乘法和模运算）。因此，myPow 函数的时间复杂度是 O(log n)。
superPowHelper 函数的时间复杂度：在 superPowHelper 函数中，我们递归地调用自己，并且每次递归调用都会减少数组 b 的一个元素。由于 b 的长度是固定的，假设为 m，则递归的深度最多是 m。在每次递归调用中，我们都会调用一次 myPow 函数，其时间复杂度是 O(log b[i])，其中 b[i] 是一个小于 10 的整数。因此，对于每次递归调用，myPow 的时间复杂度可以认为是 O(1)。所以，superPowHelper 函数的时间复杂度是 O(m)，因为我们需要遍历数组 b 中的每个元素一次。
综合时间复杂度：superPow 函数的时间复杂度与 superPowHelper 相同，因为 superPow 只调用了 superPowHelper 一次。因此，整个算法的时间复杂度是 O(m)，其中 m 是数组 b 的长度。

2. 空间复杂度

myPow 函数的空间复杂度：myPow 函数使用了一些固定数量的变量（x, n, result），因此它的空间复杂度是 O(1)。
superPowHelper 函数的空间复杂度：在递归调用过程中，每次递归调用都会在调用栈上占用一定的空间。由于递归的深度最多是 m，因此调用栈的空间复杂度是 O(m)。
综合空间复杂度：整个算法的空间复杂度主要取决于递归调用的栈空间，因此空间复杂度是 O(m)，其中 m 是数组 b 的长度。

五、总结知识点

递归：superPowHelper 函数是一个递归函数，它通过递归调用来解决子问题。递归的基本条件是当 index < 0 时返回 1。
模运算：在 myPow 函数中，频繁使用了模运算 % 1337，这是为了避免整数溢出，并确保结果在 0 到 1336 之间。
快速幂算法：myPow 函数实现了快速幂算法（也称为指数的二进制方法），用于高效计算 x 的 n 次幂。该算法通过将指数 n 表示为二进制形式，并使用迭代和位操作来减少乘法操作的次数。
位操作：在 myPow 函数中，使用位操作 (n & 1) 来检查 n 的当前最低位是否为 1，以及使用 n >>= 1 来将 n 右移一位，相当于 n = n / 2。
数组操作：在 superPow 和 superPowHelper 函数中，对数组 b 进行操作，使用数组的长度和索引来访问数组元素。
边界条件检查：在 superPow 函数开始时，检查输入数组 b 是否为 null 或者长度为 0，这是一种常见的防御性编程实践。
数学运算：代码中使用了乘法运算来计算幂的乘积，并使用了模运算来保持结果在特定的范围内。
函数封装：代码将不同功能的逻辑封装在 superPow, superPowHelper, 和 myPow 三个函数中，每个函数都有明确的职责，体现了良好的编程习惯。
数学性质：代码利用了模运算的性质 (a * b) % c = [(a % c) * (b % c)] % c，这在计算大数的幂模运算时非常有用。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。

标签：myPow,函数,递归,--,复杂度,1337,372,LeetCode,superPowHelper
From： https://blog.csdn.net/weixin_62860386/article/details/143414381