Leetcode题解-算法-数学(python版)_leetcode python 解析 pdf

1、进制转换

1.1 小于 n 的所有素数

204. 计数质数(Medium)
从 2 开始，每碰见一个素数，就将该素数的所有整数倍的数排除。

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        prime = [1] * n
        prime[0], prime[1] = 0, 0
        # 把不大于根号 n 的所有质数的倍数剔除
        for i in range(2, int(n ** 0.5) + 1):
            if prime[i] == 1:
                for j in range(2 * i, n, i):
                    prime[j] = 0
        return sum(prime)

1
2
3
4
5
6
7
8
9
10
11
12
13

1.2 7进制

504. 七进制数(Easy)

class Solution:
    def convertToBase7(self, num: int) -> str:
        if num == 0:
            return "0"
        ret = ""
        negative = "" if num >= 0 else "-"
        num = abs(num)
        while num > 0:
            ret = str(num % 7) + ret
            num = num // 7
        return negative + ret
1
2
3
4
5
6
7
8
9
10
11

1.3 16进制

405. 数字转换为十六进制数(Easy)

class Solution:
    def toHex(self, num: int) -> str:
        num_str = "0123456789abcdef"
        if num == 0: return "0"
        ans = []
        for _ in range(8):
            ans.append(num % 16)
            num = num // 16
            if num == 0:
                break

        for i in range(len(ans)):
            ans[i] = num_str[ans[i]]
        return "".join(ans)[::-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.4 26进制

168. Excel表列名称(Easy)

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        ans = []
        while(columnNumber > 0):
            columnNumber -= 1
            ans.append(chr(ord("A") + columnNumber % 26))
            columnNumber = columnNumber // 26

        return "".join(ans)[::-1]
1
2
3
4
5
6
7
8
9

2、阶乘

2.1 阶乘的尾部有多少0

172. 阶乘后的(Medium)

方法一：数学
n! 尾零的数量即为 n!中因子10的个数，而 10=2×5。由于质因子 5 的个数不会大于质因子 2 的个数，可以仅考虑质因子 5 的个数。遍历 [1,n]计算所有的质因子5的个数即可。

class Solution:
    def trailingZeroes(self, n: int) -> int:
        ans = 0
        for i in range(5, n + 1, 5):
            while i % 5 == 0:
                ans += 1
                i //= 5
        return ans
1
2
3
4
5
6
7
8

方法二：
对于 N 的阶乘，N!=1×2×3×4×5×6×……×N

从能拿出 5 的每个数中拿出一个 5，可以拿出 5 的数为 5，10，15，20，25……，也就是说能拿出5的数有N/5个，这些数拿出一个 5，变为1，2，3，4，5，6，……N/5
再从这些数中能拿出 5 的每个数中拿出一个 5，能拿出5的数有N/5²个，这些数变为1，2，3，4，5，6，……N/5²
继续拿，直到所有的数都拿不出5，即N/5ⁿ<=0
所以能拿出的 5 的总数为N/5 + N/5² + N/5³ + …

class Solution:
    def trailingZeroes(self, n: int) -> int:
        ans = 0
        while n:
            n //= 5
            ans += n
        return ans
1
2
3
4
5
6
7

3、字符串加法减法

3.1 二进制加法

67. 二进制求和(Easy)

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        res = ""
        i, j = len(a)-1, len(b)-1
        cur = 0
        while cur > 0 or i >= 0 or j >= 0:
            if i >= 0 and a[i] == '1':
                cur += 1
            if j >= 0 and b[j] == '1':
                cur += 1
            i -= 1
            j -= 1
            res = str(cur%2) + res
            cur = cur //2
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.2 字符串加法

415. 字符串相加(Easy)

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        res = ""
        i, j = len(num1) - 1, len(num2) - 1
        cur = 0
        while cur > 0 or i >= 0 or j >= 0:
            if i >= 0:
                cur += int(num1[i])
                i -= 1
            if j >= 0:
                cur += int(num2[j])
                j -= 1
            res = str(cur % 10) + res
            cur = cur // 10
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4、相遇问题

4.1 移动最少的次数使所有的数组元素都相等

方法一:排序
将元素排序，最终肯定是要将所有的元素移动到中间的位置，首位两个数移动的距离之和为 nums[j]-nums[i]。

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        sort_nums = sorted(nums)
        res = 0
        for i in range(len(nums)//2):
            res += sort_nums[-i-1] - sort_nums[i]
        return res
1
2
3
4
5
6
7

5、多数投票问题

5.1 找出数组中出现次数大于 n/2 的元素

169. 多数元素(Easy)
把不相等的数抵消，剩下的一定是出现次数大于 n/2 的数。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate  = None
        count = 0
        for num in nums:
            if count == 0:
                candidate  = num
            count += (1 if num == candidate else -1)
        return candidate 
1
2
3
4
5
6
7
8
9

时间复杂度：O(nlogn)
空间复杂度：O(logn)

6、其他

6.1 平方数

367. 有效的完全平方数(Easy)

方法一：使用内置的库函数

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        return float.is_integer(pow(num, 0.5))
1
2
3

方法二：暴力

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        i = 1
        square = 1
        while square <= num:
            square = i * i
            if i * i == num:
                return True
            i = i + 1
        return False

1
2
3
4
5
6
7
8
9
10
11

时间复杂度：O(√n)
空间复杂度：O(1)

方法三：二分查找

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 1, num
        while left <= right:
            mid = (left + right) // 2
            square = mid * mid
            if square < num:
                left = mid + 1
            elif square > num:
                right = mid - 1
            else:
                return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：O(logn)
空间复杂度：O(1)

6.2 判断一个数是不是 3 的 n 次方

方法一：试除法

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        while n and n % 3 == 0:
            n = n // 3
        return n == 1
1
2
3
4
5

时间复杂度：O(logn)
空间复杂度：O(1)

方法二：判断是否为最大 3 的幂的约数
在题目给定的 32 位有符号整数的范围内，最大的 3 的幂为 3¹⁹=1162261467。我们只需要判断 n 是否是 3¹⁹的约数即可。
这里需要特殊判断n是负数或 0 的情况。

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        return n > 0 and (3**19) % n == 0
1
2
3

时间复杂度：O(1)
空间复杂度：O(1)

6.3 乘积数组

238. 除自身以外数组的乘积(Medium)

方法一：分别构造左右乘积数组

先介绍一种空间复杂度为 O(n) 的方法，定义两个数组 left[] 和 right[]，left[i] 表示 i 元素之前的所有元素的乘积，right[i] 表示 i 元素之后的所有的元素乘积。则 left[] * right[] 就是除 i 元素外所有元素的乘积。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left = [1] * n
        right = [1] * n
        res = [1] * n
        for i in range(1, n):
            left[i] = left[i - 1] * nums[i - 1]
        for i in range(n - 2, -1, -1):
            right[i] = right[i + 1] * nums[i + 1]
        for i in range(n):
            res[i] = left[i] * right[i]
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度：O(n)
空间复杂度：O(n)

方法二：空间优化
将返回数组计算为左乘积数组，left[i] 就表示 i 元素之前的所有元素的乘积，从右向左遍历数组，每到一个位置，令整数right = right * nums[i+1]，保证 right 等于该位置之后所有元素乘积。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [1] * n
        right = 1
        for i in range(1, n):
            res[i] = res[i - 1] * nums[i - 1]

        for i in range(n - 2, -1, -1):
            right = right * nums[i + 1]
            res[i] = res[i] * right

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：O(n)
空间复杂度：O(1)

6.4 找出数组中的乘积最大的三个数

628. 三个数的最大乘积(Easy)

数组中可能会出现负数，找出数组中最大的三个数 max1, max2, max3 和最小的两个数 min1, min2结果为 max(max1*max2*max3, max1*min1*min2)

max1, max2, max3：最大的三个数，max1 > max2 > max3
min1, min2：最小的两个数，min1 < min2

先令a,b,c为float(‘-inf’),d,e为float(‘inf’)，遍历数组，更新最大的三个数和最小的两个数

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        max1 = max2 = max3 = float('-inf')
        min1 = min2 = float('inf')
        for num in nums:
            if num > max1:
                max1, max2, max3 = num, max1, max2
            elif num > max2:
                max2, max3 = num, max2
            elif num > max3:
                max3 = num
            if num < min1:
                min1, min2 = num, min1
            elif num < min2:
                min2 = num
        return max(max1 * max2 * max3, max1 * min1 * min2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 时间复杂度：O(N)
• 空间复杂度：O(1)