前言🌧️
算法,对前端人来说陌生又熟悉,很多时候我们都不会像后端工程师一样重视这项能力。但事实上,算法对每一个程序员来说,都有着不可撼动的地位。
因为开发的过程就是把实际问题转换成计算机可识别的指令,也就是《数据结构》里说的,「设计出数据结构,在施加以算法就行了」。
当然,学习也是有侧重点的,作为前端我们不需要像后端开发一样对算法全盘掌握,有些比较偏、不实用的类型和解法,只要稍做了解即可。
题目🦀
难度中等
实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。
示例 1:
输入:x = 2.00000, n = 10 输出:1024.00000
示例 2:
输入:x = 2.10000, n = 3 输出:9.26100
示例 3:
输入:x = 2.00000, n = -2 输出:0.25000 解释:2-2 = 1/22 = 1/4 = 0.25
提示:
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
解题思路🌵
- 二分法
- 需要考虑一些特殊案例:x的0次方为1、x的1次方为x、x的-1次方为1/x
- 一些性能优化的细节:用右移运算代替/2、用位与运算代表求余运算来判断一个数是奇数还是偶数(位运算的效率比乘除法及求余运算的效率要高很多)
- 思路优化方面:假设我们要求一个数的32次方,如果我们已经知道了它的16次方,那么只要在16次方的基础上再平方一次就ok了
- 而16次方是8次方的平方 ;依此类推,我们求32次方只需要做5次乘法,先求平方,在平方的基础上求4次方,在4次方的基础上求8次方,在8次方的基础上求16次方,最后在16次方的基础上求32次方
源码🔥
/** * @param {number} x * @param {number} n * @return {number} */ var myPow = function(x, n) { if(n===0){ return 1 } if(n===1){ return x } if(n===-1){ return 1/x } let result=myPow(x,n>>1) result*=result //表示n为奇数 if((n&1)==1){ result=result*x } return result };
时间复杂度: O(log2 N) 二分的时间复杂度为对数级别
空间复杂度 : O(1)
结束语🌞
那么鱼鱼的LeetCode算法篇的「LeetCode」剑指Offer-16数值的整数次方⚡️
就结束了,算法这个东西没有捷径,只能多写多练,多总结,文章的目的其实很简单,就是督促自己去完成算法练习并总结和输出,菜不菜不重要,但是热爱🔥,喜欢大家能够喜欢我的短文,也希望通过文章认识更多志同道合的朋友,如果你也喜欢折腾
,欢迎加我好友
,一起沙雕
,一起进步
。