剑指Offer基础知识(二)算法

2018-03-02

本文主要记录阅读剑指Offer这本书所遇到的算法解释并作一些个人的拓展，其中的算法面试题请看剑指Offer面试题集

第二章

2.4 算法和数据操作

排序和查找是面试时考查算法的重点，如二分查找、归并排序、快速排序等。
递归和循环是两种算法实现的方式，基于递归的实现较整洁但性能不如基于循环实现的方法，我们应该根据题目特点来选择使用哪种实现方式。
位运算可以看做一类特殊的算法，共有与、或、异或、左移和右移五种位运算

2.4.1 查找和排序

查找不外乎：顺序查找、二分查找、哈希表查找和二叉排序树查找，无论用递归还是循环都需要掌握这些查找方法的实现。
排序则复杂一些：插入排序、冒泡排序、归并排序、快速排序等不同算法的优劣，能够从额外空间消耗、平均时间复杂度和最差时间复杂度等方面去比较它们的优缺点。
值得一提的是，快速排序的实现代码是面试官钟爱的。
快速排序思路:选择一个数字(有多种选择法)，接下来把数组中的数字分成两部分，比选择的数字小的数字移到数组的左边，比选择数字大的数字移到数组右边
接下来看一个年龄排序问题
若对员工年龄排序，数字大小在一个较小范围内，可以使用辅助内存
思路：由于员工年龄有一个范围，则可以使用有限数组作为辅助空间换取排序效率，用timesOfAge数组统计每个年龄出现次数，用ages数组设置年龄排序

void sortAges(int age[],int length)
{
  //1.有效性检测
  if(age==NULL || length<=0) return;

  //2.设置timesOfAge数组，下标为年龄，值为在该年龄的人数
  int oldestAge = 99;
  int timesOfAge[oldestAge+1];
  for(int i=0;i<=oldestAge;i++) timesOfAge[i] =0; //初始化
  for(int i=0;i<length;i++)
  {
    int age = age[i];
    if(age<0 || age >99) throw new std:exception("age out of range.");
    else timesOfAge[age]++;
  }

  //3.重新设置age数组，将年龄重排
  int ageIndex = 0;
  for(int i=0;i<=oldestAge;i++)  //i为年龄
  {
    for(int j=0;j<timesOfAge[i];j++)  //j为i年龄的人数
    {
      age[ageIndex]=i;
      ageIndex++;
    }
  }

}

2.4.2 递归和循环

多次重复计算，可以使用递归和循环。
递归：在函数内部调用函数自身直到递归停止return
循环：设置计算初始值和终止条件
如计算1+2+3….n，我们可以使用递归或者循环求出结果

//递归
int Add(int n)
{
  if(n>=0) return n+Add(n-1);
  else return 0;
}
//循环
int add(int n)
{ 
  int sum=0;
  for(int i=0;i<=n;i++)
  {
    sum += i;
  }
  return sum;
}

递归与循环的选择：

1.递归简洁，若面试官无特殊要求，可以优先采用递归
2.循环高效，递归是函数调用，需要时间和空间的消耗，需要在内存栈分配空间保存参数，另外递归可能存在重复计算
3.递归有严重问题：调用栈溢出，栈容量是有限的，不可能无限调用，溢出则会出错

2.4.3 位运算

位运算是将数字用二进制表示之后对每一位上的0/1进行运算
二进制就是指数字的每一位都是0/1，其他进制如表示时间分秒的六十进制，针对进制，有许多面试题，如
在Excel 2003中，A表示1列，B表示2列…Z表示26列，AA表示27列，AB表示28列，请写出一个函数，输入字母，输出第几列
思路：这题本质上是10进制转26机制用A-Z表示，输入字母，如ABC，首先分解成A/B/C，A-1，B-2，C-3，则数字为26^2 *1 + 26^1 *2 + 26^0 *3 = 676 * 1+26 * 2+1 * 3=731

Fright For Better Day

ItEassy