更新面试可能遇到以及遇到的算法题

排序

排序算法时间复杂度

快速排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr; 
      }
      quick_sort(arr, 0, arr.size()-1); 
      return arr;
    }
  
  private:
    void quick_sort(std::vector<int> &arr, int low, int high) {
      if (left >= right) {
        return ;
      }
      
      std::swap(arr[left], arr[(left + right) / 2]);
      int key = arr[left];
      int l = left, r = right;
      
      while (l < r) {
        while (l < r && arr[l] <= key) ++l;
        while (l < r && arr[r] >= key) --r;
        std::swap(arr[l], arr[r]);
      }
      
      if (arr[l] > key) {
        --l;
      }
      
      std::swap(arr[l], arr[left]);
      
      quick_sort(arr, left, l - 1);
      quick_sort(arr, l + 1, right);
    }
};

归并排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr; 
      }
      merge_sort(arr, 0 , arr.size()-1);
      return arr;
    }
  
  private:  
    void merge_elem(std::vector<int> &arr, int low, int mid, int high) {
      std::vector<int> temp;
      int i = low, j = mid + 1;
      
      // 排序插入
      while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {
          temp.push_back(arr[i++]);
        } else {
          temp.push_back(arr[j++]);
        }
      }
      
      // 遍历剩下部分
      while (i <= mid) {
        temp.push_back(arr[i++]);
      }
      while (j <= high) {
        temp.push_back(arr[j++]);
      }
     
      // 拷贝回原数组
      for (int i = low, j = 0; i <= high; i++) {
        arr[i] = temp[j++];
      }
    }
    
    void merge_sort(std::vector<int> &arr, int low, int high) {
      if (low < high) {    // 分割到两个元素
        int mid = (low+high) / 2;
        merge_sort(arr, low, mid);
        merge_sort(arr, mid+1, high);
        merge_elem(arr, low, mid, high);   // 递归到两个元素后合并回退
      }
    }
};

堆排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr; 
      }
      heap_sort(arr, 0, arr.size()-1);
      return arr;
    }
  
  private:
    void sink(std::vector<int> &arr, int node, int size) {
      while (2*node + 1 <= size) {
        int max_node = 2*node + 1;
        if (max_node < size && arr[max_node] < arr[max_node+1]) {  // 找到最大孩子
          max_node++;
        }
        if (arr[node] >= arr[max_node]) {
          break;
        } else {
          std::swap(arr[node], arr[max_node]);
        }
        node = max_node;   // 持续下沉到叶子结点或满足条件
      }
    }
    // 从零开始，使用(n-1)/2
    void heap_sort(std::vector<int> &arr, int low, int high) {
      for (int i = (high-1) / 2; i >= 0; i--) {   // 构建最大堆 
        sink(arr, i, high);
      }
      while (high > 0) {    // 交换-下沉 完成排序
        std::swap(arr[high--], arr[0]);   // 最大元素挪到末尾，再调整堆
        sink(arr, 0, high);
      }
    }
};

冒泡排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr; 
      }
      bubble_sort(arr, arr.size()-1);
      return arr;
    }
  
  private:
    void bubble_sort(std::vector<int> &arr, int size) {
      for (int i = 0; i < size; i++) {  // n个元素循环n-1次
        for (int j = 0; j < size - i; j++) {  // 每次取出最大元素到最尾
          if (arr[j] > arr[j+1]) {
            std::swap(arr[j], arr[j+1]);
          }
        }
      }
    }
};

插入排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr;
      }
      insertion_sort(arr, arr.size()-1);
      return arr;
    }
  
  private:
    void insertion_sort(std::vector<int> &arr, int size) {
      for (int i = 1; i <= size; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
          arr[j+1] = arr[j];
          j--;
        }
        arr[j+1] = key;
      }
    }
};

选择排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr;
      }
      selection_sort(arr, arr.size()-1);
      return arr;
    }
  
  private:
    void selection_sort(std::vector<int> &arr, int size) {
      // 第一层循环选中n-1个元素
      // 从选中元素后面 挑选出最小的元素与当前元素交换
      // 选中元素最小则不交换
      for (int i = 0; i < size; i++) {
        int min = arr[i];
        int index = i;
        for (int j = i+1; j <= size; j++) {
          if (arr[j] < min) {
            min = arr[j];
            index = j;
          }
        }
        if (index != i) {
          std::swap(arr[i], arr[index]);
        }
      }
    }
};

计数排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr;
      }
      counting_sort(arr, arr.size()-1);
      return arr;
    }
  
  private:
    void counting_sort(std::vector<int> &arr, int size) {
      int max = arr[0];
      std::vector<int> copy_arr(arr);  // 辅助数组
      for (int i = 0; i <= size; i++) {
        if (arr[i] > max) {
          max = arr[i];
        }
      }  
      std::vector<int> temp(max+1, 0);  // 大小为数据区间
      for (int i = 0; i <= size; i++) {
        temp[arr[i]]++;  // 统计每个值出现的次数，存放在对应下标
      }
      // 计数累加
      for (int i = 1; i < temp.size(); i++) {
        temp[i] += temp[i-1];   // 记录当前值排的位数
      }
      // 反向填充数组
      for (int i = size; i >= 0 ; i--) {
        arr[--temp[copy_arr[i]]] = copy_arr[i];  // 索引比计数值小1，先自减
      }
    }
};

希尔排序

void shell_sort(std::vector<int> &a, int n) {
  int i,j,gap;

    // gap为步长，每次减为原来的一半。
  for (gap = n / 2; gap > 0; gap /= 2) {
        // 共gap个组，对每一组都执行直接插入排序
    for (i = 0 ;i < gap; i++) {
      for (j = i + gap; j < n; j += gap) {
                // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
        if (a[j] < a[j - gap]) {
          int tmp = a[j];
          int k = j - gap;
          while (k >= 0 && a[k] > tmp) {
            a[k + gap] = a[k];
            k -= gap;
          }
          a[k + gap] = tmp;
        }
      }
    }
  }
}     

二叉树的前中后序遍历（迭代）

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > threeOrders(TreeNode* root) {
      if (root == nullptr) {
        return std::vector<std::vector<int>>(3, std::vector<int>());
      }
      
      std::vector<std::vector<int>> res;
      std::stack<TreeNode *> s;
      std::vector<int> tmp;
      
      s.push(root);
      
      while (!s.empty()) {
        TreeNode *cur = s.top();
        s.pop();
        tmp.push_back(cur->val);
        if (cur->right) {
          s.push(cur->right);
        }
        if (cur->left) {
          s.push(cur->left);
        }
      }
      
      res.push_back(tmp);
      tmp.clear();
      
      TreeNode *node = root;
      //  中序
      while (node || !s.empty()) {
        while (node) {
          s.push(node);
          node = node->left;
        }
        
        TreeNode *cur = s.top();
        s.pop();
        tmp.push_back(cur->val);
        node = cur->right;
      }
      
      res.push_back(tmp);
      tmp.clear();
      
      s.push(root);
      
      while (!s.empty()) {
        TreeNode *cur = s.top();
        s.pop();
        tmp.push_back(cur->val);
        if (cur->left) {
          s.push(cur->left);
        }
        if (cur->right) {
          s.push(cur->right);
        }
      }
      
      std::reverse(tmp.begin(), tmp.end());
      res.push_back(tmp);
      
      return res;
    }
};

设计LRU缓存

class Solution {
  public:
    Solution(int capacity) {
      cap = capacity;
    }
    
    int get(int key) {
      if (hash.count(key)) {
        int val = hash[key]->second;
        lru.erase(hash[key]);
        lru.push_front({key, val});
        hash[key] = lru.begin();
        return val;
      } else {
        return -1;
      }
    }
    
    void set(int key, int value){
      if (hash.count(key)) {
        lru.erase(hash[key]);
      } else if (lru.size() >= cap) {
        hash.erase(lru.back().first);
        lru.pop_back();
      } 
      
      lru.push_front({key, value});
      hash[key] = lru.begin();
    }
  private:
    int cap;
    std::list<std::pair<int, int>> lru;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> hash;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* solution = new Solution(capacity);
 * int output = solution->get(key);
 * solution->set(key,value);
 */

TopK（小根堆还有快排变种）

//  小根堆
class Solution {
  public:
    int findKth(vector<int> a, int n, int K) {
      int res;
      
      //  创建k个元素的小根堆存放最大的k个元素
      create_heap(a, K - 1);
      
      for (int i = K; i < n; ++i) {
        if (a[i] > a[0]) {
          std::swap(a[i], a[0]);
          sink(a, 0, K - 1);
        }
      }
      
      //  堆顶就是第K大
      return a[0];
    }
  private:
    void create_heap(std::vector<int> &arr, int size) {
      for (int i = (size - 1) / 2; i >= 0; --i) {
        sink(arr, i, size);
      }
    }
  
    void sink(std::vector<int> &arr, int node, int size) {
      while (node * 2 + 1 <= size) {
        int min_node = node * 2 + 1;
        if (min_node < size && arr[min_node + 1] < arr[min_node]) {
          ++min_node;
        }
        if (arr[node] <= arr[min_node]) {
          return ;
        }
        std::swap(arr[node], arr[min_node]);
        node = min_node;
      }
    }
};

//  快排加分治
class Solution {
  public:
    int findKth(vector<int> a, int n, int K) {
      return quick_sort(a, 0, n - 1, K);
    }
  private:
    int quick_sort(std::vector<int> &arr, int left, int right, int k) {
      //  防止超时
      std::swap(arr[left], arr[(right + left) / 2]);
      int key = arr[left];
      int l = left, r = right;
      
      while (l < r) {
        while (l < r && arr[l] >= key) ++l;
        while (l < r && arr[r] <= key) --r;
        std::swap(arr[l], arr[r]);
      }
      
      if (arr[l] < key) {
        --l;
      }
      
      std::swap(arr[l], arr[left]);
      
      if (l + 1 == k) {
        return arr[l];
      } else if (l + 1 > k) {
        return quick_sort(arr, left, l - 1, k);
      } else {
        return quick_sort(arr, l + 1, right, k);
      }
    }
};

最小的K个数

//  快排加分治

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
      if (input.empty() || k == 0) {
        return std::vector<int>();
      }
      
      quick_sort(input, k, 0, input.size() - 1);
      
      return std::vector<int>(input.begin(), input.begin() + k);
    }
  void quick_sort(std::vector<int> &input, int k, int left, int right) {
    if (left >= right) {
      return ;
    } 
    
    int key = input[left];
    int l = left, r = right;
    
    while (l < r) {
      while (l < r && input[l] <= key) ++l;
      while (l < r && input[r] >= key) --r;
      std::swap(input[l], input[r]);
    }
    
    if (input[l] > key) {
      --l;
    }
    
    std::swap(input[l], input[left]);
    
    if (l + 1 == k) {
      return ;
    } else if (l + 1 > k) {
      quick_sort(input, k, left, l - 1);
    } else {
      quick_sort(input, k, l + 1, right);
    }
  }
};

//  最大堆法
class Solution {
  public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
      if (input.empty() || k == 0) {
        return std::vector<int>();
      }
      
      //  建立k个元素的最大堆
      create_heap(input, k - 1);
      
      //  调整堆
      for (int i = k; i < input.size(); ++i) {
        if (input[i] < input[0]) {
          std::swap(input[0], input[i]);
          sink(input, 0, k - 1);
        }
      }
      
      return std::vector<int>(input.begin(), input.begin() + k);
    }
  private:
    void create_heap(std::vector<int> &input, int size) {
      for (int i = (size - 1) / 2; i >= 0; --i) {
        sink(input, i, size);
      } 
    }
   
    void sink(std::vector<int> &input, int node, int size) {
      while (node * 2 + 1 <= size) {
        int max_node = node * 2 + 1;
        if (max_node < size && input[max_node + 1] > input[max_node]) {
          ++max_node;
        }
        if (input[node] >= input[max_node]) {
          return ;
        }
        std::swap(input[node], input[max_node]);
        node = max_node;
      }
    }
};