Leetcode: pow (x, n)

2020-12-23 11:10:13

pow(x, n)

One 、 subject

Realization pow(x, n) , Computation x Of n Power function .

Example 1:

Input : 2.00000, 10
Output : 1024.00000

Example 2:

Input : 2.00000, -2
Output : 0.25000
explain : 2-2 = 1/22 = 1/4 = 0.25

Their thinking

1. To judge n Plus or minus , To make sure our bottom line is x still 1/x
2. Through the analysis of x^9 = x^4 * x^4 * x = (x^2 * x^2) * (x^2 * x^2) * x
3. Judge n Parity , It has been determined whether it needs to be considered separately
• If it's odd , Then you need to take one more ride x In itself , because Math.floor Rounding down ,9 / 2=> 4, 4 + 4 = 8, Less 1 individual
• If it's even , So there's no need to think about , It can be reduced by half
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function(x, n) {

//  analysis n
if (n === 0) return 1;
if (n === 1) return x;
if (n < 0) {

x = 1 / x;
n = -n;
}
let res = 1;
// x^7 = x^1 * x^2 * x^4
// x^9 = x^4 * x^4 * x = (x^2 * x^2) * (x^2 * x^2) * x
while (n > 0) {

// if(m Is odd ,m One of them is 1), Take more 1 Time x, Because we do rounding down
// & Express  2 The phase and of decimal digits
//  If it's odd , take x^9 give an example , So for the first time res = 1 * x, The last time was 1,res = x * x ^ 8
//  If even , take x^8 give an example , So for the first time res = 1 * x ^ 8
if ((n & 1) === 1) res *= x;
n = Math.floor(n / 2);
x *= x; // x = x^2  The bottom is squared , Every half of it , You have to square it once
}
return res;
};

LeetCode result

Execution time ：76 ms,  In all  JavaScript  Defeated in submission 95.38% Users of
Memory consumption ：39.6 MB,  In all  JavaScript  Defeated in submission 5.03% Users of

3、 ... and 、 At the end

If it's helpful to you, you can give it to the project github Order one star, This is my biggest encouragement

• flower ： Afterglow
• WX：j565017805
• addiction JS, Level co., LTD. , Learning with an open mind

Other precipitates https://chowdera.com/2020/12/20201223110937553t.html