Leetcode【372、1131】

问题描述：【Math】372. Super Pow

解题思路：

快速幂算法。计算 a^b mod 1337，a 是一个正整数，b 是一个非常大的正整数且以数组形式给出。

这道题其实是考察快速幂（取模）算法。

1、如何计算快速幂：比如我们要计算 3^13，常规方法就是累乘以 3，时间复杂度为 O(n)；快速幂算法就是将 3^13 的指数看成二进制形式，即 3^13 = 3^(1101) = 3^8 * 3^4 * 3^1，因此我们只需要确定指数 exp 的二进制中哪一位为1，可以利用位运算中的 & 和 >> 运算：exp & 1 == 1 表示二进制最低位为 1；exp = exp >> 1 表示除以 2，即去除 exp 的二进制的最低位。因为每次对指数除以 2，则时间复杂度为 O(log n)。求解快速幂（不包括取模）的代码如下：

def power(base,exp):
    res = 1  # 保存结果
    while exp:  # 当指数不为0
        if exp & 1:  # 判断二进制最低位是否为1，如果为1，就把之前的幂乘到结果中。
            res *= base
        base *= base  # 一直累乘，构造 base^2 -> base^4 -> base^8 -> base^16 -> ...
        exp = exp >> 1  # 去掉指数的二进制最低位，继续判断
    return res

2、如何计算快速幂取模：这道题是快速幂取模，因此需要把取模加入到代码中。有下面一条性质：

• a^b mod c = (a mod c)^b mod c；

因此，在快速幂算法中，可以先对底数 a 进行 mod 1337 操作，可以减少计算量。但是，指数 exp 很大也会超时，因此可以在计算诸如 3^13 = 3^(1101) = 3^8 * 3^4 * 3^1 的每一项 3^i 也进行 mod 1337 操作，就可以大幅度减小计算量（上述代码的 base *= base 的地方）。注意，还要对结果进行 mod 1337 操作。因此可以写出如下代码：

Python3 实现：

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        exp, base = 0, 1
        for i in range(len(b) - 1, -1, -1):  # 根据b数组计算指数exp
            exp += b[i] * base
            base *= 10
        ans = 1
        a = a % 1337  # 对底数a进行取余
        while exp:
            if exp & 1:
                ans = (ans * a) % 1337  # 对结果进行取余
            a = (a * a) % 1337  # 对每一项a^i进行取余
            exp = exp >> 1
        return ans

---

问题描述：【Math】1131. Maximum of Absolute Value Expression

解题思路：

绝对值最大表达。给两个数组 arr1 和 arr2，求 |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j| 的最大值。

这道题就是把所有绝对值去掉，总共有以下 8 种情况：

• 对于 i < j，有：
  (arr1[i] + arr2[i] - i) - (arr1[j] + arr2[j] - j)；
  (arr1[i] - arr2[i] - i) - (arr1[j] - arr2[j] - j)；
  (- arr1[i] + arr2[i] - i) - (- arr1[j] + arr2[j] - j)；
  (- arr1[i] - arr2[i] - i) - (- arr1[j] - arr2[j] - j)；
• 对于 i > j，有：
  (arr1[i] + arr2[i] + i) - (arr1[j] + arr2[j] + j)；
  (arr1[i] - arr2[i] + i) - (arr1[j] - arr2[j] + j)；
  (- arr1[i] + arr2[i] + i) - (- arr1[j] + arr2[j] + j)；
  (- arr1[i] - arr2[i] + i) - (- arr1[j] - arr2[j] + j)。

对于 i > j，发现和 i < j 的情况对称（将 i > j 中的 i 和 j 替换，发现和前面相同），因此实际上只有 i < j 的 4 种情况。

此时，这道题和 Leetcode 【Math、DP】121. Best Time to Buy and Sell Stock 中的方法 1 基本相同了。我们实际上在解决一个 max(ai - aj), i < j 的问题，那么在只使用一层循环的过程中，对 aj 进行遍历的同时记录 ai 的最大值即可。即 ans = max(ans, max_-a[i]), max_ = max(max_, a[i])。

时间复杂度为 O(1)，空间复杂度为 O(1)。

Python3 实现：

class Solution:
    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
        N = len(arr1)
        max1 = max2 = max3 = max4 = float("-inf")
        ans1 = ans2 = ans3 = ans4 = float("-inf")
        for i in range(N):
            if i == 0:
                max1 = max(max1, arr1[0] + arr2[0] - 0) 
                max2 = max(max2, arr1[0] - arr2[0] - 0)
                max3 = max(max3, - arr1[0] + arr2[0] - 0)  
                max4 = max(max4, - arr1[0] - arr2[0] - 0)
            else:
                ans1 = max(ans1, max1 - (arr1[i] + arr2[i] - i))
                ans2 = max(ans2, max2 - (arr1[i] - arr2[i] - i))
                ans3 = max(ans3, max3 - (- arr1[i] + arr2[i] - i))
                ans4 = max(ans4, max4 - (- arr1[i] - arr2[i] - i))
                max1 = max(max1, arr1[i] + arr2[i] - i) 
                max2 = max(max2, arr1[i] - arr2[i] - i)
                max3 = max(max3, - arr1[i] + arr2[i] - i)  
                max4 = max(max4, - arr1[i] - arr2[i] - i)
        return max(ans1, ans2, ans3, ans4)