常見的演算法實現

常見的演算法實現

1 人贊了文章

推薦幾個不錯的學習測試演算法的工具吧。首先是Leetcode，這是一個美國的在線編程網站,上面主要收集了各大IT公司的筆試面試題,對於應屆畢業生找工作是一個不可多得的好幫手。Leetcode的主要特點就是按照難易將題目分為了easy、medium和hard三種，並且在leetcode上將題目進行了分類。在自己練習通過之後可以打開討論區，看看別人是怎麼思考解決該問題的。其次是牛客網，這是一個專註於程序員的學習和成長的專業平台，集筆面試系統、課程教育、社群交流、招聘內推於一體。我們可以在在線編程模塊進行演算法題的練習。

接下來我們正式開始常見演算法題的介紹，主要內容包括以下七個小節：

• 排序和查找演算法
• 單鏈表
• 二叉樹
• 隊列和棧
• 字元串
• 數組
• 其它演算法

第一節：排序和查找演算法

在排序中，90%的概率會考察快速排序演算法，所以我們需要準備一個沒有任何bug的快速排序演算法。當面試官讓我們寫一個快排的時候，我們可以毫不猶豫的寫出來。在一些簡單的時候，面試官可能會要求你寫一個二分查找演算法。

快速排序：是一種分區交換排序演算法。採用分治策略對兩個子序列再分別進行快速排序，是一種遞歸演算法。

法描述：在數據序列中選擇一個元素作為基準值，每趟從數據序列的兩端開始交替進行，將小於基準值的元素交換到序列前端，將大於基準值的元素交換到序列後端，介於兩者之間的位置則成為了基準值的最終位置。同時，序列被劃分成兩個子序列，再分別對兩個子序列進行快速排序，直到子序列的長度為1，則完成排序。

舉例：假設要排序的數組是a[6],長度為7，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一躺快速排序。一躺快速排序的演算法是：

1. 設置兩個變數i，j，排序開始的時候i=0；j=6；
2. 以第一個數組元素作為關鍵數據，賦值給key，即key=a[0]；
3. 從j開始向前搜索，即由後開始向前搜索（j--），找到第一個小於key的值，兩者交換；
4. 從i開始向後搜索，即由前開始向後搜索（i++），找到第一個大於key的值，兩者交換；
5. 重複第3、4步，直到i=j；此時將key賦值給a[i]；

例如：待排序的數組a的值分別是：（初始關鍵數據key=49）

此時完成了一趟循環，將49賦值給a[3]，數據分為三組，分別為{27,38,13}{49}{76,96,65}，利用遞歸，分別對第一組和第三組進行排序，則可得到一個有序序列，這就是快速排序演算法。

快速排序代碼如下：

public void sort(int a[], int low, int high){ if (low < high){ int i=low; int j=high; int key=a[low]; while(i<j){ // 此處的while循環結束，則完成了元素key的位置調整 while(i<j&&key<=a[j]){ j--; } a[i]=a[j]; while(i<j&&key>=a[i]){ i++; } a[j]=a[i]; a[i]=key; //此處不可遺漏 } sort(a,low,i-1); sort(a,i+1,high); } }

二分查找又稱折半查找，優點是比較次數少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。

步驟：首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重複以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

演算法前提：必須採用順序存儲結構；必須按關鍵字大小有序排列。

實現方式：包含遞歸實現和非遞歸實現兩種方式。二分查找的遞歸代碼實現如下：

private int halfSearch(int[] a,int left,int right,int target) { int mid=(left+right)/2; int midValue=a[mid]; if(left<=right){ if(midValue>target){ return halfSearch(a, left, mid-1, target); }else if(midValue<target) { return halfSearch(a, mid+1, right, target); }else { return mid; } } return -1; }

非遞歸實現代碼如下：

private int halfSearch(int[] a,int target){ int i=0; int j=a.length-1; while(i<=j){ int mid=(i+j)/2; int midValue=a[mid]; if(midValue>target){ j=mid-1; }else if(midValue<target){ i=mid+1; }else { return mid; } } return -1; }

篇幅有限，更多排序查找演算法，請參考我的博客：

• 排序查找演算法大總結

第二節 單鏈表相關演算法

對鏈表的操作由於涉及到指針，所以鏈表是一種極其常見的演算法考題。常見的鏈表題有：單鏈表反轉、合併有序單鏈表、求單鏈表的中間節點、判斷單鏈表相交或者有環、求出進入環的第一個節點、求單鏈表相交的第一個節點等。

我們首先給出單鏈表的定義：用代碼實現。

class Node{ int val; Node next; public Node(int val){ this.val=val; }}

單鏈表反轉：比如1→2→3→4→5，反轉之後返回5→4→3→2→1

步驟：

1. 從頭到尾遍歷原鏈表，每遍歷一個結點
2. 將其摘下放在新鏈表的最前端。
3. 注意鏈表為空和只有一個結點的情況。

代碼實現如下：

public static Node reverseNode(Node head){ // 如果鏈表為空或只有一個節點，無需反轉，直接返回原鏈表表頭 if(head == null || head.next == null) return head; Node reHead = null; Node cur = head; while(cur!=null){ Node reCur = cur; // 用reCur保存住對要處理節點的引用 cur = cur.next; // cur更新到下一個節點 reCur.next = reHead; // 更新要處理節點的next引用 reHead = reCur; // reHead指向要處理節點的前一個節點 } return reHead; }

合併有序的單鏈表：給出兩個分別有序的單鏈表，將其合併成一條新的有序單鏈表。

舉例：1→3→5和2→4→6合併之後為1→2→3→4→5→6 步驟：首先，我們通過比較確定新鏈表的頭節點，然後移動鏈表1或者鏈表2的頭指針。然後通過遞歸來得到新的鏈表頭結點的next 代碼實現如下：

public static Node mergeList(Node list1 , Node list2){ if(list1==null) return list2; if(list2==null) return list1; Node resultNode; if(list1.val<list2.val){ // 通過比較大小，得到新的節點 resultNode = list1; list1 = list1.next; }else{ resultNode = list2; list2 = list2.next; } // 遞歸得到next resultNode.next = mergeList(list1, list2); return resultNode; }

篇幅有限，更多鏈表相關演算法請參考我的博客：

• 鏈表基礎題大全（一）
• 鏈表基礎題大全（二）
• 多種單鏈表反轉面試題總結

第三節 二叉樹相關演算法

二叉樹相比單鏈表，會有更多的指針操作，如果面試官想進一步考察應聘者指針操作，那麼二叉樹無疑是理想的考題。二叉樹常見的考題包括：分層遍歷（寬度優先遍歷. 前序遍歷、中序遍歷、後序遍歷以及求二叉樹中兩個節點的最低公共祖先節點。

我們首先定義二叉樹這種數據結構，代碼實現如下：

class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; }}

面試中，對分層遍歷二叉樹考察最多。舉例如下，針對如下所示的二叉樹。

其分層遍歷（寬度優先遍歷）序列為：1,2,3,4,5,6,7,8,9,10 可以看出，這好像符合一種先進先出的規律，我先遍歷到某個節點，就將其輸出。想到用過隊列Queue來實現分層遍歷。

步驟：隊列初始化，將根節點壓入隊列。當隊列不為空，進行如下操作：彈出一個節點，訪問，若左子節點或右子節點不為空，將其壓入隊列 。

代碼實現如下：

public static void levelTraversal(TreeNode root){ if(root==null) return ; LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); // 隊列初始化，將根節點加入隊列 while(!queue.isEmpty()){ TreeNode cur = queue.remove(); System.out.print(cur.val+" "); if(cur.left!=null) queue.add(cur.left); if(cur.right!=null) queue.add(cur.right); } }

說完了寬度優先遍歷二叉樹，我們再來一個深度優先遍歷二叉樹，也就是二叉樹的前序遍歷序列。

這顆二叉樹的前序遍歷序列為：abdefgc。前序遍歷中，遍歷順序為根左右，也就是左節點在右節點之前，我們考慮使用堆棧這種後進先出的數據結構來實現。

步驟：使用一個輔助堆棧，初始時將根節點加入堆棧，當堆棧不為空時，彈出一個節點，分別將其不為空的右子節點和左子節點加入堆棧。 代碼實現如下：

public static void preorderTraversal(TreeNode root){ if(root==null) return ; Stack<TreeNode> stack = new Stack<TreeNode>(); // 輔助stack stack.push(root); while(!stack.isEmpty()){ TreeNode cur = stack.pop(); // 出棧棧頂元素 System.out.print(cur.val+" "); // 關鍵點：要先壓入右孩子，再壓入左孩子，這樣在出棧時會先列印左孩子再列印右孩子 if(cur.right!=null) stack.push(cur.right); if(cur.left!=null) stack.push(cur.left); } }

篇幅有限，更多關於二叉樹的常考演算法題，請參考我的博客：

• 二叉樹基礎題（一）
• 二叉樹基礎題（二）
• 二叉樹路徑問題 Path SUM（①②③）
• 樹中兩個節點的最低公共祖先節點

第四節 隊列和堆棧相關演算法

隊列和堆棧通常在演算法題的考察中會作為一種輔助的數據結構出現。分別利用其先進先出和後進先出的特性。

但是，有時候會單純的考察隊列和堆棧的相關知識，常見的演算法題包括：包含min函數的堆棧、兩個棧實現隊列以及自定義堆棧的實現等。

題目：包含min函數的棧

定義棧的數據結構，請在該類型中實現一個能夠得到棧最小元素的min函數。在該棧中，調用min、push和pop方法。要求的時間複雜度均為O(1)

思路：題目要求我們的各個方法均為O(1)複雜度，則我們考慮增加輔助空間來實現，即增加一個專門用來存儲min值的輔助棧。

比如，data中依次入棧，5, 4, 3, 8, 10, 11, 12, 1。則輔助棧依次入棧， 5, 4, 3，no,no, no, no, 1。no代表此次不如棧。即，每次入棧的時候，如果入棧的元素比min中的棧頂元素小或等於則入棧，否則不入棧。

代碼實現如下：

import java.util.Stack; public class Main { Stack<Integer> stack = new Stack<>(); Stack<Integer> minStack = new Stack<>(); public void push(int node) { stack.push(node); if(minStack.isEmpty()||minStack.peek()>=node) minStack.push(node); } /** * 首先需要對stack執行出棧操作, * 判斷minStack中是否需要出棧操作 */ public void pop() { stack.pop(); if(stack.peek()==minStack.peek()){ minStack.pop(); } } public int top() { return stack.peek(); } /** * 直接peek minStack * @return */ public int min() { return minStack.peek(); } }

該實現演算法中，在push和pop操作中，均有判斷，判斷值相等一定要用peek方法而不是pop！！！切記切記，關鍵點。

篇幅有限，更多關於隊列和堆棧的常考演算法題，請參考我的博客：

• 用兩個棧實現隊列
• 如何自定義實現堆棧？

第五節 字元串相關演算法

字元串是一種非常常見的數據類型，我們應當對API中常用的函數進行一定的學習和了解。在字元串的考察中，比較經典的是自定義一個函數實現字元串轉整數的功能；加大難度之後，會考察以下常見的5種關於字元串中「最長」問題：

1. 最長公共子序列
2. 最長公共子串
3. 最長遞增子序列
4. 最長公共前綴
5. 最長不含重複元素的子串

來看自定義一個函數，實現字元串轉換成整數。當面試官說出這個題時，他肯定會避免和你說太多，只說出了最簡單的要求。如果你立馬動筆刷刷刷的用了三分鐘就說寫好了。

那麼，對不起，我敢以人格擔保，你這輪面試絕對死翹翹了。。。這道題看似簡單，而且面試官也沒有提醒你應該注意哪些。但是！！，這道題的目的就是為了考察你的特殊情況處理能力，你能不能想到會有哪些特殊情況或者邊界處理，這才是本題的重點。

那麼，遇到這道題，我們應該如何面對？我們要不慌不亂的和面試官親切交談，制定該函數的一些規則，即如何處理異常輸入等，之後，再遍曆數組，根據需求進行相應的異常處理哦~

首先，我們應該要想到本題的一些特殊情況。

本題的特殊情況如下：

1. 能夠排除首部的空格，從第一個非空字元開始計算
2. 允許數字以正負號(+-)開頭
3. 遇到非法字元便停止轉換，返回當前已經轉換的值，如果開頭就是非 法字元則返回0
4. 在轉換結果溢出時返回特定值，這裡是最大/最小整數

我們需要針對以上的特殊情況和面試官親切交流，詢問如果有特殊情況該如何處理。

其次，我們要想到一些測試用例，根據測試用例來詢問面試官輸出是否應該為XX。

先來幾組測試用例：

" 010"" +004500"" -001+2a42"" +0 123""-2147483648""2147483648"" - 321"" -11919730356x""9223372036854775809"

以上的測試用例對應的正確輸出如下：

104500-10-214748364821474836470-21474836482147483647

如果你能想到這些特殊情況和測試用例，那麼恭喜你，你已經成功了90%，面試官會從心底里開始欣賞你。

最後，代碼的編寫（so easy）

代碼如下：

public static int myAtoi(String str) { if(str==null||str.length()==0) return 0; char[] array = str.toCharArray(); long result = 0; // 要返回的結果result int count = 0; // 記錄『+』或者『-』出現的次數 int num = 0; // 判斷空格出現的位置 int flag = 1; // 正數還是負數 for (int i = 0; i < array.length; i++) { Character c = array[i]; if(c>=0&&c<=9){ result = result*10+c-0; // 判斷是否溢出 if(flag==1&&result>Integer.MAX_VALUE){ return Integer.MAX_VALUE; }else if(flag==-1&&-result<Integer.MIN_VALUE) return Integer.MIN_VALUE; num++; }else if(c== &&num==0&&count==0) continue; else if(c==+&&count==0){ count = 1; } else if(c==-&&count==0){ flag = -1; count = 1; } else{ return (int) (flag*result); } } return (int) (flag*result); }

篇幅有限，更多字元串相關常考演算法，請參考我的博客：

• 5種關於字元串中「最長」問題的解法

第六節 數組相關演算法

數組也是一種極其常見的數據結構，在面試中和數組相關的演算法題出現頻率賊高。對數組的操作，一般會要求時間複雜度和空間複雜度。所以，最常用的方法就是設置兩個指針，分別指向不同的位置，不斷調整指針指向來實現O（N）時間複雜度內實現演算法。常見的面試題有：拼接一個最大/小的數字、合併兩個有序數組、調整數組順序使奇數位於偶數前面、查找多數元素、數組中的重複元素

題目一：查找多數元素

找出一個數組中佔50%以上的元素，即尋找多數元素，並且多數元素是一定存在的假設。

思路1：將數組排序，則中間的那個元素一定是多數元素

public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; }

該代碼的時間複雜度為O（NlogN），面試官會問你能不能進行優化時間複雜度？

思路2：利用HashMap來記錄每個元素的出現次數

public int majorityElement(int[] nums) { HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if(!map.containsKey(nums[i])){ map.put(nums[i], 1); }else { int values = map.get(nums[i]); map.put(nums[i], ++values); } } int n = nums.length/2; Set<Integer> keySet = map.keySet(); Iterator<Integer> iterator = keySet.iterator(); while(iterator.hasNext()){ int key = iterator.next(); int value = map.get(key); if (value>n) { return key; } } return 0; }

該代碼的時間複雜度為O（N），空間複雜度為O（N）。面試官還不滿意，問你能不能用O（N）+O（1）實現該演算法？

思路3：Moore voting algorithm--每找出兩個不同的element，就成對刪除即count--，最終剩下的一定就是所求的。

public int majorityElement(int[] nums) { int elem = 0; int count = 0; for(int i = 0; i < nums.length; i++) { if(count == 0) { elem = nums[i]; count = 1; } else { if(elem == nums[i]) count++; else count--; } } return elem; }

完美，這才是本題的正確最優解。

題目二：把數組排成最小的數

輸入一個正整數數組，把數組裡所有數字拼接起來排成一個數，列印能拼接出的所有數字中最小的一個。例如輸入數組{3，32，321}，則列印出這三個數字能排成的最小數字為321323。

思路：我們需要定義一種新的比較大小規則，數組根據這個規則可以排成一個最小的數字。

排序規則：兩個數字m和n，我們比較mn和nm的大小，來確定在新的比較規則下n和m的大小關係，來確定哪個應該排在前面

步驟：將整型數組轉換為String數組。在新的規則下對數組進行排序（本例使用了選擇排序）。

public String PrintMinNumber(int [] num) { if(num==null||num.length==0) return ""; int len = num.length; String[] str = new String[len]; for(int i = 0; i < len; i++){ str[i] = String.valueOf(num[i]); } for (int i = 0; i < str.length; i++) { for (int j = i+1; j < str.length; j++) { if(compare(str[i], str[j])){ String temp = str[j]; str[j] = str[i]; str[i] = temp; } } } StringBuilder sb = new StringBuilder(); for(int i = 0;i<str.length;i++){ sb = sb.append(str[i]); } return sb.toString(); } private boolean compare(String s1,String s2){ int len = s1.length()+s2.length(); String str1 = s1+s2; String str2 = s2+s1; for (int i = 0; i < len; i++) { if(Integer.parseInt(str1.substring(i,i+1))>Integer.parseInt(str2.substring(i,i+1))) return true; if(Integer.parseInt(str1.substring(i,i+1))<Integer.parseInt(str2.substring(i,i+1))) return false; } return false; }

篇幅有限，更多數組相關演算法，請參考我的博客：

• 在排序數組中查找數字出現的次數
• 數組中數字出現的次數
• 調整數組順序使奇數位於偶數前面
• 數組中的重複元素

第七節 Others Algorithm

其它常見的演算法題還有青蛙跳台階問題。

題目一：青蛙跳台階問題

一隻青蛙一次可以跳上1級台階，也可以跳上2級台階。求該青蛙跳上一個n級台階總共有多少種跳法？

分析：當n = 1， 只有1中跳法；當n = 2時，有2種跳法；當n = 3 時，有3種跳法；當n = 4時，有5種跳法；當n = 5時，有8種跳法；.......規律類似於Fibonacci數列：

遞歸實現的代碼如下：

public int Fibonacci(int n){ if(n<=2) return n; return Fibonacci(n-1)+Fibonacci(n-2); }

當我們寫出遞歸代碼時，面試官應該會建議我們對遞歸代碼進行優化，因為遞歸代碼中有太多的重複運算。所以，我們考慮使用使用變數保存住中間結果。 代碼實現如下：

public int jumpFloor(int number) { if(number<=2) return number; int jumpone=2; // 離所求的number的距離為1步的情況，有多少種跳法 int jumptwo=1; // 離所求的number的距離為2步的情況，有多少種跳法 int sum=0; for(int i=3;i<=number;i++){ sum=jumptwo+jumpone; jumptwo=jumpone; jumpone=sum; } return sum; }

題目二：青蛙變態跳台階問題

一隻青蛙一次可以跳上1級台階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的台階總共有多少種跳法。

解題思路：

• 先跳到n-1級，再一步跳到n級，有f(n-1)種；
• 先跳到n-2級，再一步跳到n級，有f(n-2)種；
• 先跳到n-3級，再一步跳到n級，有f(n-3)種；
• 。。。。。。
• 先跳到第1級，再一步跳到n級，有f(1)種；
• 所以：
• f(n)=f(n-1)+f(n-2)+f(n-3)+···+f(1)
• f(n-1)=f(n-2)+f(n-3)+···+f(1)
• 推出f(n)=2*f(n-1)

代碼實現如下：

public int jumpFloor2(int num) { if(num<=2) return num; int jumpone=2; // 前面一級台階的總跳法數 int sum=0; for(int i=3;i<=num;i++){ sum = 2*jumpone; jumpone = sum; } return sum; }

結束語

當各位同學讀到此處時，你可能只是僅僅對文章內容進行了一次簡單的瀏覽，還來不及細細消化品味文中演算法的樂趣。誠然，這是一篇特別長的文章。因為，我的本意是將每一小節都寫成一個單獨的課時，這樣方便讀者閱讀，不至於產生疲憊感。但是，我後來才知道，達人課才能那麼寫，普通的單場Chat就是一篇文章搞定。所以，我只能儘可能的精簡篇幅，以使讀者不至於閱讀疲憊。

備註：

知乎演算法：互聯網公司最常見的面試演算法題有哪些？

推薦閱讀：