国外做giveaway的网站猎头公司logo
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
思路分析
难点分析
- 超过进制最大范围之后如何准确映射到其他进制
特别是ABCDEF这种情况，简单的方式是大量采用if判断，但是这样会出现写了一坨，最后写不下去 - 需要对结果进行一次转转置
- 需要判断负号
实现方案
- 定义大小为16的数组，保存的是2到16的各个进制的值对应的标记
这样赋值时只计算下标，不必考虑不同进制的转换关系 - Java使用StringBuffer完成数组转置等功能，如果不记得这个方法，工作量直接飙升
- 通过一个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