首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode【372、1131】

Leetcode【372、1131】

作者头像
echobingo
发布2019-07-24 15:40:01
6890
发布2019-07-24 15:40:01
举报
问题描述:【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 的 4 种情况。

此时,这道题和 Leetcode 【Math、DP】121. Best Time to Buy and Sell Stock 中的方法 1 基本相同了。我们只需要从左到右遍历一遍,分别找出 arr1[i] + arr2[i] - iarr1[i] - arr2[i] - i- arr1[i] + arr2[i] - i- arr1[i] - arr2[i] - i、的最大值和最小值 max1/min1、max2/min2、max3/min3、max4/min4,然后最后的结果就是四种情况的最大值减去最小值的差的最大值,即 ans = max(max1 - min1, max2 - min2, max3 - min3, max4 - min4)

时间复杂度为 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")
        min1 = min2 = min3 = min4 = float("inf")
        for i in range(N):
            max1 = max(max1, arr1[i] + arr2[i] - i)  # > >
            min1 = min(min1, arr1[i] + arr2[i] - i)
            max2 = max(max2, arr1[i] - arr2[i] - i)  # > <
            min2 = min(min2, arr1[i] - arr2[i] - i)
            max3 = max(max3, - arr1[i] + arr2[i] - i)  # < >
            min3 = min(min3, - arr1[i] + arr2[i] - i)
            max4 = max(max4, - arr1[i] - arr2[i] - i)  # < <
            min4 = min(min4, - arr1[i] - arr2[i] - i)
        return max(max1 - min1, max2 - min2, max3 - min3, max4 - min4)
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019.07.22 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题描述:【Math】372. Super Pow
  • 解题思路:
  • Python3 实现:
  • 问题描述:【Math】1131. Maximum of Absolute Value Expression
  • 解题思路:
  • Python3 实现:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档