学步园

昨天听同学说有小米的笔试，几经辗转才过去，但是已经迟到将近半个小时了，本来就一个半小时的时间，搞得挺紧张的。

题目不是很难，两道算法题

1 一个有序数组经过循环移位，但是不知道移了多少位，要求查找n，并给出时间、空间复杂度

思路：先通过二分查找求出移了多少位，也就是最大值和最小值相接的地方

然后，通过比较，就知道n在前一部分查找，还是后一部分，查找过程直接用二分法

时间复杂度是0（n），空间是O(1)

求移位的我是这么写的

int l=0, h=len-1;
while(l<=h)
{
    mid = (l+h)/2;
     if(l==h) break;
     else if(a[l]<a[mid])  l = mid +1;
           else h=mid-1;
}

最后l所指向的就是最大值，那么l+1就是最小值

2 剑指offer里的一道题

double Power( double base, int exponent);

#include "stdafx.h"
#include <math.h>

bool g_InvalidInput = false;
bool equal(double num1, double num2);
double PowerWithUnsignedExponent(double base, unsigned int exponent);
 
double Power(double base, int exponent)
{
    g_InvalidInput = false;
 
    if(equal(base, 0.0) && exponent < 0)
    {
        g_InvalidInput = true;
        return 0.0;
    }
 
    unsigned int absExponent = (unsigned int)(exponent);
    if(exponent < 0)
        absExponent = (unsigned int)(-exponent);
 
    double result = PowerWithUnsignedExponent(base, absExponent);
    if(exponent < 0)
        result = 1.0 / result;
 
    return result;
}
 
double PowerWithUnsignedExponent(double base, unsigned int exponent)
{
    if(exponent == 0)
        return 1;
    if(exponent == 1)
        return base;

    double result = PowerWithUnsignedExponent(base, exponent >> 1);
    result *= result;
    if((exponent & 0x1) == 1)
        result *= base;

    return result;
}

bool equal(double num1, double num2)
{
    if((num1 - num2 > -0.0000001)
        && (num1 - num2 < 0.0000001))
        return true;
    else
        return false;
}

需要注意的就是浮点数要和0进行比较，只要足够接近，就认为是0

如果底数为0，那么指数不能为负数

递归求解时，可以优化如果要是偶数 结果为(a^(x/2))^2

如果为奇数 结果为(a^(x/2))^2*a，递归不要忘了写退出条件，我就忘了

指数如果为负数，转换成正数去做，这一步也忘了。

有个填空：

1

while(i<n)
{
   i*=2;
   for(int j=0; j<i; j++);
}

问时间复杂度

如果只有i*=2，肯定是log2 n，但是下面还有从0到i的循环，不太会算，写了个nlogn

2 还有一道题是爬楼梯，一个可以爬1个，2个，3个问有多少种方法

f(n) = f(n-1)+f(n-2)+f(n-3)，可以直接递推，不是递归，递归就麻烦了，递推很简单

3 有道题是-1和无符号数进行比较，因为都要转换成无符号数，所以-1是无符号中的最大值，有的时候还处在循环中，其实就是个语法陷阱，知道了就不难了。