LeetCode - Medium - 50. Pow(x, n)

野性酷女 2022-11-10 05:38 164阅读 0赞

## Topic ##

*  Binary Search
 *  Math

## Description ##

[https://leetcode.com/problems/powx-n/][https_leetcode.com_problems_powx-n]

Implement `pow(x, n)`, which calculates x raised to the power n (i.e. x^n).

**Example 1**:

Input: x = 2.00000, n = 10
    Output: 1024.00000

**Example 2**:

Input: x = 2.10000, n = 3
    Output: 9.26100

**Example 3**:

Input: x = 2.00000, n = -2
    Output: 0.25000
    Explanation: 2^(-2) = 1/(2^2) = 1/4 = 0.25

Constraints:

*   − 100.0 < x < 100.0 -100.0 < x < 100.0 −100.0<x<100.0
 *   − 2 31 < = n < = 2 31 − 1 -2^\{31\} <= n <= 2^\{31\}-1 −231<=n<=231−1
 *   − 1 0 4 < = x n < = 1 0 4 -10^\{4\} <= x^\{n\} <= 10^\{4\} −104<=xn<=104

## Analysis ##

方法一：暴力算法，一个个地乘，但耗时，故弃。

方法二：递归算法，从上到下，与方法一相比，乘法的次数对数减少。

方法三：别人写的递归算法，简单优雅，特别是本方法不像方法二对n为-2147483648时需特别处理。

--------------------

PS. 对n为Integer.MIN\_VALUE(-2147483648)特殊情况，对其作出以下运算：

System.out.println(-Integer.MIN_VALUE);
    System.out.println(Math.abs(Integer.MIN_VALUE));

**两行代码皆输出为-2147483648**，与事实不符，理应是2147483648，归因于32位整数的最大值只能为2147483647，再加1便会溢出。日后注意这特殊情况。

## Submission ##

public class Pow { 
    
    	//方法二
    	public double myPow(double x, int n) { 
    		double spe = 1;
    		if (n == Integer.MIN_VALUE) { // 针对最小值，Math.abs(Integer.MIN_VALUE)还是返回Integer.MIN_VALUE
    			n++;
    			spe = x;
    		}
    
    		int num = Math.abs(n);
    		double product = helper(x, num);
    		return n > 0 ? product : 1 / (product * spe);
    	}
    
    	private double helper(double x, int n) { 
    		if (n == 0)
    			return 1;
    		if (n == 1)
    			return x;
    		double temp = helper(x, n / 2);
    		return temp * temp * ((n & 1) == 1 ? x : 1);
    	}
    
    	//方法三
    	double myPow2(double x, int n) { 
    		if (n == 0)
    			return 1;
    		if (n < 0) { 
    			n = -n;
    			x = 1 / x;
    		}
    		System.out.println(-Integer.MIN_VALUE);
    		return myPow(x * x, n / 2) * ((n & 1) == 1 ? x : 1);
    	}
    }

## Test ##

public class PowTest { 
    
    	@Test
    	public void test() { 
    		Pow obj = new Pow();
    
    		double delta = 10e-9;
    		assertEquals(1024.0, obj.myPow(2.0, 10), delta);
    		assertEquals(9.2610, obj.myPow(2.1, 3), delta);
    		assertEquals(0.25, obj.myPow(2.0, -2), delta);
    		assertEquals(1.0, obj.myPow(1.0, Integer.MAX_VALUE), delta);
    		assertEquals(1.0, obj.myPow(1.0, Integer.MIN_VALUE), delta);
    	}
    	
    	@Test
    	public void test2() { 
    		Pow obj = new Pow();
    		
    		double delta = 10e-9;
    		assertEquals(1024.0, obj.myPow2(2.0, 10), delta);
    		assertEquals(9.2610, obj.myPow2(2.1, 3), delta);
    		assertEquals(0.25, obj.myPow2(2.0, -2), delta);
    		assertEquals(1.0, obj.myPow2(1.0, Integer.MAX_VALUE), delta);
    		assertEquals(1.0, obj.myPow2(1.0, Integer.MIN_VALUE), delta);
    	}
    	
    	@Test
    	public void testOther() { 
    		assertEquals(Integer.MIN_VALUE, -Integer.MIN_VALUE);
    		assertEquals(Integer.MIN_VALUE, Math.abs(Integer.MIN_VALUE));
    	}
    	
    }

[https_leetcode.com_problems_powx-n]: https://leetcode.com/problems/powx-n/