2.4 算法和数据操作
重点关注二分查找，归并排序和快速排序。
很多算法都有递归和循环两种不同实现方法。通常基于递归的方法会比较简洁，但是性能不如循环算法。
位运算是一种特殊的算法，把数字表示成二进制之后对0和1进行操作。有与、或、异或、左移、右移5种位运算。
2.4.1 查找和排序
查找包括：顺序查找，二分查找，哈希表查找和二叉搜索树查找。哈希查找效率最高，但是需要额外内存来实现。
面试题：二分查找
// 二分查找 int binarySearch(int a[], int search, int begin, int end) { if (begin >= end - 1) { return -1; } int mid = begin + (end - begin) / 2; cout << "mid: " << mid << endl; if (a[mid] == search) { return mid; } else if (a[mid] > search) { return binarySearch(a, search, begin, mid); } else { return binarySearch(a, search, mid, end); } return -1; } int binarySearch(int a[], int n, int search) { return binarySearch(a, search, 0, n); }
排序包括：插入排序，冒泡排序，归并排序，快速排序，堆排序并比较算法优劣，包括是否需要额外内存，最坏时间复杂度和平均时间复杂度。不同算法适用场景不同，应聘者一定要问清面试官这个排序算法应用场景和约束条件，在得到足够信息后再选择合适的算法。
面试题：插入排序，冒泡排序，归并排序，快速排序，堆排序特点比较及代码。包括最坏，平均时间复杂度，是否需要额外内存以及是否为稳定排序
答：插入，冒泡，归并排序是稳定的，即对于两个相同大小的数，排序后保持其原始的相对位置，快速排序和堆排序是不稳定的。插入，冒泡和堆排序不需要额外的空间，快速排序和归并排序需要额外空间。插入排序平均时间复杂度n2，最坏时间复杂度n2。冒泡排序平均时间复杂度n2，最坏时间复杂度n2。快速排序最坏时间复杂度n2，平均时间复杂度nlog2n。堆排序和归并排序平均时间复杂度nlog2n，最坏时间复杂度nlog2n。插入排序思想为前n-1元素已有序，找到当前元素适合插入位置，并进行插入，适合基本有序的序列。
// // Created by Xue,Lin on 2020/6/18. // #ifndef UNTITLED_SORT_ALGORITHM_H #define UNTITLED_SORT_ALGORITHM_H void swap(int &a, int &b) { // cout << "break3" << endl; int tmp = a; a = b; b = tmp; } // 希尔排序是插入排序，堆排序是选择排序，冒泡排序和快速排序是交换排序 // 1.插入排序 稳定，不占用额外空间，平均时间复杂度和最坏时间复杂度均为n2 // 思路为找到每个元素该在的位置，n轮循环后前n个元素有序，比较n+1元素和前n个元素 // 找到n+1元素应在位置，插入，此时前n+1元素有序 // 两轮循环 // 最坏时间复杂度n2，平均时间复杂度n2 // 最好情况为整个数组有序，每个元素仅需要和前一个元素比较，复杂度n // 因此比较是个基本有序的数组 // 注意数组作为参数传递，一定要传递数组长度，在函数内无法判断长度 void insertSort(int a[10], int n) { for(int i = 1; i < n; i++) { if (a[i] > a[i - 1]) { continue; } for(int j = i - 1; j >= 0; j--) { if (a[j+1] < a[j]) { swap(a[j+1], a[j]); } else { break; } } } } // 2.冒泡排序 // 注意是相邻元素比较，如果想把最大的先捞出来，第二重循环就从前往后遍历 // 如果是想把最小的先捞出来，第二重循环就从后往前遍历 void bubbleSort(int a[], int n) { for(int i = 0; i < n; i++) { for(int j = n; j >= i; j--) { if (a[j-1] > a[j]) { swap(a[j-1], a[j]); } } } } // 3.快速排序，冒泡排序的升级，属于交换排序类 // 快速排序基本思想为通过一趟排序将待排序的记录分割成两个独立的部分 // 其中一部分记录的关键字均比另外一部分要小，然后对这两部分进行分别排序 // 最终实现整个数组有序 // partition是快排的精髓部分，交换原始表a中数据位置，使小于枢纽值在左，大于枢纽值在右，最终返回枢纽所在位置 int partition(int a[], int low, int high) { // 枢纽值设定为带排序数组第一个元素 // 由于枢纽值的选取会影响快排效率，有改进法为3数选取，即在待排序数组中任选3个数，取中间数为枢纽 int pivot_value = a[low]; // 交换方式为low和high两个指针移动， // 先移动high，high--，当high小于pivot，交换，然后开始low++，当low大于pivot，交换 // 再移动high，重复上面过程，知道low和high相遇，代表此时partition结束 while(low < high) { // cout << "low:" << low << " " << "high:" << high << endl; // 注意high要是有效的 while(low < high && a[high] >= pivot_value) { high--; } swap(a[high], a[low]); // 注意这里要判断low < high 并且 a[low] 小于等于而不是小于，不然遇到相等的会一直出不去 while(low < high && a[low] <= pivot_value) { low++; } swap(a[low], a[high]); } return low; } void quickSort(int a[], int low, int high) { if (low >= high) { return; } int pivot; pivot = partition(a, low, high); quickSort(a, low, pivot - 1); quickSort(a, pivot + 1, high); } void quickSort(int a[], int n) { quickSort(a, 0, n - 1); } // 4.归并排序 // 归并排序的原理是假设原始序列包含n个记录，可以看成是n个有序的子序列，每个子序列的长度为1 // 然后两两归并，得到【n/2】个长度为2的子序列，再两两归并，直到整个序列有序 void merge(int a[], int begin, int mid, int end) { cout << "begin: " << begin << "end: " << end << endl; int *arr = new int(end-begin); // 将a中begin到end按照从小到大归并到arr，其中【begin，mid），【mid，end）是两个有序子序列 int l1 = begin, l2 = mid; int index = 0; while(l1 < mid && l2 < end) { if (a[l1] < a[l2]) { arr[index] = a[l1]; l1++; } else{ arr[index] = a[l2]; l2++; } index++; } while(l1 < mid) { arr[index++] = a[l1++]; } while(l2 < end) { arr[index++] = a[l2++]; } for(int i = begin; i < end; i++) { a[i] = arr[i-begin]; } return; } void msort(int a[], int begin, int end) { if (begin >= end - 1) { return; } int mid = begin + (end - begin) / 2; cout << "begin: " << begin << "end: " << end << "mid:" << mid << endl; msort(a, begin, mid); msort(a, mid, end); merge(a, begin, mid, end); return; } void mergeSort(int a[], int n) { msort(a, 0, n); } // 5.堆排序 // 堆是具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子的节点值，称为大顶堆 // 每个节点值都小于或等于其左右孩子的节点值，称为小顶堆 // 堆排序就是利用堆进行排序的方法。将待排序数组构造成一个大顶堆，此时，这个序列的最大值就是堆顶 // 将他移走（就是把堆顶和堆数组末尾元素交换，此时末尾元素就是最大值） // 然后将剩余n-1个序列重新构造一个堆，这样就会得到n个元素中次大值 // 反复重复，可以得到一个有序序列 // 所以核心是实现两个函数 1.根据当前序列构建一个堆 2.在输出堆顶元素后，如何调整剩余元素成为一个新堆 // 参考链接：https://www.cnblogs.com/wanglei5205/p/8733524.html void headAdjust(int a[], int begin, int end) { // 核心函数，建立堆 // begin为第一个非叶子节点的下标 // cout << "begin:" << begin << "end:" << end << endl; int temp, j; temp = a[begin]; for(j = 2*begin; j < end - 1; j=j*2) { // 找到一个比较大的元素和当前元素进行交换 if (j < end - 1 && a[j] < a[j+1]) { j++; } if (temp >= a[j]) { break; } a[begin] = a[j]; begin = j; } a[begin] = temp; // cout << "begin:" << begin << "end:" << end << endl; return; } void headSort(int a[], int n) { int i; // 两个循环 // 第一个循环根据序列建立一个堆 for(i = n / 2; i >= 0; i--) { // cout << "break 1" << endl; // 从第一个非叶子节点开始，当前非叶子节点大顶堆，一步步往上推 headAdjust(a, i, n); } /* 可以把树结构打出来，验证问题，打出来就是按每层从左到右 for(int i = 0; i < n; i++) { cout << a[i] << " "; } */ // 第二个循环为移除顶点，然后重新建立堆 for(i = n; i >= 1; i--) { // cout << "break2" << endl; swap(a[0], a[i-1]); // 这个时候因为交换了顶点，因此顶点不满足大顶堆，但是其余根节点还是满足的 // 因此这里begin参数传0就可以 headAdjust(a, 0, i-1); /* for(int i = 0; i < n; i++) { cout << a[i] << " "; } */ } return; } // 6.希尔排序 // 希尔排序是插入排序的升级，看好的是插入排序相对基本有序数组排序较为高效的特点 // 希尔排序的思想是，每次循环完成对间隔为increment数组的排序，直到increment为1，即为完成全数组排序 void shellSort(int a[], int n) { int increment = n; do{ increment = increment / 3 + 1; cout << increment << endl; for(int i = increment; i < n; i++) { // cout << "i:" << i << endl; int tmp = a[i]; if (a[i - increment] > tmp) { // 寻找当前tmp插入的最合适的位置，应该插入到比他小的元素的前面，后面的元素都后移 int j = i - increment; for( ; j >= 0 && tmp < a[j]; j-=increment) { // cout << "j:" << j << endl; // 后移 a[j+increment] = a[j]; } // tmp插入合适位置 a[j+increment] = tmp; } // 完成一次按间隔increment抽出来的数组的插入排序 } } while(increment > 1); } #endif //UNTITLED_SORT_ALGORITHM_H int a[10] = {1,4, 2, 7, 2, 3, 8, 9, 4}; // insertSort(a, 10); // bubbleSort(a, 10); // quickSort(a, 10); // shellSort(a, 10); // headSort(a, 10); mergeSort(a, 10); for(int i = 0; i < 10; i++) { cout << a[i] << " "; }
堆排序没写出来，注意有时间需要重写一下!!!
面试题8：旋转数组中的最小数字
把一个数组最开始的若干元素搬到数组末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
对应leetcode链接为https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/class Solution { public: int force_find(vector<int>& nums, int begin, int end) { int result = nums[begin]; for(int i = begin + 1; i <= end; i++) { if (nums[i] < result) { result = nums[i]; } } return result; } int findMin(vector<int>& nums) { // 用二分法找到翻转点 if (nums.size() == 0) { return 0; } int index1 = 0; int index2 = nums.size() - 1; int mid = index1; while(nums[index1] >= nums[index2]) { if (index2 - index1 == 1) { mid = index2; break; } mid= index1 + (index2 - index1) / 2; if (nums[index1] == nums[index2] && nums[index1] == nums[mid]) { // 全相等无法判断mid所属区间，只能暴力查找 return force_find(nums, index1, index2); } if (nums[mid] >= nums[index1]) { index1 = mid; } else if(nums[mid] <= nums[index2]) { index2 = mid; } } return nums[mid]; } };
思路：二分查找扩展。注意前后元素相等的特殊情况。
旋转后，队列可分为两部分，前递增序列和后递增序列。二分查找即为找两个序列的分界点。设置index1为前递增序列尾指针，初始化为0。index2位后递增序列首指针，初始化为size()-1。mid为中间节点(index1+index2)/2。当判断mid>=index1,即认为mid在前递增序列中，前递增序列的尾节点应该是mid或mid后面的元素，因此用mid替代index1。当判断mid小于等于index2，认为mid在后递增序列中，则分解点应在index1-mid中，用mid代替index2。直到index2-index1=1，代表index2即为交界点。注意可能存在不旋转情况，这种情况满足不了index1>=index2，将mid赋值为index1，直接获取首元素，退出。
class Solution {
public:
int findMin(vector<int>& nums) {
// 用二分法找到翻转点
if (nums.size() == 0)
{
return 0;
}
int index1 = 0;
int index2 = nums.size() - 1;
int mid = index1;
while(nums[index1] >= nums[index2])
{
if (index2 - index1 == 1)
{
mid = index2;
break;
}
mid= index1 + (index2 - index1) / 2;
if (nums[mid] >= nums[index1])
{
index1 = mid;
}
else if(nums[mid] <= nums[index2])
{
index2 = mid;
}
}
return nums[mid];
}
};
存在问题，当index1=mid=index2时，上面判断方法会出现误判，考虑下面两个序列
1，0，1，1，1
1，1，1，0，1
第一次判断mid=1，index1=1，index2=1（均指对应value），无法判断旋转点在前面还是在后面，这个时候，只能用暴力循环来找。因此代码需要进一步升级
class Solution {
public:
int force_find(vector<int>& nums, int begin, int end)
{
int result = nums[begin];
for(int i = begin + 1; i <= end; i++)
{
if (nums[i] < result)
{
result = nums[i];
}
}
return result;
}
int findMin(vector<int>& nums) {
// 用二分法找到翻转点
if (nums.size() == 0)
{
return 0;
}
int index1 = 0;
int index2 = nums.size() - 1;
int mid = index1;
while(nums[index1] >= nums[index2])
{
if (index2 - index1 == 1)
{
mid = index2;
break;
}
mid= index1 + (index2 - index1) / 2;
if (nums[index1] == nums[index2] && nums[index1] == nums[mid])
{ // 全相等情况采用暴力查找
return force_find(nums, index1, index2);
}
if (nums[mid] >= nums[index1])
{
index1 = mid;
}
else if(nums[mid] <= nums[index2])
{
index2 = mid;
}
}
return nums[mid];
}
};
【c++拾遗】数组作为函数的参数或返回值
参考链接：https://blog.csdn.net/jpzhu16/article/details/79950684c++数组作为传参，只是传递首地址，无法在函数内部获得数组正确长度，因此需要传递数组长度参数。由于是指针传递，数组在传递函数中的改动将直接影响数组本身。
数组作为返回值，在函数中定义需要是new定义的空间，且无法在函数外获取长度，需要已知长度。不能直接定义局部变量，出函数会被释放，无法作为返回值。也可定义为static 变量。
2.4.2 循环和递归
如果我们需要重复多次计算相同问题，可以选用递归或者循环。
递归优点：代码简洁
缺点：1）由于函数调用需要栈分配内存保存参数，返回地址和临时变量，而且往栈中压入数据和弹出数据需要时间，递归性能一般较差 2）递归中很可能一部分计算是重复的 3）容易造成调用栈溢出
面试题9：斐波那契数列
题目一：写一个函数，输入n，求斐波那契数列的第n项。斐波那契数列定义如下
leetcode 链接 https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/class Solution { public: int fib(int n) { if (n ==0) { return 0; } if (n == 1) { return 1; } if (n == 2) { return 1; } int result[n+1]; result[0] = 0; result[1] = 1; result[2] = 1; for(int i = 3; i <= n; i++) { result[i] = (result[i-1] + result[i-2])%1000000007; } return result[n]; } };
经典递归解法：
class Solution {
public:
int fib(int n) {
if (n <= 0)
{
return 0;
}
if (n == 1)
{
return 1;
}
if (n == 2)
{
return 1;
}
return fib(n-1) + fib(n-2);
}
};
经典递归解法问题：
分析其递归过程
可以明显看出其中有很多重复运算的部分。改进方法为将已经计算过的数据保存起来，如果前面已经计算过了，就不再重复计算。
class Solution {
public:
map<int, int> result;
int fib(int n) {
if (n <= 0)
{
return 0;
}
if (n == 1)
{
return 1;
}
if (n == 2)
{
return 1;
}
// return fib(n-1) + fib(n-2);
int ret = 0;
if (result.find(n) != result.end())
{
ret = result[n];
}
else
{
ret = (fib(n-1) + fib(n-2)) % 1000000007;
result[n] = ret;
// cout << "n:" << n << " " << ret <<endl;
}
return ret;
}
};
更好的思路是自底向上计算，先根据f(0)和f(1)计算f(2),然后计算f(3),f(4)依次递推
class Solution {
public:
int fib(int n) {
if (n ==0)
{
return 0;
}
if (n == 1)
{
return 1;
}
if (n == 2)
{
return 1;
}
int result[n+1];
result[0] = 0;
result[1] = 1;
result[2] = 1;
for(int i = 3; i <= n; i++)
{
result[i] = (result[i-1] + result[i-2])%1000000007;
}
return result[n];
}
};
题目二：一只青蛙一次可以跳一个台阶，也可以跳两级。求该青蛙跳到n级台阶总共有多少种方法。 leetcode链接 https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
class Solution { public: int numWays(int n) { if (n <= 0) { return 1; } if (n == 1) { return 1; } if (n == 2) { return 2; } int result[n+1]; result[0] = 1; result[1] = 1; result[2] = 2; for(int i = 3; i <= n; i++) { result[i] = (result[i-1] + result[i-2]) % 1000000007; } return result[n] ; } };
和斐波那契数列完全一样
题目二扩展：如果一个青蛙一次可以跳1，2，3...n阶台阶，跳到n阶台阶一共有多少种方法
class Solution { public: int numWays(int n) { if (n <= 0) { return 1; } if (n == 1) { return 1; } if (n == 2) { return 2; } int result[n+1]; result[0] = 1; result[1] = 1; result[2] = 2; for(int i = 3; i <= n; i++) { result[i] = 0; for(int j = 1; j <= i; j++) { result[i] += result[i-j]; } result[i] = result[i] % 1000000007; cout << "i:" << i << "result: " << result[i] << endl; } return result[n] ; } };
相关题目：我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。问用8个2x1的小矩形无重叠的覆盖一个2x8的大矩形，总共有多少种方法。
牛客网链接：https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&&tqId=11163&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-rankingclass Solution { public: int rectCover(int number) { int result[number + 1]; if (number == 0) { return 0; } if (number == 1) { return 1; } if (number == 2) { return 2; } result[0] = 1; result[1] = 1; result[2] = 2; for(int i = 3; i <= number; i++) { result[i] = result[i-1] + result[i-2]; } return result[number]; } };
思路：用第一个1*2的小矩形去覆盖大矩形的最左面，有两个选择1）竖着放，则剩余可选择方法f(n-1) 2）横着放，这样必须并列再放一个，剩余可选择f(n-2)因此还是一个斐波那契数列
2.4.3 位运算
位运算指将数字用二进制表示之后，对每一位的0或1进行运算。
左移n位，最左面n位舍弃，最右面补0。右移n位，如果是正数，右面补0。如果是负数，右面补1。
面试题：在excel2003中，用A表示第一列，B表示第二列....Z表示第26列，AA表示第27列....以此类推。请写出一个函数，输入为用字母表示的列号编码，输出为第几列。另一个函数，输入为列数，输出为字母表示的列号编码。
leetcode链接 https://leetcode-cn.com/problems/excel-sheet-column-number/
https://leetcode-cn.com/problems/excel-sheet-column-title/// 编码转列号 class Solution { public: int titleToNumber(string s) { int result = 0; int n = 0; for(int i = s.length() - 1; i >= 0; i--) { char tmp = s[i]; // cout << tmp << endl; int value = tmp - 'A' + 1; result = result + value * pow(26, n); n++; } return result; } }; // 列号转编码 class Solution { public: string convertToTitle(int n) { string s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; string result = ""; string s1 = ""; while(n != 0) { int tmp = (n-1) % 26; char c_tmp = 'A' + tmp; s1 = s1 + c_tmp; n = (n-1) / 26; } cout << s1 << endl; for(int i = s1.length() - 1; i >= 0; i--) { result = result + s1[i]; } return result; } };
思路：这个题的本质是把10进制的数字用A-Z表示为26进制。
面试题10：二进制中1的个数
请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。 leetcode 链接 https://leetcode-cn.com/problemset/all/?search=%E4%BA%8C%E8%BF%9B%E5%88%B6%E4%B8%AD1%E7%9A%84%E4%B8%AA%E6%95%B0 leetcode不考虑负数，可以看牛客链接 https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8?tpId=13&&tqId=11164&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
class Solution { public: int hammingWeight(uint32_t n) { // 由于一个数和它-1做与，会将最右面的1置为0，其余不变 // 对于正数 int result = 0; while(n != 0){ n = n & (n - 1); result++; } return result; } };
解题思路：将一个整数减1之后再和原来的整数做位与运算，得到的结果相当于是把整数的二进制表示中最右边的一个1变成0。很多二进制问题都可以用这个思路解决。
注意：用位移代替除法，位移的效率比除法高很多。注意负数移动。
相关题目：用一条语句判断一个整数是不是2的整数次方
return n & (n -1) == 0;
解题思路：如果一个整数是2的整数次方，那么他的二进制中有且只有一位为1，其余位都是0。把这个整数减1之后再与他本身做与运算，这个整数中唯一的1会变成0。
输入两个整数m和n，计算需要改变m的二进制中多少位才能得到n。
int a = 0, b = 6; int c = a ^ b; int n = 0; while(c != 0) { c = c & (c-1); n++; } cout << n << endl; // sort
解题思路：两个数做异或，求最终结果中有多少个1
