北京哪家做网站优化,无需域名网站建设,视频投票网站怎么做的,网站查询地址1.数字统计专题
统计特定场景下的符号或数字个数等
1.1符号统计
LeetCode1822 数组元素积的符号 https://leetcode.cn/problems/sign-of-the-product-of-an-array/description/
思路分析
如果将所有的数都乘起来#xff0c;再判断正负#xff0c;工作量大#xff0c;还…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 ans1.2 阶乘0的个数
面试题 16.05 设计一个算法算出n阶乘有多少个尾随0 https://leetcode.cn/problems/factorial-zeros-lcci/
思路分析
如果硬算一定会超时 其实统计有多少个0实际上是统计2的倍数和5的倍数一起出现多少对 因为2的倍数出现的次数一定是大于5的倍数出现的次数因此我们只需要检查5的倍数的出现的次数就好了
统计 51015 … 5*n 这样5的整数倍项出现的个数 其中25 5^2 相当于两个5会出现两个05^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, n1):while i % 5 0:count 1i // 5return count代码2
class Solution:def trailingZeroes(self, n: int) - int:count 0while n:n // 5count nreturn count2.溢出问题
重要只要设计到输入一个数字都可能遇到 典型的题目有三个数字反转、将字符串转成数组和回文数
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) # -6public 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注如果num0先对num取绝对值再转换
代码实现
def convertToBase7(num: int):if num 0:return 0sign 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)) # 103.2进制转换
给定一个十进制数M以及需要转换的进制数N将十进制数M转换为N进制数M是32为整数2N16
思路分析
难点分析
超过进制最大范围之后如何准确映射到其他进制 特别是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
