《剑指offer》系列---2

1.求斐波那契数列的第N项

这个题目很简单，讲递归的书上都是用这个来讲的，但是面试的时候，如果你写个递归，那估计会让人失望的，因为递归的效率真是一个问题，你可以测试一下，输入50,基本上得到结果的时间，够你去喝杯茶了

#include <iostream>
using namespace std;

//使用递归效率太低了，甚至可能造成栈溢出
/*int fabonacci1(int n)
{
	if(n <= 0)
		return 0;
	else if(n == 1)
		return 1;
	else return fabonacci1(n-1)+fabonacci1(n-2);
}*/

int fabonacci2(int n)
{
	int num1 = 0, num2 = 1, num3 = 0;
	int i = 2;
	while(i <= n)
	{
		num3 = num1+num2;
		num1 = num2;
		num2 = num3;
		i++;
	}
	return num3;
}

int main()
{
	int ret2 = fabonacci2(5);
	int ret1 = fabonacci1(5);
	cout<<ret2<<endl;
	cout<<ret1<<endl;
	return 0;
}

剑指offer上还给我们列出了一个数学公式，我觉得就没必要掌握了，但是搞算法的同学还是应该去了解一下

2.输入一个整数，输出它的二进制表示中1的个数

这个题目考察的是我们对位运算的运用，作为一道面试题，自然，我们应当记住最好的解法

第一种：直接和1做&运算，如果最低位是1则增加1,然后整个数右移一位，再与1做与运算，这样就是下面的

/*int number_of1_in_binary(int m)
{
    int count = 0;
    while(m)
    {
        if(m&1)
            count++;
        m>>=1;
    }
    return count;
}*/

但是这样有一个缺点，如果输入的数是负数怎么办呢？右移一位，左边的最高位补上的是1,到最后变成了0ＸＦＦＦＦＦＦＦＦ，陷入了死循环

第二种：我们可以把移动1,每次比较之后，左移1一位，然后做与运算，就是下面的这样

/*int number_of1_in_binary(int m)
{
    int count = 0, flag = 1;
    while(flag)//每次都把flag往左移动移位，移动32次
    {
        if(m&flag)
            count++;
        flag = flag<<1;
    }
    return count;
}*/

但是这样我们就移动了32次，是不是有点多？，还有没有其它方法？

第三种方法：考察一个数7,二进制111,7-1 = 6的二进制是110, 然后&7 = 110是6, 6-1 = 5的二进制是101,然后&6 = 100是4, 4-1 = 3的二进制是011,然后&4 = 0,我们发现每次把这个数-1然后与上这个数，得到数是原来这个数的最后右边的1变为0的值，由此我们得到如下的解法：

int number_of1_in_binary(int m)
{
    int count = 0;
    while(m)
    {
        ++count;
        m = (m-1)&m;
    }
    return count;
}

3.实现库函数Power(double base, double exponent),不使用库函数，同时不考虑大数问题

如果你大笔一挥，一分种内写下如下的代码：那你就是和我一样的人，别人offer跳板的人

double Power(double base, int exp)
{
    double ret = 1.0;
    while(exp)
    {   
        ret *= base;
        exp--;
    }   
    return ret;
}

1.如果指数是负数怎么办？

2.如果指数是负数而且底数是0怎么办？0的倒数是没有意义的

再加上考虑的这两点，我们完善一下我们的代码

bool flag = true;

bool equal(double m, double n)
{
	if(m-n > -0.000001 && m-n < 0.000001)
		return true;
	else
		return false;
}
double power(double base, double exp)
{
	double ret = 1.0;
	while(exp)
	{
		ret *= base;
		exp--;
	}
	return ret;
}

double Power(double base, int exp)
{
	if(equal(base, 0.0) && exp < 0)
	{
		flag  = false;
		return 0.0;
	}
	unsigned int temp = (unsigned int)exp;
	if(exp < 0)
		temp = 0-exp;
	double ret = power(base, temp);
	if(exp<0) return 1.0/ret;
	return ret;
}

这里还考察了这些细微的编程知识，对于浮点数如何和0比较，对于错误如何返回更好

4. 输入一个数字，打印从1到最大的ｎ位十进制数，比如输入3,打印从1到999的所有数字

如果我们反应快，很快就能想到，可以先求出这个最大的数，然后打印：

void print_to_max_number(int n)
{
    int m = 1;
    while(n)
    {   
        m *= 10; 
        n--;
    }   
    for(int i = 1; i < m; i++)
        cout<<i<<endl;
}

但是这里我们没有考虑大数的问题了，如果ｎ很大怎么办？

大数问题一般都是用数组或者字符串存储每一位，这里我们用字符串

bool Increment(char *num)
{
	bool isOverFlow = false;
	int nTakeOver = 0;
	int len = strlen(num);
	int Num;

	for(int i = len-1; i >= 0; i--)
	{
		Num = num[i]-'0'+nTakeOver;
		if(i == len-1)
			Num++;
		if(Num >= 10)
		{
			if(i == 0)
				isOverFlow = true;
			else
			{
				Num -= 10;
				nTakeOver = 1;
				num[i] = Num + '0';
			}
		}
		else
		{
			num[i] = Num + '0';
			break;
		}
	}
	return isOverFlow;
}

void printnum(char *s)
{
	char *p = s;
	while(*p == '0') p++;
	cout<<p<<endl;
}

void print_to_max_number(int n)
{
	if(n <= 0)
		return;
	char *num = new char[n+1];
	memset(num, '0', n);
	num[n] = '\0';
	 
	while(!Increment(num))//对一个字符串自增，考虑进位
		printnum(num);//打印数字字符串注意的地方
	delete[] num;
}

5.给定单链表的头指针和一个节点指针，定义一个函数在Ｏ（1）复杂度内删除该节点

通常我们的思路就是遍历然后查找，时间复杂度是Ｏ（ｎ），找到这个节点的前一个节点，然后把前一个节点的next指向这个节点的下一个节点

现在我们已经给定了这个节点了，我们换一种思路，把这个节点的下一个节点的值付给这个节点，然后把这个节点的next指针指向下一个节点的下一个节点，等于用下一个节点覆盖这个节点，这个思路就可以在Ｏ（1）时间复杂度内删除这个节点

typedef struct ListNode
{
	int data;
	struct ListNode *next;
}ListNode;

void DeleteNode(ListNode**head, ListNode *node)
{
	if(head == NULL || node == NULL)
		return;

	if(node->next != NULL)
	{
		ListNode *p = node->next;
		node->data = p->data;
		node->next = p->next;

		delete p;
		p = NULL;
	}
	else if(*head == *node)//这个节点是头节点
	{
		delete node;
		node = NULL;
		*head = NULL;
	}
	else//这个节点是最后一个节点
	{
		ListNode *p = *head;
		while(p->next != node)
			p = p->next;
		p->next = NULL;
		delete node;
		node = NULL;
	}
}

需要注意的是如果这个节点是头节点，或者是最后一个节点怎么办

6.输入一个数组，调整该数组的顺序，使得奇数位于数组的前面，偶数位于数组的后面

常规思维，从前往后遍历，找到一个偶数就把这个数后面的所有数往前移动一位，然后把这个数放到最后一个位置，时间复杂度为

Ｏ（ｎ2），太高了解题思路，利用爽指针法，前后各一个指针，然后前指针找到的偶数和后指针找到的奇数交换就可以了，时间复

杂度为Ｏ（ｎ）

void ReorderArray(int a[], int len)
{
    if(a == NULL || len <= 0)
        return ;
    int *p = a, *q = a+len-1;
    int temp;
    while(p < q)
    {   
        while(p < q && (*p & 0x1))
            p++;
        while(p < q && !(*q & 0x1))
            q--;
        if(p < q)
        {   
            temp = *p; 
            *p = *q; 
            *q = temp;
        }   
    }   
}

双指针法的应用常常能得到意外的收获

7.输入一个连表，求该链表的倒数第Ｋ个节点

采用双指针法，一个指向第一个节点，一个指向第Ｋ个节点，然后同时往后移动，两个差距为Ｋ，然后一个到达最后一个节点的时候，另一个就是倒数第Ｋ个节点

SLnode getKnode(SLnode head, int k)
{
    if(head == NULL || head->next == NULL || k == 0)
        return NULL;

    SLnode node1 = head;
    SLnode node2 = head->next;
    while(k >= 1 && node1 != NULL)
    {   
        node1 = node1->next;
        k--;
    }   
    if(node1 == NULL)
        return NULL;
    
    while(node1->next != NULL)
    {   
        node1 = node1->next;
        node2 = node2->next;
    }   
    return node2;
}