算法通关村十三关-白银：数字与数学高频问题

有很多解题技巧，需要持续积累

1.数组实现加法专题

如果让你用数组来表示一个数，如何实现加法呢？
理论上仍然从数组末尾向前挨着计算就行了，但是实现的时候会发现很多问题，例如需要进位该怎么办？

进一步拓展，两个数相加，一个用数组存储，另一个是普通的整数，如何处理？

再拓展，如果两个整数使用字符串表示呢？如果是要按照二进制加法的规则来呢？

1.1数组实现整数加法

LeetCode66
https://leetcode.cn/problems/plus-one/

思路分析

从后向前一直加就行，如果有进位就需要进位
重点关注：当进位导致数组长度变化的情况，如 [9,9,9]，加1后变为[1,0,0,0]，数组长度发生变化

代码实现

Java中巧妙处理数组长度变化

digits = new int[len+1];
digits[0] = 1
1
2

def plusOne(digits):
    n = len(digits)
    for i in range(n - 1, -1, -1):
        digits[i] += 1
        digits[i] %= 10
        if digits[i] != 0:
            return digits
    return [1] + digits

1
2
3
4
5
6
7
8
9

def plusOne(digits):
    n = len(digits)
    for i in range(n - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    digits.insert(0, 1)
    return digits
1
2
3
4
5
6
7
8
9

1.2字符串加法

给定两个字符串形式的非负整数 num1 和 num2，计算它们的和并同样以字符串形式返回

思路分析

从低到高逐位相加，如果当前和超过10，则向高位进一位

通过代码写出来
定义两个指针i和j，分别指向num1和num2的末尾，即最低位
定义一个变量add维护当前是否有进位
从末尾到开头逐位相加

注：两个数组位数不同，补0处理

代码实现

def addString(num1, num2):
    i, j = len(num1) - 1, len(num2) - 1,
    ans = ""
    add = 0
    while i >= 0 or j >= 0 or add:
        x = num1[i] if i >= 0 else '0'
        y = num2[j] if j >= 0 else '0'
        result = int(x) + int(y) + add
        ans = str(result % 10) + ans
        add = result // 10
        i -= 1
        j -= 1
    return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

1.3二进制加法

LeetCode67
https://leetcode.cn/problems/add-binary/

思路分析
方法1：中规中矩，参考上面字符串加法

方法2：先将其转换成十进制，加完之后转换成二进制
这么做实现非常容易，而且可以使用语言提供的方法直接转换
工程里可以这么干，稳定可靠，但是算法里不行，太简单了

代码实现

方法1：

def addBinary(a, b):
    i, j = len(a) - 1, len(b) - 1,
    ans = []
    add = 0
    while i >= 0 or j >= 0 or add:
        result = add
        result += int(a[i]) if i >= 0 else 0
        result += int(b[j]) if j >= 0 else 0
        ans.append(str(result % 2))
        add = result // 2
        i -= 1
        j -= 1
    ans.reverse()
    return "".join(ans)


if __name__ == '__main__':
    print(addBinary('100', '111'))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.幂运算

形式 a^b ，a的b次方，a为底数，b为指数
合法，不会出现a=0且b<=0的情况

关注底数和指数的数据类型和取值范围
如有的问题中，底数是正整数，指数是非负整数
有的问题中，底数是实数，指数是整数

LeetCode中，幂运算相关的问题主要是判断一个数是不是特定正整数的整数次幂，以及快速幂的处理

2.1求2的幂

LeetCode 231 2 的幂
https://leetcode.cn/problems/power-of-two/

思路分析

如果存在一个整数x，使得 2^x = n，则认为n是2的幂次方

方法1：除法
用除法逐步缩小n的值
首先判断 n 是否是正整数，n为0或者为负整数，返回false
n 是正整数，连续对n进行除以2的操作，直到n不能被2整除，如果 n==1，返回true，否则返回false

方法2：位运算
该方法与前面统计数字转换成二进制之后1的个数思路一致
当 n>0 时，考虑 n 的二进制表示
如果 n = 2^k，则n的二进制表示为1后面跟 k 个0
仅当 n 的二进制表示中只有最高位是1，其余位都是0，此时满足 n&(n-1)=0

代码实现

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        # 方法1：除法
        if n <= 0:
            return False
        while n % 2 == 0:
            n //= 2
        return n == 1
1
2
3
4
5
6
7
8

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        # 方法2：位运算
        return n>0 and n&(n-1) == 0
1
2
3
4

2.2求3的幂

LeetCode326
https://leetcode.cn/problems/power-of-three/

思路分析

方法1：除法
同上面求2的幂

方法2：技巧
给定的n是int型，其最大值为 2^31-1
不超过 2^31 的最大的3的幂是 3^19 = 1162261467
如果在 1~2^31-1内的数，如果是3的幂，则一定是能被 1162261467 整除

代码实现

方法1：除法

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        # 方法1：除法
        if n<=0:
            return False
        while n%3==0:
            n//=3
        return n == 1
1
2
3
4
5
6
7
8

方法2：技巧

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        # 方法2：技巧
        return n>0 and 3**19 % n == 0
1
2
3
4

拓展思考

这里将3换成 4，5，6，7，8，9可以吗？如果不可以，那如果只针对素数 3，5，7，11，13可以吗？

2.4求4的幂

LeetCode342
https://leetcode.cn/problems/power-of-four/submissions/

思路分析

方法1：除法
与求2的幂思路一致，数学方法一直除

方法2：利用2的次幂进行拓展来优化
如果n是4的幂，那么n一定是2的幂 满足 n&(n-1)==0
如果n是4的幂，n的二进制表示只有1个1，1后面必须有偶数个0，且1出现在从低位开始（从0开始）的第偶数个二进制位上

如 16 的二进制表示 10000

n为32为有符号整数，构建辅助二进制数
MASK = 1010 1010 1010 1010 1010 1010 1010 1010
MASK = AAAAAAAA 16进制

方法3：取模

4^x≡(3+1) ^x ≡1^x≡1(mod 3)

如果 n是2的幂却不是 2 的幂，那么它可以表示成 4^× * 2，它除以3的余数一定为2。
因此我们可以通过n除以 3 的余数是否为 1来判断 n 是否是 4 的幂。

代码实现

方法1：

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        # 方法1：除法
        if n<= 0:
            return False
        while n % 4 == 0:
            n //= 4
        return n == 1
1
2
3
4
5
6
7
8

方法2：

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        # 方法2：2的幂的拓展
        return n>0 and n&(n-1)==0 and n&(0xaaaaaaaa) == 0
1
2
3
4

方法3：

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        # 方法3:取模
        return n>0 and n&(n-1)==0 and n % 3 == 1
1
2
3
4