計算機專業保研面試備考：計算機算法（必看）

本文總結了計算機專業保研面試中較為常考的算法題目，也是部落客當年的備考材料。如果這篇文章對你有幫助，請給部落客點個贊鼓勵一下吧。

• 排序算法
  • 綜述

    

  • 評價标準
    • 時間複雜度：比較+移動/交換，最好/最壞/平均
    • 空間複雜度：是否原地排序
    • 穩定性：順序的問題
  • 常見算法
    • 插入排序（穩定）
      • 通過while向前移動

        

      • 

      • 最好：O(n)；最壞：O(n^2).
    • 選擇排序（不穩定）
      • 每次選擇最小的元素交換

        

      • 一種實作方式：

        

      • 最好：O(n^2)，最壞：O(n^2)
    • 冒泡排序（穩定）
      • 每次比較相鄰元素并交換

        

      • 

      • 最好O(n) 最壞O(n^2)
    • 歸并排序（穩定）
      • 平均、最好、最壞：O(nlogn)
      • 分+排+合
      • 每次合并都要用到一個臨時數組，之後将資料拷貝到原數組
    • 快速排序（不穩定）
      • 平均時間複雜度是 O（nlogn），最壞情況下的時間複雜度是 O（n^2）
      • 每次選擇第一個為基準數，兩個哨兵i、j，每次先移動j；遞歸
    • 計數排序（可以穩定，可以不穩定）
      • 不穩定：用額外的數組記錄輸入資料中各資料出現的次數，然後将資料按出現頻數取出
      • 穩定：将count改為累計，使用臨時數組存儲結果，反向填充數組
    • 桶排序（穩定）
      • 桶代表的是一個區間範圍。将數組配置設定到有限量的桶裡，然後對每個桶分别進行排序。

        

      • 數組元素n，m個桶。平均每個桶的元素個數為k = n/m個。如果在桶内我們使用快速排序，總的時間複雜度即為nlog(n/m)。如果桶的數量接近元素的數量，桶排序的時間複雜度就是O(n) 了。如果所有的元素都到了一個桶了，時間複雜度退化成 O(nlogn) 。
    • 基數排序（穩定）
      • 整數排序算法，将整數按位切割成不同的數字（分桶），然後按每個位數分别比較。
        • 設定10個桶，分别存放位數為0-9的元素。
        • 周遊初始序列，将元素放入不同的桶中
        • 按照桶的順序，把桶中元素全部拿出來重新組裝成一個序列
        • 重複2、3步驟，直到最高位。即可完成排序
      • 設待排序列為n個記錄，序列中最大值的位數為d，數字的基數為 r，則進行鍊式基數排序的時間複雜度為O(d(n+r))。
    • 希爾排序（改進的插入排序，不穩定）
      • 把序列按一定間隔分組，對每組使用直接插入排序；随着間隔減小，一直到1，使得整個序列有序
      • 時間複雜度複雜
    • 堆排序（不穩定）
      • 建堆：從最後一個非葉結點開始shift_dowm
      • pop：最後一個結點提到根部，shift_down根節點
      • 最好最壞以及平均情況下的時間複雜度均為O(nlogn)
• P問題、NP問題
  • P問題：Polynomial-time問題，能夠在多項式時間内用算法求解的問題
  • NP問題：非确定型多項式時間（nondeterministic polynomial-time）問題，指不确定是否存在多項式時間的求解算法，但可以在多項式時間内驗證一個猜測解的正确性的問題
  • 任意一個NP完全問題如果能夠在多項式時間内解決，則所有的NP問題都能在多項式時間内解決
  • NPC類問題（Nondeterminism Polynomial complete），指所有NP問題都能在多項式時間複雜度内歸約到的NP問題
  • NP難問題，指所有NP問題都能在多項式時間複雜度内歸約到的問題

  • 

• 主方法
  • 求解遞推式的時間複雜度

    

    

• 最短路徑算法
  • Dijkstra
    • 求單源、無負權的最短路
    • 松弛操作
    • 時間複雜度O(n^2)
  • Floyd
    • 求多源、無負權邊的最短路
    • 從i号頂點到j号頂點隻經過前k号點的最短路程

      

  • Bellman-Ford
    • 求單源最短路，可以判斷有無負權回路
    • 就是我小班課講過的東西：在每次的周遊過程中，對所有的邊進行周遊判斷

      

• 無序數組尋找中位數
  • 線性選擇算法：快排遞歸處理劃分的兩邊，而線性選擇隻對其中的一個部分進行處理。具體步驟為：
    • A[p...r]通過随機劃分函數得到樞軸q
    • 根據劃分的兩個區間A[p...q-1],A[q],A[q+1...r]
    • 然後判斷<=A[q]的元素數量k=q-p+1 與 需要尋找的第i小的關系，決定處理左面還是右面
    • O(n)
• 最長公共子序列
  • c[i][j]表示串1前i個字元、串2前j個字元的最長公共子序列長度

    

  • 如果想要得到串本身：

    

    • 在對應字元相等的時候，用↖标記
    • 在p1 >= p2的時候，用↑标記
    • 在p1 < p2的時候，用←标記
• 最長公共字串
  • 當A[i] != B[j]，dp[i][j] = 0
  • 當A[i] == B[j]，
    • 若i = 0 || j == 0，dp[i][j] = 1
    • 否則 dp[i][j] = dp[i - 1][j - 1] + 1
• 01背包問題

  • 

• 卡特蘭數
  • 适用題型：有一個大問題A，規模為n，要解決這個問題，可以用分治的思想，首先固定其中某一個元素，将剩下的n-1個元素拆分成兩個小問題，這兩個小問題的規模分别是(0,n-1) (1,n-2) (2,n-3) ... (n-1,0)
  • 如：
    • 二叉樹計數，n個結點的二叉樹，首先固定根節點，将剩下的n-1個結點拆分給左右子樹
    • 從1到n可以建構的BST的數目
    • 三角形劃分問題，凸(n+2)邊形可以劃分為n個三角形，首先固定一條邊（即一個三角形），這個三角形将這個(n+2)邊形拆分成兩個更小的多邊形
  • 遞推式：

    

  • 通項公式：

    

• 第K大的數
  • 借助最小堆，保持堆的大小為K，O(nlogk)
  • 基于快速排序，隻關注位置k，o(n)