算法集训营第二期｜Week2--经典算法思想：二分，贪心，分治，及问题答疑总结
cyoushika
3311
2021.12.12
2021.12.14
发布于 未知归属地
求职面试算法集训营第二期

1. 周赛总结：本周周赛一共6题，AC5题，最后一题虽然有思路，但是已经超时，没有时间写了，十分遗憾，状态较上周略有下滑，一共罚时9次，除了一些匪夷所思的WA之外，至少有6次罚时是因为自己没看清题目要求或者笔误导致的，实在是不应该...总分90/100，排名第五，希望下周状态能够回归，争取AK！（答疑部分在帖子的最后）

2nd Week Contest

2. 学习内容：本周涉及一些经典算法思想 —— 二分，贪心，分治

A. 二分 ( 时间复杂度=O(logN), 空间复杂度=O(1) )：

什么是二分？二分是对有序集合中搜索特定值的过程，因此使用二分之前，必须保证查找空间内的数据单调有序。二分包含三个部分：预处理，二分查找，后处理。

  1. 预处理：如果集合未排序，则进行排序；
  2. 二分查找：包含左边界，右边界，标杆三个元素，每次取左右边界的中间值，与标杆比较，对左右边界进行调整，并重新计算中间值，直至寻找成功/失败，结束循环；
  3. 后处理：在剩余的空间中确定的可行的候选者；

模板1--最基础的二分，用于精确寻找某个值在查找空间的位置，不需要考虑左右边界的留存，每个位置只有yes和no两种结果，搜索过程中就可以判断是否找到了元素，因此也不需要后处理。

int binarySearch(vector<int>& nums, int target){
  if(nums.size() == 0)
    return -1;

  int left = 0, right = nums.size() - 1;
  while(left <= right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ return mid; }
    else if(nums[mid] < target) { left = mid + 1; }
    else { right = mid - 1; }
  }

  // End Condition: left > right
  return -1;
}

推荐题目：LeetCode 69. Sqrt(x)

模板2--高级二分，在查找的过程中，对右边界进行留存，查找空间在每一步至少有2个元素，当只剩下一个元素时结束循环。循环结束后，检查右边界指向的元素是否满足条件。

int binarySearch(vector<int>& nums, int target){
  if(nums.size() == 0)
    return -1;

  int left = 0, right = nums.size();
  while(left < right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ return mid; }
    else if(nums[mid] < target) { left = mid + 1; }
    else { right = mid; }
  }

  // Post-processing:
  // End Condition: left == right
  if(left != nums.size() && nums[left] == target) return left;
  return -1;
}

推荐题目：LeetCode 162. 寻找峰值

模板3--特殊二分，在查找过程中，对左右边界都进行留存，查找空间在每一步至少有3个元素，当只剩下两个元素时结束循环。循环结束后，分别检查左右边界指向的元素是否满足条件。

int binarySearch(vector<int>& nums, int target){
    if (nums.size() == 0)
        return -1;

    int left = 0, right = nums.size() - 1;
    while (left + 1 < right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}

推荐题目：LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

B. 贪心：贪心算法是一种做事的思路，是在众多选择中选择当前看起来最好的选择，而不去考虑其他可能的，由每一次“当前最优”的选择一步步走向“全局最优”。

  1. 与动态规划，回溯算法的区别：

    • 回溯算法：记录每一个步骤，每一个选择
    • 动态规划：记录每一个步骤，所有选择的汇总值（最大，最小，或者计数）
    • 贪心算法：每个步骤只有一种选择，也只记录与当前选择相关的信息

  2. 什么时候可以贪心？：
    个人经验...没有放之四海而皆准的标准，因为每个题的背景不同，贪心策略也会不同，而大部分时候，我们是没有时间或者能力去证明贪心算法的正确性的...只能靠刷题积累经验，多看，多做，才能做到一看题目就知道能否用贪心算法。

  3. 推荐题目：

C. 分治：分治算法是将一个大问题分成规模更小的问题，分别解决，最后合并处理。使用分治算法，要求子问题之间相互独立。

经典应用：

  1. 经典应用就是归并排序，将长度为n的数组分成两个n/2的数组，进而对每个n/2数组进行二分，直至只有1个元素时，开始返回合并。合并过程中，设置一个临时数组，比较两个数组的元素，将较小的元素放入临时数组，直至两个数组的元素都放入临时数组后，将临时数组的元素拷贝到原数组当中。

  2. 逆序对数：因为归并排序的特性，我们可以在合并过程中，求逆序数。推荐题目：

  3. 快速排序：快速排序是选定一个标杆x，将数组分为小于x，等于x，大于x三部分，然后对于小于和大于x的部分重复选标杆和分类，逐渐达到全体有序的过程，这个过程有个响当当的名字，叫做“荷兰国旗问题”，有兴趣的朋友可以去搜索一下，在这不做展开。如今，很多语言已经将快速排序作为库函数实现了，所以我们平时刷题很少会遇到手敲排序算法的情况，但是面试当中是有可能遇到手写排序的，因此有必要保证自己会几种经典排序算法的实现（如快速排序，堆排序，归并排序，插入排序，这几种排序方法在工业至今仍有应用）。

D. 第二周 问题答疑汇总

1. 经典快排的时间复杂度退化问题：

经典快速排序通常都是指定一个固定的位置作为标杆的选择位，比如区间的头部，尾部，或中间。这就带来了一个问题，就是对于某一种特定排列的数组，固定位置选择标杆可能会导致快速排序的速度退化成O(N^2)。举个例子，一个已经是升序排序的数组【1，2，3，4，5，6】（但是我们不知道它已经有序），用经典快速排序，选择第一个元素作为标杆x的话，那么左指针会指向2，大于x，不动；右指针一直左移，直到left的位置，走过了n-1个位置，发现都分好了，1的左边是比它小的数组（啥也没有），右边是比1大的数组，2~6.然后继续对【2，3，4，5，6】进行上面的操作，选择2为标杆...我们会发现，总操作和为n-1+n-2+...+1的等差数列，求和得到n^2/2，因此时间复杂度是O(N^2)的。为了避免这个问题，我们可以采用随机标杆选定来减少这种极端情况的出现。

2. 快慢指针求环入口问题：

(1) 是否存在环：在寻找环入口之前，我们需要先判断是否存在环。判断的方式有很多，经典的方法就是快慢指针。所谓快慢指针，就是用两个指针，一个每次只移动一步，一个每次移动两步，移动块的指针我们称之为快指针，类似“斥候”，用于探路。如果快指针到达了空节点，那么说明不存在环，如果快慢指针相遇，则必定存在环。

(2) 环入口：先说结论，当快慢指针相遇后，我们将快指针重置回head头节点（或者重新设立一个位于head的指针），与慢指针同速率移动，二者相遇的地方就是环入口。
证明：将链表分段，从开头到环入口的距离为L，快慢指针在第t次移动后相遇的位置为X（从环入口开始数），从X位置继续前进，到达环入口的距离记为Y，则有下面的关系：

  • 快指针走过的距离为2*t = L+n*(X+Y)+X, n为双指针相遇前快指针在环内循环的圈数。（式子1）
  • 慢指针走过的距离为t = L+X（式子2）
  • 联立式子1和式子2，得到：0 = -L+n*(X+Y)-X => L = n*(X+Y)-X，且n必定是大于等于1的（快指针必然绕过1圈才能到达慢指针的后面，才有机会与慢指针相遇）
  • 右边的式子，如果我们再减去一个Y，就会变成(n-1)*(X+Y),正好是完整的环长度，走过Y个距离，应该正好回到环入口，我们设环入口的位置为0，则有L-Y=0，得出L=Y，这意味着，快慢指针相遇的位置出发到达环入口的距离，就是从头节点出发到达环入口的距离。 因此，如果我们设一个指针从头节点走，而另一个指针从位置X开始走，二者走过L个距离，应该正好到达环入口。

(3) 为什么快指针要移动2格，移动3格，4格不行吗？
当然可以更快，但是快指针不是越快越好。如果它移动的速度超过了环的长度Q，那么它每次都会走超过环长度的步数（假设为n），那走n步与走n%Q步是等价的，因为它绕了好几圈，回到了环入口，最终也只比它之前的位置多走了n%Q步。如果n%Q==1，那快指针实际上和慢指针的速度是一样的，一旦错过，就永远不会相遇了。之所以设置成2，是因为单向链表的环的长度最少为3，两个节点是无法形成环的。

评论 (5)