算法通关村十三关-青铜：数字与数学基础问题

1.数字统计专题

统计特定场景下的符号或数字个数等

1.1符号统计

LeetCode1822 数组元素积的符号
https://leetcode.cn/problems/sign-of-the-product-of-an-array/description/

思路分析

如果将所有的数都乘起来，再判断正负，工作量大，还有可能溢出
实践发现，一个数是 -100 和 -1，对符号的贡献是一样的，只需要看有多少个负数，就能判断最后乘积的符号

代码实现

class Solution:
    def arraySign(self, nums: List[int]) -> int:
        ans = 1
        for i in nums:
            if i == 0:
                ans = 0
            elif i < 0:
                ans = -ans
        return ans
1
2
3
4
5
6
7
8
9

1.2 阶乘0的个数

面试题 16.05 设计一个算法，算出n阶乘有多少个尾随0
https://leetcode.cn/problems/factorial-zeros-lcci/

思路分析

如果硬算，一定会超时；
其实统计有多少个0，实际上是统计2的倍数和5的倍数一起出现多少对；
因为2的倍数出现的次数一定是大于5的倍数出现的次数，因此我们只需要检查5的倍数的出现的次数就好了；

统计 5，10，15 … 5*n 这样5的整数倍项出现的个数
其中，25 = 5^2 相当于两个5，会出现两个0，5^n将会出现n个0

尾随0的个数 = 5的倍数的个数 + 25的倍数的个数 + 125倍数的个数 + … + 5^n的倍数的个数
尾随0的个数 = 5的n次方的倍数的个数

代码实现

代码1：符合要求，但耗时较长

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

代码2：

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

2.溢出问题

重要，只要设计到输入一个数字，都可能遇到
典型的题目有三个：数字反转、将字符串转成数组和回文数

java int 32位 [-2^31, 2^31-1]
python 无需考虑溢出

2.1整数反转

LeetCode 7. 整数反转
https://leetcode.cn/problems/reverse-integer/

思路分析

关键点

• 如何进行数字反转？
• 如何判断溢出？

代码实现

python和java中取余（%）的差异

print(4 % 10)  # 4
print(6 % 10)  # 6
print(-4 % 10)  # 6
print(-6 % 10)  # 4

print(4 % -10)  # -6
print(6 % -10)  # -4
print(-4 % -10)  # -4
print(-6 % -10)  # -6
1
2
3
4
5
6
7
8
9

public class temp {
    public static void main(String[] args) {
        System.out.println(4 % 10); // 4
        System.out.println(6 % 10); // 6
        System.out.println(-4 % 10); // -4
        System.out.println(-6 % 10); // -6

        System.out.println(4 % -10); // 4
        System.out.println(6 % -10); // 6
        System.out.println(-4 % -10); // -4
        System.out.println(-6 % -10); // -6
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.2字符串转整数

LeetCode8

2.3回文数

LeetCode9

思路分析

想法1：

• 数字自身直接反转，将反转后的数字与原始数字进行比较
• 如果相同，就是回文；否则，不是回文
• 缺点：可能会遇到溢出问题（不予采纳）

想法2：
为避免想法1中的溢出问题，考虑只反转 int 数字的一半
如果是回文，则后半部分反转后应该与原始数字的前半部分相同

代码实现

def isPalindrome(x: int):
    # 特殊情况
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    elif x == 0:
        return True

    # 计算后半部分反转的数字
    reversed_number = 0
    while x > reversed_number:
        reversed_number = reversed_number * 10 + x % 10
        x //= 10

    # 注意区分数字长度为奇数和偶数的情况
    # 奇数：判断 x == reversed_number // 10
    # 偶数：判断 x == reversed
    return x == reversed_number // 10 or x == reversed_number


if __name__ == '__main__':
    print(isPalindrome(-1))
    print(isPalindrome(10))
    print(isPalindrome(0))
    print(isPalindrome(1221))
    print(isPalindrome(2221))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

3.进制专题

3.1七进制数

LeetCode504
给定一个整数 num，将其转化为7进制，并以字符串的形式输出，其中 -10^7 <= num <= 10^7

思路分析

数字7进制
10进制 0 1 2 3 4 5 6
7进制 0 1 2 3 4 5 6

10进制 7 8 9 10 11 12 13
7进制 10 11 12 13 14 15 16

转7进制的主要过程：循环取余和整除，最后将所有的余数反过来即可

举例：10进制 101

101 ÷ 7 = 14 余 3
14  ÷ 7 = 2  余 0
2   ÷ 7 = 0  余 2

7进制表示 203  2*7^2 + 0*7^1 + 3*7^0 = 101
1
2
3
4
5

注：如果num<0，先对num取绝对值，再转换

代码实现

def convertToBase7(num: int):
    if num == 0:
        return "0"
    sign = num < 0
    res = ""
    if sign:
        num *= -1

    while num:
        res = str(num % 7) + res
        num //= 7

    if sign:
        res = "-" + res

    return res


if __name__ == '__main__':
    print(convertToBase7(-101))  # -203
    print(convertToBase7(0))  # 0
    print(convertToBase7(101))  # 203
    print(convertToBase7(7))  # 10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.2进制转换

给定一个十进制数M，以及需要转换的进制数N，将十进制数M转换为N进制数，M是32为整数，2<=N<=16

思路分析

难点分析

1. 超过进制最大范围之后如何准确映射到其他进制
   特别是ABCDEF这种情况，简单的方式是大量采用if判断，但是这样会出现写了一坨，最后写不下去
2. 需要对结果进行一次转转置
3. 需要判断负号

实现方案

1. 定义大小为16的数组，保存的是2到16的各个进制的值对应的标记
   这样赋值时只计算下标，不必考虑不同进制的转换关系
2. Java使用StringBuffer完成数组转置等功能，如果不记得这个方法，工作量直接飙升
3. 通过一个flag来判断整数还是负数，最后才处理

代码实现

def convert(M, N):
    """
    将10进制数M转换为N进制
    """
    sign = -1 if M < 0 else 1
    M *= sign
    sb = []
    digits = ["0", "1", "2", "3", "4", "5",
              "6", "7", "8", "9", "A", "B",
              "C", "D", "E", "F"]
    while M:
        digit = M % N
        # 通过数组解决了大量繁琐的不同进制映射的问题
        sb.append(digits[digit])
        M //= N
    if sign < 0:
        sb.append("-")
    sb.reverse()
    return "".join(sb)


if __name__ == '__main__':
    print(convert(100, 7))  # 202
    print(convert(11, 16))  # B
    print(convert(-100, 7))  # -202

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26