重写幂次函数

pow(double base, int exp);

首先要写一些测试用例：

1.base=0时，exp<=0是不合法的输入。2.base不等于0，exp<0时，要计算的值是base的|exp|次幂，然后取倒数。3.base不等于0，exp>0时，直接计算base的|exp|次幂。

代码实现：

double myPow(double x, int n) {	if(equalZero(x, 0.0) && n <= 0)	{		return 0.0;	}		int absExp = n;	if(n < 0)	{		absExp = -n;	}		double res = getPowWithAbsExp(x, absExp);		if(n < 0)		res = 1.0 / res;			return res;}double getPowWithAbsExp(double base, int absExp){	double result = 1.0;	for(int i = 0; i < absExp; ++i)	{		result *= base;	}		return result;}bool equalZero(double num1, double num2){	double delt = 0.0001;	if((num1 - num2 < delt) && (num1 - num2 > -delt))	{		return true;	}	else 	{		return false;	}}//equalZero()

　　但是这时新的问题来了，如果exp很大，那么这个样子的连乘，肯定需要很大的时间复杂度。这里利用到了归并排序的思想，把相同的小的子问题，配对计算，得出中等的问题，然后再把中等的问题配对计算，最后得到大的问题的解。这一点很像中用到的方法。

所以新的getPowWithAbsExp函数可以这样写：

double getPowWithAbsExp(double base, int absExp){	double result = 0.0;	if(absExp == 0)		return 1.0;	if(absExp == 1)		return base;			result = getPowWithAbsExp(base, absExp / 2);	result *= result;		if(absExp % 2 != 0)		result *= base;		return result;}

　　这样就通过归并的方法，大大的减少了计算乘法的次数。

重写memmove函数

在内存复制的时候，如果两段内存有重叠，那么就很容易产生覆盖。所以重写这个函数，对有重叠的内存的拷贝进行处理。

void* memmove(void* str1,const void* str2,int n){    char* pStr1 = (char*) str1;    const char* pStr2 = (const char*)str2;    if(pStr1 < pStr2)	//从前面开始copy	{        for(int i=0; i!=n; ++i)		{            *(pStr1++) = *(pStr2++);        }    }    else	//从后面开始copy	{        pStr1 += n-1;        pStr2 += n-1;        for(int i=0; i!=n; ++i)		{            *(pStr1--) = *(pStr2--);        }    }    return pStr1;}

　　为了避免把还未copy的内存区域覆盖掉，这里用到的解决办法就是根据两块内存的位置，从前面或者后面进行内存copy。

平方根函数

在O(logx)的时间复杂度内求解x的平方根，这个题目很容易想到二分查找。但是要注意数据溢出。

/** * @param x: An integer * @return: The sqrt of x */int sqrt(int x) {	// write your code here	int low = 0;	int high = x;	while(low <= high)	{		int mid = low + (high - low) / 2;				long long square = (long long)mid * (long long)mid;//这里一定要先做类型的转换，不然还是会数据溢出的		if(square == x)		{			return mid;		}		else if(square > x)		{			high = mid - 1;		}		else		{			long tmp = (long long)(mid + 1) * (long long)(mid + 1);			if(tmp > x)				return mid;			else				low = mid + 1;		}	}//while}