[LeetCode] Power and Sqrt | C语言实现幂和开方运算

Power(x, n) | 实现幂运算

Implement pow(x, n).

思路1: 分治

恰如1+2+3+…+n的解决方案，pow(x,n)也可优化拆解

二分法：x^n = x^(n/2) * x^(n/2) * x^(n%2)
时间复杂度：O(logn), 空间复杂度O(1)

1
2
3
4
5
6
7
8
9
int power(int x, int n) {
    if(n==0)
        return 1;
    int res = power(x,n/2);
    if(n%2 != 0)
        return res*res*x;
    else
        return res*res;
}

当然，也可以采用三分法、四分法，相应的可以降低logn的底数，但增加了x^(x%2)计算过程的复杂性,具体性能差异不明显。

思路2: 循环

最原始的实现：while(n–) pow*=x;

时间复杂度：O(n), 空间复杂度O(1)

1
2
3
4
5
6
7
8
int power(int x, int n) {
    if(n==0)
        return 1;
    int res = 1;
    while(n--)
        res *= x;
    return res;
}

总结

分治的思想，就是一个大的问题分解为更小规模的几个同类问题。
一般此类解法与递归相配合使用，关键在于找到问题分解的方式。

Sqrt(x) | 实现开方运算

Implement int sqrt(int x).
Compute and return the square root of x.
返回x的平方根

思路

  • 输入为int，返回为int
  • m^2=x，求m，最简单粗暴的方式时遍历[1, x]的所有值
  • 改进方案则考虑减少遍历过程的次数，二分法遍历

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Sqrt(x)
//LeetCode: https://leetcode.com/problems/=_=
#include<stdio.h>

int sqrt(int x) {
    if(x<2)
        return x;
    int min=1, max=x/2;
    //int mid = (min+max)/2;//改用下面的方式，避免溢出
    int mid = min + (max - min)/2;
    while(mid >min && mid < max){
        //if(mid*mid<x) //改用下面的方式，避免溢出
        if(mid<x/mid)
            min=mid;
        else if(mid>x/mid)
            max=mid;
        else
            return mid;
        mid = min + (max - min)/2;
    }
    return mid;
}
void main(){
    int x = 99;
    int res = sqrt(x);
    printf("Squre root for %d is: %d\n", x, res);
}

总结

  1. x的平方根<=x/2, 因此遍历范围可缩小为[1,x/2]
  2. 注意避免整数溢出的操作，如(min+max)/2变更为min+(max-min)/2，mid*mid<x变更为mid<x/mid
  3. 特殊情况的处理：x=0,1时，直接范围x即可，理论上x不应等于0，但对于x=0的情况，这里不做异常处理，直接返回