算法与数据结构面试题-3

常见面试题

1. 说说什么是稳定的排序？⭐⭐⭐⭐⭐

   • 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
   • 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

   冒泡排序、归并排序是稳定排序；快速排序是不稳定排序。

2. 说说动态规划算法⭐⭐⭐⭐⭐

   暴力解法有很多重复计算，动态规划就是为了帮助我们减少重复计算，所以动态规划提前存储前面计算的值，后面的值来源于已经存储的值，或者只需要在已经存储的值的基础上简单的叠加，这就是动态规划的本质，空间换时间。
   三个非常重要的领悟：
   1、动态规划应用于存在重复子结构的问题中，避免重复计算法
   2、动态规划空间换时间
   3、动态规划提前存储前面计算的值，后面的值来源于已经存储的值，或者只需要在已经存储的值的基础上简单的叠加

3. 手撕归并排序，说说原理⭐⭐⭐⭐⭐

   归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

   class Solution {
       void mergeSort(vector<int>& nums, vector<int>& temp, int l, int r){
           if (l >= r) return;
           int mid = (l + r) / 2;
           mergeSort(nums, temp, l, mid);
           mergeSort(nums, temp, mid+1, r);
           int i=l,j=mid+1; int t = 0;
           while (i<=mid && j<=r){
               if (nums[i] <= nums[j]) temp[t++] = nums[i++];
               else temp[t++] = nums[j++];
           }
           while (i <= mid) temp[t++] = nums[i++];
           while (j <= r) temp[t++] = nums[j++];
   
           for (int i=l,t=0; i<=r; i++)
               nums[i] = temp[t++];
       }
   public:
       vector<int> sortArray(vector<int>& nums) {
           if (nums.empty()) return {};
           vector<int> temp(nums.size(), 0);
           mergeSort(nums, temp, 0, nums.size()-1);
           return nums;
       }
   };
   // 时间复杂度：O(nlogn)
   // 空间复杂度：O(n)

4. 手撕快速排序，说说原理⭐⭐⭐⭐⭐

   快速排序的基本思想：也是采用分治的思想，将数组拆分成一个个的子序列，针对每个子序列进行排序，排序的方法是，设立一个“基准元素”，比“基准元素”小的数字放左边，比“基准元素”大的数字放右边。

   //快排递归实现
   class Solution {
       void quickSort(vector<int>& nums, int l, int r){
           if (l >= r) return;
           int mark = nums[l];
           int mark_ptr = l;
           for (int i=l; i<=r; i++){
               if (nums[i] < mark){
                   mark_ptr++;
                   swap(nums[i], nums[mark_ptr]);
               }
           }
           swap(nums[mark_ptr], nums[l]);
           quickSort(nums, l, mark_ptr-1);
           quickSort(nums, mark_ptr+1, r);
       }
   public:
       vector<int> sortArray(vector<int>& nums) {
           if (nums.empty()) return {};
           quickSort(nums, 0, nums.size()-1);
           return nums;
       }
   };
   // 时间复杂度：O(nlogn)
   // 空间复杂度：O(logn)
   
   //快排非递归实现，利用栈，BFS的思想，存储前后指针
   class Solution {
       void quickSort(vector<int>& nums, int l, int r){
           using Pair = pair<int,int>;
           stack<Pair> stk; stk.pu