核心代码模式和ACM模式的介绍
我现在见到最多的两种模式分别是
① leetcode为代表的核心代码模式;
② y总acwing、洛谷、北大的POJ、杭电的HDOJ、浙大ZOJ还有俄罗斯的cf等等常使用的ACM模式了。
核心代码模式
核心代码模式是这种:
用可爱的两数之和做做演示吧
可以自己着手去熟悉一下嗷~
题目链接
ACM模式
ACM模式是这种的:
题目链接
看了两张图和图中的描述,大家大致清楚了两种模式的大致的区别了,其他啰嗦的说了也没有什么很大的用,就不赘述啦~
当前这个专栏是leetcode的核心代码模式了,然后C和C++的代码都会有的
幂和对数的基础知识
① 关于幂的知识
② 关于对数的知识
③ 换底公式
现学现用
第一题 231. 2 的幂
1、 模拟的写法,学会用无符号来防止溢出;
2、 pow函数返回值为double类型
题目描述
解题报告
倘若采用模拟的方式,就是常规的将去逐一枚举,不断的迭乘2来实现2的幂的效果,在枚举的途中判断有没有符合要求的。
也可以按照数学中的想法,比如想判断16是不是2的幂了,那么直接把16放到对数函数上进行处理,想判断3是不是也可以放到对数函数中进行处理。有个小细节了,就是加上一个精度,避免精度损失导致取整出错;
对于最后一步的判定相等,切记直接使用==来进行,因为pow函数的返回值是浮点型,对于浮点数的判等依赖于两个数的差的绝地址小于某个精度时,就认为它们相等,
即使用这种方式:f a b s ( a − b ) < 1 e − 8 fabs(a-b) < 1e^{-8}fabs(a−b)<1e
−8至于精度的选择,大多数情况下都是1 e − 8 1e^{-8}1e −8
参考代码(C/C++版本)
解法一:
C语言版本,C++用这个代码也是没有问题的,
解法二:
C++用这个代码也是没有问题的,就不额外再放C++的代码了。
第二题 326. 3 的幂
唯一可取的了,是背一下2^31的数值是2147483648
题目描述
解题报告
上面一题的变型了,解题报告就不详细写啦~
参考代码(C/C++版本)
解法一:
解法二:
第三题 342. 4的幂
变型
题目描述
解题报告
这个就不写解题报告了吧~
参考代码(C/C++版本)
解法一:
解法二:
总结
今天需要掌握的了:
① 幂和对数的知识得拿捏住吧
② 时刻注意数据范围,在数据范围比较大的时候,可能会出现溢出,记住无符号类型unsigned有自动取模的功能,可以有效的解决溢出问题
③ 记住2^31是2147483648
④pow函数的返回值类型是浮点型,浮点型判等要利用精度