LeetCode题目解析（C++语言版）（第14期）

（本文共939字，1图，预计阅读时间：5分钟）
01
Leetcode 50：计算x的n次幂

[h1]题目描述[/h1]实现pow(x,n)，即计算x的n次幂函数。
[h1]题目解析[/h1]在剑指offer之中，我们可以使用二进制移位来实现相应的功能，但实际上，当数字过大的时候，这个方法已经不能使用了。这个时候我们可以用二分法。步骤如下：

依旧是先判断n是不是小于零，若是，令x等于原来的倒数，n变为原来的绝对值；否则不变，然后进入第2步。
执行一个fastPow()函数，这个函数是递归调用执行。首先如果此时n=0了，那么自然结果就是1.0；然后递归调用
1. half=fastPow(x,n/2)
复制代码
，这实际上就是计算x的n/2次方的结果，然后这个时候判断n是奇数还是偶数，如果是偶数，那自然x的n次方就等于x的n/2次方乘x的n/2次方；如果是奇数，则结果就等于x的n次方就等于x的n/2次方乘x的n/2次方再乘x。

[h1]代码实现[/h1]

double fastPow(double x, long long n)

复制代码

{

复制代码

if (n == 0)

复制代码

return 1.0;

复制代码

double half = fastPow(x, n / 2);

复制代码

if (n % 2 == 0)

复制代码

return half*half;

复制代码

else

复制代码

return half*half*x;

复制代码

}

复制代码

[/code][code]double myPow(double x, int n) {

复制代码

if (x == 1.0)

复制代码

return x;

复制代码

if (n == 0)

复制代码

return 1.0;

复制代码

long long N = n;

复制代码

if (N < 0)

复制代码

{

复制代码

x = 1 / x;

复制代码

N = -N;

复制代码

}

复制代码

return fastPow(x, N);

复制代码

}

复制代码

02
leetcode 69：x的平方根（sqrt of x）

[h1]题目描述[/h1]实现

int sqrt(int x)

复制代码

函数，计算并返回x的平方根，其中x是非负整数。由于返回类型是整数，所以结果只保留整数部分，将小数部分舍去。
[h1]题目解析[/h1]

所以我们要做的事情就是让这个x(n+1)不断逼近x。由于只要求保留到整数，所以误差可以选择大一点，比如误差到0.5就可以结束逼近了。所以代码实现如下。

int mySqrt(int x) {

复制代码

if(x0.5)

复制代码

{

复制代码

res=(res+x/res)/2;

复制代码

}

复制代码

return int(res);

复制代码

}

复制代码

关注我们