猿輔導（實習800-天）面試演算法題詳解
不是標題黨：猿輔導的實習薪資確實開到了800一天，度娘截圖如下：
博主第一次聽說猿輔導這家公司也是因為逆天的實習薪資，也正是因為這個原因博主才投遞了簡歷，並且在拿到滿意的offer之後依舊去參加了面試。僅僅因為好奇，想體驗實習800一天的公司面試。
博主8月中上旬參加了猿輔導的在線筆試，猿輔導的筆試時間很緊張，四十多分鐘好像：選擇題和兩道編程題。編程題不能跳出考試頁面，相當於記事本撕代碼，時間很緊。其中一道筆試題是：用指定字元在屏幕上輸出「Y」形狀，「Y」的各部分的長度都是通過輸入給定。感覺與演算法無關，更多屬於細節和代碼功底的考察。
現在回過頭來看，猿輔導的面試注重點和今日頭條很相似：java基礎、源碼和演算法，這兩個公司的面試基本都沒怎麼問項目。面試呢，猿輔導一共只有兩輪技術面，一面主要是：java語言的一些基本語法特性、JDK源碼和手撕演算法。今天和大家分享的是博主在猿輔導一面期間遇到的兩道演算法題，兩道演算法題都是原題。
是不是原題其實不是很重要，原題不是你輕視面試的原因。重要的是：你問問自己能不能在十分鐘內完成A4紙手撕代碼？能不能保證代碼的正確率？能不能清晰的向面試官描述你的代碼思路(否則會覺得你表達能力有問題)？
如果不能，即使是原題又如何呢？沒有任何意義。如果能，那麼恭喜你，offer在向你招手。博主當時在十分鐘內給出了沒有bug的代碼，所以也順利通過面試了。言歸正傳，這兩道演算法題如下：
1
第一道是劍指offer上的原題，基本沒有演算法，更多是代碼細節處理和代碼功底的考察。第一道題目是順時針列印矩陣，具體要求如下：
假設有一個如下的4*4矩陣：
你只需要順時針列印這個矩陣，上面輸入對應的輸出順序是：
【1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10】
你可以認為函數的輸入是一個二維數組（表示矩陣），返回值是矩陣的列印順序集合。
題目應該不難，基本沒有演算法。看到完題目的小夥伴，停下來動手試試，即使你以前做過這道題，可以試試看：十分鐘內能否A4紙手撕出代碼，並且保證正確率？切記，僅僅在腦海里想遠遠不夠，動手寫寫看。在動手寫代碼前一定要整理好思路，沒有打通思路動手也是白搭，大概率是浪費時間，代碼只是思路的一種體現，思路很重要，編程語言倒是其次。
往下看之前先想想，我們需要些什麼條件來實現順時針列印。往下看之前建議停下來想想，解決這個問題你需要什麼條件？只要可以滿足所有你需要的條件：問題就迎刃而解了，代碼也就呼之欲出了。
2
順時針列印肯定得知道當前列印到哪一行和哪一列了；其次不能出現越界和重複列印。
第一點很好實現，定義兩個變數row和col指向當前列印的行和列即可；第二點，順時針列印其實是一圈一圈的列印，列印過程中的任何一次順時針列印圈都可以用四個變數唯一確定：當前圈的最一行和最後一行；當前圈的最左列和最右一列。越界問題其實也就是要限定row和col變數的取值範圍。
下面用top表示當前列印圈的第一行、left表示當前圈最左列、bottom表示當前列印圈的最後一行、right表示當前列印圈的最右邊一列。這四個變數中top和bottom是用來限定row的取值範圍；left和right是用來限定col的取值範圍。
到這裡代碼思路大致介紹完了，讀者可以停下來，自己動手碼一下代碼，面試中很注重手撕代碼的能力，僅僅有思路寫不出實現代碼也是不行，所以強烈建議拿出A4紙或者【沒有提示功能的編輯器】動手撕一波代碼。
3
具體而言，上面案例列印輸出的第一圈輸出應該是：
【1,2,3,4,8,12,16,15,14,13,9,5】
這個圈可以用
top=0；bottom=3；left=0；right=3
來唯一確定；
列印的第二圈的輸出為：
【6,7,11,10】
這個圈可以用：
top=1；bottom=2；left=1；right=2
來唯一確定。
對列印邊界的限定可以避免出現數據的重複處理，即之前已經列印輸出過的數據再次被輸出；也可以防止數組越界異常。當出現：top>bottom或者left>right則表明所有的數據都已經處理完了。java代碼如下
public ArrayList printMatrix (int [][] matrix) {
if(matrix==null) return null;
//獲取矩陣的行和列
int row = matrix.length;
int col = matrix[0].length;
//保存待返回的結果集
ArrayList<Integer> res
= new ArrayList(row*col);
int top=0,left=0；
int bottom=row-1,right=col-1;
while( left<=right
&& top<=bottom ){
//列印left->right, left<=right
for(int m=left;m<=right;m++){
res.add(matrix[top][m]);
}
//列印top->bottom top<=bottom
for(int m=top+1;m<=bottom;m++){
res.add(matrix[m][right]);
}
//列印right->left
//只剩一行時left->right和right->left
//列印的是同一行，所以沒有重複必要處理
if( top!=bottom )
for(int m=right-1;m>=left;m--){
res.add(matrix[bottom][m]);
}
//列印bottom->top
//只剩一列時top->bottom和bottom->top
//列印的是同一行，所以沒有重複必要處理
if(right != left)
for(int m=bottom-1;m>top;m--){
res.add(matrix[m][left]);
}
//為列印下一圈做準備
top++;
left++;
bottom--;
right--;
}
return res;
}
這裡再次強調一點：不要刻意去強調原題之類的，也不要覺得是原題就眼高手低。你唯一應該關注的是【你能不能手撕出代碼、正確率又是多少】，面試的時候碰到一個原題卻寫不出代碼或者正確率達不到，這真的很扎心，到時一定恨不得給自己兩巴掌。另外，刷題一定要總結！博主也會儘力為大家總結一些常見題型的解法，博主的每篇文章不會為了發文章而發文章，文章最後都會有解題方法總結。
4
總結：數組、矩陣類的題大多思路是：
- 使用邊界指針，通過某種方式移動邊界指針（每次移動一步或者二分法移動）
- 貪心暴力演算法：通過遞歸的方式遍歷所有可能的解法，選出滿足條件的組合
- 動態規劃：當前的狀態要和之前的狀態有關，以空間換時間
- HashMap<元素值，數組索引>或HashSet去重特性，這兩個數據結構用的很多
- 快慢指針法
數組要盡量利用有序、不重複之類的條件，任何有序字眼都要想想能不能用二分法，二分是log級別的複雜度，如果能用，基本就是最優解了。不能用二分然後試試上面其他幾類方法。猿輔導一面的第二道演算法題也是和數組有關。
5
第二道面試題，題目描描述很短，如下：
給你兩個有序的數組，要求：找出這兩個數組合併之後的中位數。要求：最小時間和空間複雜度。
這個題在線性時間複雜度O(n)很好解：維護兩個指針找出第k大的數，這裡的k就是：數組合併後的中位數位置。但是這不是最優解，你回答完O(n)的思路後，面試官肯定會問你也沒有更優的解法。
一旦面試官詢問更優解法，其實是「此地無銀三百兩」，大概率是有的，要不面試官問你就沒有意義了，這更多是一種提示。回到上面總結部分，有序數組如果可以使用【二分法】，就能達到log級別的複雜度，大概率是最優解，所以思路肯定轉到二分發上面去了。
這個題博主在面試百度的時候也曾遇到過，具體解法請看這篇文章。博主當時在五分鐘內給出了代碼實現，並使用上面那篇文章中介紹的圖解方法向面試官介紹了完整的解題思路。這道題解完，面試官說了一句話：「今天的面試就到這裡了，等待下面的二面通知。」如果這道題解得不那麼好，怕是隻能收到面試官的前半句話了。
面試題時的手撕演算法大多是牛客網和LeetCode上的原題，如果你還不知道該刷哪些演算法題，該如何準備秋招，強烈建議看這篇文章：這篇文章詳細介紹了整個秋招準備過程，學習方法。學習資料、簡歷、找面經方法等等，基本涵蓋了秋招的所有相關事情。
這兩道演算法題你花了多長時間手撕代碼呢？歡迎評論區留言分享討論~
資料分享：
java學習筆記、10T資料、100多個java實戰項目分享
歡迎關注個人公眾號【菜鳥名企夢】，公眾號專註：互聯網求職面經、java、python、爬蟲、大數據等技術、海量資料分享：
公眾號菜鳥名企夢後臺發送「csdn文庫下載」即可免費領取【csdn】和【百度文庫】下載服務；公眾號菜鳥名企夢後臺發送「資料」:即可領取5T精品學習資料、java面試考點和java面經總結，以及幾十個java和大數據項目，資料很全，你想找的幾乎都有推薦閱讀
我的【奇葩經歷】分享
推薦閱讀：
