剑指offer第三天

呃 其实是昨天追太阳的后裔和银魂搞得第二天的内容没写完。
最近好虐 国足出线 银魂本季完结 心塞...
不过每天洗完澡照照镜子 又会发觉世界是多么美好

1.png

言归正传

2.4 算法和数据操作

重点掌握 二分查找 归并排序 快速排序
tips 如果题目要求在排序的数组(或部分排序的数组）中查找一个数字或统计某个数字出现的次数，我们都可以尝试二分查找算法。

哈希表最主要的优点是能够在O(1)时间查找某一元素。

快速排序 主要思想 在数组中选择一个数字，把数组中小于该数字的移到数组左边，大的移到右边。
快排代码

void qucikSort(int left,int right,int a[]){
int i,j,t,temp;
if (left>right) {
    return;
}
temp=a[left];
i=left;
j=right;
while (i!=j) {
    while (a[j]>=temp && i<j) {
        j--;
    }
    while (a[i]<=temp && i<j) {
        i++;
    }
    if (i<j) {
        t=a[j];
        a[j]=a[i];
        a[i]=t;
    }
}
a[left]=a[i];
a[i]=temp;
qucikSort(left, i-1,a);
qucikSort(i+1, right,a);
}

如果需要排序的数字在一个较小的范围内，可以考虑桶排。

2.4.2 递归和循环

如果我们需要重复计算相同的问题，可以选择递归或者循环两种不同的方法。

斐波那契数列 又想起组合数学了 让我哭一会

代码

int Fib(int x){
if (x<=0) {
    return 0;
}
if (x==1 || x==2) {
    return 1;
}
return Fib(x-1)+Fib(x-2);
}

非递归

//真为自己的单词量感到捉急
int FibNotDigui(int x){
  if(x==0) return 0;
  if(x==1) return 0;
  int FibOne=1;
  int FibTwo=0;
  int Fib=0;
  //f(n)＝f(n-1)+f(n-2) FibOne:f(n-1)   FibTwo:f(n-2)
  for (int i=2; i<=x; i++) {
    Fib=FibOne+FibTwo;
    FibTwo=FibOne;
    FibOne=Fib;
    }
return Fib;
}

相关变形 一只蛤一次可以跳上一级，也可以跳上两级，求跳n级台阶共有多少种跳法。
n级台阶只有从n－1级和n－2级跳上两种方法，设f(n)为n级台阶的跳法
f(n)＝f(n-1)+f(n-2)
识得唔识得 还是一个斐波那契问题 ！

位运算

输入一个整数，输出该数二进制中1的个数，如9 1001 输出2
思路 把n和1做运算 得出最低位是否为1 再把1左移一位 和n做与运算 得出次地位是否为1 依此类推
代码如下

void numberofOne(int x){
int count=0;
 unsigned int test=1;
  if (x==1) {
    printf("%d",1);
    return;
  }
while (test<x) {
    if (x & test) {
        count++;
    }
   test= test << 1;
    }
printf("%d",count);
}

先写那么多 今天看的还得整理下
ps:希望保安别那么早赶人 让我把剧看完
pps:今天绝对不能吃宵夜了！