AlgoPressAppearance
OF16-数值的整数次方
题目描述
https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof
实现 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
解释：2^-2 = 1/22 = 1/4 = 0.25
提示：
$$ -100 < x < 100 \ -2^{31} <= n <= 2^{31-1} \ -10^4 <= x^n <= 10^4 $$
思路分析
题目不得使用库函数，不需要考虑大数问题，所以我们可以用常规的解法。
需要注意的点
n 是 “负号” 的处理， 需要将结果用去除1
x是负数处理，根据n是否是单数，是单数则最后带符号，否则是正数
以上两个处理完，就可以按照正常的规则处理，注意递归可能超时，需要使用循环的方式 折半乘方 来计算，注意是否单数
注意 负数的溢出，当 n 是 -2147483648 时， -n 同样还是这个数，会产生死循环
https://www.cnblogs.com/gexin/p/7485231.html
对int类型最小值INT_MIN取负值结果不变
在32位系统中，int类型的最大值是0x7fffffff（即除了最高的1Bit其他31位都为1），而最小值是0x80000000（除了最高1bit，其他31位都为0）。
显然，对于最小值求负数是不存在的，为什么会使最小值本身呢？
这是由于在计算负运算时，是针对int类型数据进行“取反加一”操作。这样对于最小值而言，“取反加一”还是本身保持不变。
另外，针对整数的计算，都是从位的角度的进行的。比如，int类型数据的最大值（0x7fffffff ）加1，会得到int类型的最小值（0x80000000）；而对于unsigned int类型的0x7fffffff 加1 ，也会得到0x80000000，这在位的角度来看都是一致的。
c#include <stdio.h> int main() { int a = 0x80000000; int b = 0x7fffffff; printf("INT_MIN and its' negative is :\n %d, %d\n\n", a, -a); printf("INT_MAX and INT_MAX+1 is :\n %d, %d\n\n", b, b+1); printf("unsigned(INT_MAX) and unsigned(INT_MAX+1) is :\n %u, %u\n\n", b, b+1); return 0; } /*******输出如下****************/ Process started >>> INT_MIN and its' negative is : -2147483648, -2147483648 INT_MAX and INT_MAX+1 is : 2147483647, -2147483648 unsigned(INT_MAX) and unsigned(INT_MAX+1) is : 2147483647, 2147483648 <<< Process finished. (Exit code 0)
实现代码
第一次实现，超出时间限制
csharp
public class Solution {
public double MyPow(double x, int n) {
if(n == 0){
return 1;
}
if(n == 1){
return x;
}
//指数负数处理
if(n < 0){
return 1.0 / MyPow(x, -n);
}
//x负数处理
if(x < 0){
if(n % 2 == 1){
return -MyPow(-x, n);
}
else{
return MyPow(-x,n);
}
}
//折半计算
double result = MyPow(x, n/2) * MyPow(x, n/2);
if(n % 2 == 1){
result *= x;
}
return result;
}
}
第二次实现
csharp
public class Solution {
public double MyPow(double x, int n) {
if(n == 0){
return 1;
}
if(n == 1){
return x;
}
//指数负数处理
if(n < 0){
return 1.0 / MyPow(x, -n);
}
//x负数处理
if(x < 0){
if(n % 2 == 1){
return -MyPow(-x, n);
}
else{
return MyPow(-x,n);
}
}
//折半计算
double result = 1.0;
while(n > 0){
//如果是2的倍数+1，那么就乘以这个数，在计算倍数
if(n & 1 == 1){
result *= x;
}
//折半n,并且将x翻倍，最终的时候 n == 1 会乘以到 result 里面
x = x * x;
n>>=1;
}
return result;
}
}
改代码执行的时候，会溢出
1.00000
-2147483648
Stack overflow : repat 6249651 times
检查这种情况应该是 n 负数处理的时候出错了
-(-2147483648) == ?
//执行下面代码可以知道 -m = m, 都会输出 -2147483648，所以会重复不停计算
int m = -2147483648;
Console.WriteLine(m);
Console.WriteLine(-m);
需要将代码
csharp
if(n < 0){
return 1.0 / MyPow(x, -n);
}
改成
csharp
if(n < 0){
return 1.0/(x * MyPow(x, -(n+1)));
}
参考线上代码 : 十分精炼
csharp
public class Solution {
public double MyPow(double x, int n) {
double ans = 1.0;
if(n==0) return ans;
if(n<0)
{
ans = MyPow(1/x,-(n+1));//防溢出
ans*=1/x;
}
while(n>0)
{
if((n&1)==1) ans*=x;
x*=x;
n>>=1;
}
return ans;
}
}
第二遍做：注意折半的时候，放大 x *= x;
csharp
public class Solution {
public double MyPow(double x, int n) {
if(x == 0){
return 0;
}
if(n == 0){
return 1;
}
//判断n负数
double result = 1.0;
if(n < 0){
//考虑到 n = int.MinValue 时， -n 还是这个值，所以不能直接用 MyPower(1/x,-n)
result = MyPow(1 / x, -(n+1));
result *= 1/x;
}
while(n > 0){
//将 n 除以 2， 那么原来的值就 平方，如果有单数，则 额外乘以 x
if( n % 2 == 1){
result *= x;
}
x*=x;
n = n / 2;
}
return result;
}
}
参考代码：复习20220503
csharp
public class Solution {
public double MyPow(double x, int n) {
//直接循环计算会超时
double result = 1.0;
if(n == 0){
return result;
}
if(n < 0){
// -(n+1) 放置溢出 int.MinValue 溢出
result = MyPow(1/x, -(n+1));
result *= 1/x;
return result;
}
while(n > 0){
//指数逐渐缩小
if(n % 2 == 1){
result *= x;
}
n = n/2;
//根数逐渐放大
x *= x;
}
return result;
}
}