《剑指offer》系列-二
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;
}