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

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 = 1for i in nums:if i == 0:ans = 0elif i < 0:ans = -ansreturn ans

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 = 0for i in range(1, n+1):while i % 5 == 0:count += 1i //= 5return count

代码2：

class Solution:def trailingZeroes(self, n: int) -> int:count = 0while n:n //= 5count += nreturn count

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)  # 4print(4 % -10)  # -6
print(6 % -10)  # -4
print(-4 % -10)  # -4
print(-6 % -10)  # -6

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

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 Falseelif x == 0:return True# 计算后半部分反转的数字reversed_number = 0while x > reversed_number:reversed_number = reversed_number * 10 + x % 10x //= 10# 注意区分数字长度为奇数和偶数的情况# 奇数：判断 x == reversed_number // 10# 偶数：判断 x == reversedreturn x == reversed_number // 10 or x == reversed_numberif __name__ == '__main__':print(isPalindrome(-1))print(isPalindrome(10))print(isPalindrome(0))print(isPalindrome(1221))print(isPalindrome(2221))

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  余 27进制表示 203  2*7^2 + 0*7^1 + 3*7^0 = 101

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

代码实现

def convertToBase7(num: int):if num == 0:return "0"sign = num < 0res = ""if sign:num *= -1while num:res = str(num % 7) + resnum //= 7if sign:res = "-" + resreturn resif __name__ == '__main__':print(convertToBase7(-101))  # -203print(convertToBase7(0))  # 0print(convertToBase7(101))  # 203print(convertToBase7(7))  # 10

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 1M *= signsb = []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 //= Nif sign < 0:sb.append("-")sb.reverse()return "".join(sb)if __name__ == '__main__':print(convert(100, 7))  # 202print(convert(11, 16))  # Bprint(convert(-100, 7))  # -202