代碼面試最常用的10大算法

面試也是一門學問，在面試之前做好充分的準備則是成功的必須條件 ，而程序員在代碼面試時，常會遇到編寫算法的相關(guān)問題，比如排序、二叉樹遍歷等等
。

在程序員的職業(yè)生涯中 ，算法亦算是一門基礎(chǔ)課程，尤其是在面試的時候 ，很多公司都會讓程序員編寫一些算法實例，例如快速排序、二叉樹查找等等。

本文總結(jié)了程序員在代碼面試中最常遇到的10大算法類型，想要真正了解這些算法的原理 ，還需程序員們花些功夫。

1.String/Array/Matrix

在Java中，String是一個包含char數(shù)組和其它字段 、方法的類
 。如果沒有IDE自動完成代碼 ，下面這個方法大家應該記住 ：

String/arrays很容易理解 ，但與它們有關(guān)的問題常常需要高級的算法去解決
 ，例如動態(tài)編程、遞歸等 。

下面列出一些需要高級算法才能解決的經(jīng)典問題：

Evaluate Reverse Polish Notation

Longest Palindromic Substring

單詞分割

字梯

Median of Two Sorted Arrays

正則表達式匹配

合并間隔

插入間隔

Two Sum

3Sum

4Sum

3Sum Closest

String to Integer

合并排序數(shù)組

Valid Parentheses

實現(xiàn)strStr()

Set Matrix Zeroes

搜索插入位置

Longest Consecutive Sequence

Valid Palindrome

螺旋矩陣

搜索一個二維矩陣

旋轉(zhuǎn)圖像

三角形

Distinct Subsequences Total

Maximum Subarray

刪除重復的排序數(shù)組

刪除重復的排序數(shù)組2

查找沒有重復的最長子串

包含兩個獨特字符的最長子串

Palindrome Partitioning

2.鏈表

在Java中實現(xiàn)鏈表是非常簡單的 ，每個節(jié)點都有一個值，然后把它鏈接到下一個節(jié)點 。

比較流行的兩個鏈表例子就是棧和隊列。

棧（Stack）

隊列（Queue）

值得一提的是，Java標準庫中已經(jīng)包含一個叫做Stack的類，鏈表也可以作為一個隊列使用（add()和remove()）。（鏈表實現(xiàn)隊列接口）如果你在面試過程中 ，需要用到?；蜿犃薪鉀Q問題時 ，你可以直接使用它們。

在實際中，需要用到鏈表的算法有：

插入兩個數(shù)字

重新排序列表

鏈表周期

Copy List with Random Pointer

合并兩個有序列表

合并多個排序列表

從排序列表中刪除重復的

分區(qū)列表

LRU緩存

3.樹&堆

這里的樹通常是指二叉樹。

下面是一些與二叉樹有關(guān)的概念 ：

二叉樹搜索：對于所有節(jié)點，順序是：left children <= current node <= right children；

平衡vs.非平衡 ：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹；

滿二叉樹：除最后一層無任何子節(jié)點外，每一層上的所有結(jié)點都有兩個子結(jié)點；

完美二叉樹（Perfect Binary Tree）：一個滿二叉樹，所有葉子都在同一個深度或同一級
，并且每個父節(jié)點都有兩個子節(jié)點；

完全二叉樹
：若設(shè)二叉樹的深度為h ，除第 h 層外 ，其它各層 (1 h-1) 的結(jié)點數(shù)都達到最大個數(shù)，第 h 層所有的結(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹 。

堆（Heap）是一個基于樹的數(shù)據(jù)結(jié)構(gòu)，也可以稱為優(yōu)先隊列（PriorityQueue），在隊列中，調(diào)度程序反復提取隊列中第一個作業(yè)并運行，因而實際情況中某些時間較短的任務將等待很長時間才能結(jié)束，或者某些不短小 
，但具有重要性的作業(yè)，同樣應當具有優(yōu)先權(quán)。堆即為解決此類問題設(shè)計的一種數(shù)據(jù)結(jié)構(gòu)