C++ 演算法面試常函式

簡介

這邊介紹我自己在解題會用到的小抄以及解題想法。

解題思路

1. 看題目：先想資料範圍、資料儲存形式、正負與大小會不會有影響、加總、乘積會不會超過 INT_MAX 等，這個是當下要跟面試官討論的部分
   1. 想題目的 edge case
   2. Overflow
2. 先講暴力破解方法，並且分析時間跟空間複雜度
3. 開始想資料結構和演算法優化
   1. One-pointer
      • Greedy
      • Prefix sum
   2. Two-pointer
      • 兩邊慢慢集中到中間
      • Sliding window
      • 快慢指標
   3. Sort
      • Binary search
   4. Divide and Conquer
   5. DP
      • Retrieve
      • Top-down/Bottom-up

常用資料結構

以下先提供各種小抄：

stack, queue, and priority_queue

注意 construct heap 是 O(n)，但排序整個 heap 是 nlog(n)

常用演算法函式

1. binary_search, lower_bound, upper_bound

   int a[100]= {4,10,11,30,69,70,96,100};
   int b=binary_search(a,a+9,4);//查找成功，返回1
   cout<<"在数组中查找元素4，结果为："<<b<<endl;
   int c=binary_search(a,a+9,40);//查找失败，返回0
   cout<<"在数组中查找元素40，结果为："<<c<<endl;
   int d=lower_bound(a,a+9,10)-a;
   cout<<"在数组中查找第一个大于等于10的元素位置，结果为："<<d<<endl;
   int e=lower_bound(a,a+9,101)-a;
   cout<<"在数组中查找第一个大于等于101的元素位置，结果为："<<e<<endl;
   int f=upper_bound(a,a+9,10)-a;
   cout<<"在数组中查找第一个大于10的元素位置，结果为："<<f<<endl;
   int g=upper_bound(a,a+9,101)-a;
   cout<<"在数组中查找第一个大于101的元素位置，结果为："<<g<<endl

2. sort

   std::sort(arr, arr+10, std::greater<int>());
   std::sort(v.begin(), v.end(), [](int a, int b){
       return a < b; // 升序排列
   });

3. reverse

   reverse(a.begin()+2, a.begin()+6);

4. next_permutation

   next_permutation(a, a+3);

5. accumulate(arr.begin(), arr.end(), 0);

演算法

1. Pointer
   • Two pointers
   • Sliding window
   • Prefix sum
2. Graph
   • BFS/DFS
   • Union Find
   • Topological Sort
3. Search
   • Binary Search

其他

Policy-Based Data Structures (PBDS)

GCC 編譯器內建的一套強大擴充庫，雖然它不屬於標準 C++ STL，但因為 Leetcode 是使用 GCC 環境編譯，所以你可以直接調用。

有各種額外的資料結構，像是：

1. Order Statistic Tree (能查排名的平衡樹)，在標準 STL 中，set 只能幫你排序和去重，但它沒辦法在 $O(\log n)$ 時間內告訴你「某個數字是第幾名」或「第 $k$ 大的數字是誰」，PBDS 補足了這個缺憾
2. gp_hash_table: 比 unordered_map 快非常多的 Hash Table（在某些題目可以避免被惡意測資卡掉）
3. Priority Queue: 比 STL 的更強大，支持 join（合併兩堆只要 $O(1)$ 或 $O(\log n)$）。

Refernce

• C++ STL 大全