演算法思維題

Ⅰ 大公司筆試面試有哪些經典演算法題目

1、二維數組中的查找

具體例題：如果一個數字序列逆置之後跟原序列是一樣的就稱這樣的數字序列為迴文序列。例如：{1, 2, 1}, {15, 78, 78, 15} , {112} 是迴文序列, {1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是迴文序列。現在給出一個數字序列，允許使用一種轉換操作：選擇任意兩個相鄰的數，然後從序列移除這兩個數，並用這兩個數字的和插入到這兩個數之前的位置(只插入一個和)。現在對於所給序列要求出最少需要多少次操作可以將其變成迴文序列？

Ⅱ 演算法如何刷題

1、原題
我自己感覺原題的概率還是挺大的，特別是劍指offer的66題更是如此。千萬別小看這66題，這幾十道題裡面基本所有的演算法類型都有包括在內，常用的數據結構，操作方式，常用演算法思路都有不少的題。

如果真的能夠充分理解這幾十道題的最優解，我感覺其實已經形成基本的演算法思維了。

另外，leetcode的原題也很常見，因為LC本身題量大，在裡面出原題不是為了考倒你，而是檢驗你的刷題質量。

畢竟那些大公司面試官也不是傻子，知道你在面試前肯定會大規模刷題的。所以把刷過的題完全搞懂才是最重要的。

2、改編題
改編題就很顯而易見了。改編題大多需要從基本的演算法原理中找到處理的思維，然後結合實際題干進行性能優化，就能夠搞定。

這里要記得一點的是，正常的演算法考察不會故意刁難你（正常情況），也不會給過多的時間讓你思考和敲代碼。

所以遇到改編題不要想得太復雜，盡量要找到它的演算法思維是什麼。怎麼說呢，透過現象看本質。我總結的改編題有以下幾種思路：

1）新的數據結構，換湯不換葯。比如最常見的排序演算法的改編，原來是對數字進行排序，現在對鏈表排序等等。比較難一點的可能會遇到自定義的數據結構。但是演算法本質不會變。

2）演算法類型改編。

這里要說的就是一個比較大的范圍，比如動態規劃、貪心演算法、遞歸、回溯和分治等等。這種是從演算法大的類型上進行改編，很難用相同的套路去解題。

遇到這類題的關鍵就是要先弄明白演算法核心。比如動態規劃的狀態方程，貪心演算法的局部最優情況，遞歸回溯的邊界判斷，分治的子問題劃分等等。這種類型的確比較難把握，怎麼碩呢，每種類型的都來搞幾道感覺感覺吧。

3）添加應用題背景。

這種題目看起來不難，但是難就難在對應用題背景的理解，需要去理解題意，然後考慮合適的數據結構和處理演算法。這裡面有數學建模的思維在裡面，需要把一堆無用的信息剔除，篩選出有效的信息，然後才能選擇正確的演算法。

3、創新題
這類題考察的是你的擴展思維，如果說上面的題考查的是你的思維深度，這種題就是考察演算法的廣度。可能一看題目，完全沒見過這種類型。但是演算法本身其實不就是讓計算機代替人腦進行高重復性的計算嘛。

首先你需要想到你應該去怎麼算這個題，然後再換到計算機上，會發生什麼問題（空間時間問題，運行效率，代碼冗餘等等），之後再想通過經典的演算法原理來解決這些

1、題型分類
按照個人的習慣，喜歡按照一種類型狂刷，然後再刷另外一種類型。一般常見的演算法類型可分為：

數組、鏈表

包含基本排序演算法、二分查找、鏈表的一系列操作。

棧、隊列、堆

利用棧、隊列互相實現，堆的使用

二叉樹與圖

主要是遍歷演算法和節點的計算：
二叉樹四種遍歷方式、廣度優先遍歷（BFS）和廣度優先遍歷（DFS），節點到節點距離等等。

哈希表

使用標准庫自帶的模板或者函數就很簡單了，一般會與其它數據結構相結合來提升時間復雜度。

字元串操作

字元串的操作也很多，本質上可以看作是數組的操作。另外字元串的一些匹配和尋求字串的演算法還是非常具有思考價值的。KMP，馬拉車等等。

遞歸

重點掌握邊界判斷條件。

回溯

重點掌握邊界判斷條件。

分治

重點掌握如何劃分子問題。

動態規劃

題太多了，可從一階dp到二階dp理解不同的狀態方程。

貪心及其它

這個就很容易理解了，遇到貪心題應該要偷笑了。

2、高頻熱點多刷
這不多說了吧，Leetcode熱題HOT 100。你值得擁有。

在不知道怎麼刷的情況下，不如先刷起來。刷個題沒那麼多捷徑，只有堅持刷起來了，才會形成自己的思維方式和學習習慣。

我建議是先按照類型刷，每個類型刷十幾二十道。然後打混按照演算法熱度排序重新查漏補缺。

3、思路回顧
許多同學在一股腦刷了很多題之後，再看做過的題會發現忘了不少。可能大家都是這樣的吧。我覺得是因為在刷題的時候過於心急，理解了大概就過了，或者類型做的太雜，沒有留下印象。

我比較喜歡的方式是偶爾會重新看看曾經做過的題，就看題目然後想思路，再畫一畫步驟演進，沒時間就不細敲了。這樣可以增強一下思維記憶，之前理解過的東西，再回憶起來還是非常快的。

Ⅲ 面試官常問十大經典演算法排序（用python實現）

演算法是一種與語言無關的東西，更確切地說就算解決問題的思路，就是一個通用的思想的問題。代碼本身不重要，演算法思想才是重中之重

我們在面試的時候總會被問到一下演算法，雖然演算法是一些基礎知識，但是難起來也會讓人非常頭疼。

排序演算法應該算是一些簡單且基礎的演算法，但是我們可以從簡單的演算法排序鍛煉我們的演算法思維。這里我就介紹經典十大演算法用python是怎麼實現的。

十大經典演算法可以分為兩大類：

比較排序： 通過對數組中的元素進行比較來實現排序。

非比較排序： 不通過比較來決定元素間的相對次序。

演算法復雜度

冒泡排序比較簡單，幾乎所有語言演算法都會涉及的冒泡演算法。

基本原理是兩兩比較待排序數據的大小 ，當兩個數據的次序不滿足順序條件時即進行交換，反之，則保持不變。

每次選擇一個最小（大）的，直到所有元素都被輸出。

將第一個元素逐個插入到前面的有序數中，直到插完所有元素為止。

從大范圍到小范圍進行比較-交換，是插入排序的一種，它是針對直接插入排序演算法的改進。先對數據進行預處理，使其基本有序，然後再用直接插入的排序演算法排序。

該演算法是採用 分治法 對集合進行排序。

把長度為n的輸入序列分成兩個長度為n/2的子序列，對這兩個子序列分別採用歸並排序，最終合並成序列。

選取一個基準值，小數在左大數在在右。

利用堆這種數據結構所設計的一種排序演算法。

堆是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。利用最大堆和最小堆的特性。

採用字典計數-還原的方法，找出待排序的數組中最大和最小的元素，統計數組中每個值為i的元素出現的次數，對所有的計數累加，將每個元素放在新數組依次排序。

設置一個定量的數組當作空桶；遍歷輸入數據，並且把數據一個一個放到對應的桶里去；對每個不是空的桶進行排序；從不是空的桶里把排好序的數據拼接起來。

元素分布在桶中：

然後，元素在每個桶中排序：

取得數組中的最大數，並取得位數；從最低位開始取每個位組成新的數組；然後進行計數排序。

上面就是我整理的十大排序演算法，希望能幫助大家在演算法方面知識的提升。看懂之後可以去試著自己到電腦上運行一遍。最後說一下每個排序是沒有調用數據的，大家記得實操的時候要調用。

參考地址：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html