💓专栏介绍
自己写这个专栏的介绍主要是想帮自己身边关系最好的她熟悉一些算法,积累一些算法,浅培养一点算法素养吧。因为她有点小懒,让她去看y总的视频学算法也不现实,之前浅试过自己我自己设定一些层次的题,效果有点痛苦。
我自己在尝试把李煜东老师的《算法竞赛进阶指南》也做成一个专栏的,书中第一个算法讲的是位运算的,但是提供的题目就有状态压缩动态规划,对零基础相当不友好。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/5c9d12e1c71c4652ad9406ec88e93d21.png#pic_center) 前阵子看到英雄哥之前早上直播的时候在弄《算法零基础100讲》,就想结合着英雄哥设定的学习顺序,他放置的习题,结合自己的理解然后编纂这个专栏的文章,尽量日更,假如忙不过来才两天一更的。不能说我抄袭哈,我自己是买了专栏的哈(狗头保命) ![在这里插入图片描述](https://img-blog.csdnimg.cn/e9001d3041f842dea54d6ba692ff9b1b.png#pic_center)
![在这里插入图片描述](https://img-blog.csdnimg.cn/0b6cbdd3720c4e79921d6246d10e3491.png#pic_center)
💓核心代码模式和ACM模式的介绍
我现在见到最多的两种模式分别是 ① leetcode为代表的核心代码模式; ② y总acwing、洛谷、北大的POJ、杭电的HDOJ、浙大ZOJ还有俄罗斯的cf等等常使用的ACM模式了。
这两种模式各有所长吧,我只是练习ACM模式偏多一点,对核心代码模式不是特别的熟悉 ![在这里插入图片描述](https://img-blog.csdnimg.cn/e9c6fe1ce5cc4a9c9e7bb2ab19a7d366.gif#pic_center)
📁核心代码模式
核心代码模式是这种: ![在这里插入图片描述](https://img-blog.csdnimg.cn/a50c3252c87e4b45ab2ce376c3534748.png#pic_center) 用可爱的两数之和做做演示吧 ![在这里插入图片描述](https://img-blog.csdnimg.cn/c53a2621ad6741b28dd6f883a7ae9faf.png#pic_center) 可以自己着手去熟悉一下嗷~ 题目链接
🔖ACM模式
ACM模式是这种的: ![在这里插入图片描述](https://img-blog.csdnimg.cn/60c2c1fc1b734e02991c4e11c7f036b7.png#pic_center) 依旧拿出咱可爱的两数之和吧,反复折磨(doge) ![在这里插入图片描述](https://img-blog.csdnimg.cn/f1409c0cd599401f847de360ff51d1db.png#pic_center) ![在这里插入图片描述](https://img-blog.csdnimg.cn/417c45ce611246049ad7de7c71b8a360.png#pic_center) 题目链接 看了两张图和图中的描述,大家大致清楚了两种模式的大致的区别了,其他啰嗦的说了也没有什么很大的用,就不赘述啦~ 当前这个专栏是leetcode的核心代码模式了,然后C和C++的代码都会有的。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/9beca4572a7d45dd87e9b19cf9ccf84c.png)
![在这里插入图片描述](https://img-blog.csdnimg.cn/0b6cbdd3720c4e79921d6246d10e3491.png#pic_center)
💓幂和对数的基础知识
?小建议
幂和对数应该是初中知识吧,之前听y总讲过,咱们现在做的算法题其实大部分是小学、初中、高中奥数的题,咱们现在这个阶段,倘若用数学的想法去弄,有些甚至可以用眼睛看出结果的 ![在这里插入图片描述](https://img-blog.csdnimg.cn/4cb3e65b83ee47d09a7690a00e74d62c.png) 就比如这种题,但是落实到代码上,好像就没有那么轻松了,所有y总说,算法题也是训练大家的代码实现能力的。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/4dfa2a6513a3450a9ec7294cd42cb2f2.gif#pic_center) 所以希望一定要自己去敲出来,特别是某人,不要看着会了,就不去落实到代码上了。
🍏① 关于幂的知识
![在这里插入图片描述](https://img-blog.csdnimg.cn/4f74ec33c5c8475eb05a0a1ed2a2e080.png)
🍎② 关于对数的知识
![在这里插入图片描述](https://img-blog.csdnimg.cn/b250cc90245843889604d86d31edfcd3.png)
🍑③ 换底公式
![在这里插入图片描述](https://img-blog.csdnimg.cn/2b0a6081362a4808a32bdbbbba494ef2.png)
![在这里插入图片描述](https://img-blog.csdnimg.cn/0b6cbdd3720c4e79921d6246d10e3491.png#pic_center)
💓现学现用^ - ^
🍪第一题 231. 2 的幂
1、 模拟的写法,学会用无符号来防止溢出; 2、 pow函数返回值为double类型
💒题目描述
![在这里插入图片描述](https://img-blog.csdnimg.cn/e3481fef0376494687ddd6cbd61e137b.png) 原题链接
🌟解题报告
倘若采用模拟的方式,就是常规的将去逐一枚举,不断的迭乘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++用这个代码也是没有问题的, ![在这里插入图片描述](https://img-blog.csdnimg.cn/13d0d947f372481296b1f99fccf108fd.png) 解法二: C++用这个代码也是没有问题的,就不额外再放C++的代码了。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/6c708ff9818944d9a1de3ee772b1f497.png)
![在这里插入图片描述](https://img-blog.csdnimg.cn/0b6cbdd3720c4e79921d6246d10e3491.png#pic_center)
🍩第二题 326. 3 的幂
唯一可取的了,是背一下2^31的数值是2147483648
💒题目描述
![在这里插入图片描述](https://img-blog.csdnimg.cn/83b6699e998a46c888f6bce68f3ab347.png) 题目链接
🌟解题报告
上面一题的变型了,解题报告就不详细写啦~ ![在这里插入图片描述](https://img-blog.csdnimg.cn/2dec6c23107e452dbf659ece95a809e0.png)
🌻参考代码(C/C++版本)
解法一: ![在这里插入图片描述](https://img-blog.csdnimg.cn/b90bb717d667496b810ac6455fbce37d.png) 解法二: ![在这里插入图片描述](https://img-blog.csdnimg.cn/5130f4e93c7d4f9d92de96a2551fd624.png)
![在这里插入图片描述](https://img-blog.csdnimg.cn/0b6cbdd3720c4e79921d6246d10e3491.png#pic_center)
🍰第三题 342. 4的幂
变型
💒题目描述
![在这里插入图片描述](https://img-blog.csdnimg.cn/7663a0f32bbb4363bc76180cef9cc162.png) 题目链接
🌟解题报告
这个就不写解题报告了吧~
🌻参考代码(C/C++版本)
解法一: ![在这里插入图片描述](https://img-blog.csdnimg.cn/7e79c4396d944f2586baa899e073aa42.png) 解法二: ![在这里插入图片描述](https://img-blog.csdnimg.cn/7cc484d0dcc843cdb987627e180811ec.png)
![在这里插入图片描述](https://img-blog.csdnimg.cn/0b6cbdd3720c4e79921d6246d10e3491.png#pic_center)
💓总结
今天需要掌握的了: ① 幂和对数的知识得拿捏住吧
② 时刻注意数据范围,在数据范围比较大的时候,可能会出现溢出,记住无符号类型unsigned 有自动取模的功能,可以有效的解决溢出问题
③ 记住2^31 是2147483648
④pow函数 的返回值类型是浮点型,浮点型判等要利用精度。
|