【DFS】春来我不先开口,哪个虬儿敢做声 - 3.快速幂
本篇博客给大家带来的是DFS深度优先遍历的解法技巧,在后面的文章中题目会涉及到回溯和剪枝,遇到了一并讲清楚.
🐎文章专栏: DFS
🚀若有问题 评论区见
❤ 欢迎大家点赞 评论 收藏 分享
如果你不知道分享给谁,那就分享给薯条.
你们的支持是我不断创作的动力 .
王子,公主请阅🚀
要开心
要快乐
顺便进步
1. 快速幂
题目链接:50. Pow(x, n)
题目内容:
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，x^n ）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解法一: 暴力枚举
循环遍历n, x在循环中自乘, 如果n太大,则会超出时间限制.
解法二: 递归实现快速幂
举两个例子讲清楚快速幂的原理
假设x = 3;
1. 当n为偶数时:
当n为偶数时, 3^n = 3 ^n/2 * 3^n/2;
2. 当n为奇数时:
当n为奇数时3^n = 3 ^n/2 * 3^n/2 * 3
综上所述, 不难得出递归出口即为,当n = 0时,返回1即可.
代码实现
classSolution{publicdoublemyPow(double x,int n){return n <0?1.0/pow(x,-n):pow(x,n);}publicdoublepow(double x,int n){if(n ==0)return1.0;double tmp =pow(x,n/2);return n %2==0? tmp*tmp : tmp*tmp*x;}}本篇博客到这里就结束啦, 感谢观看 ❤❤❤
🐎期待与你的下一次相遇😊😊😊
