演算法為編程語言的基礎
技術面試中，面試官一般會先就你所應聘的崗位進行相關知識的考察，也叫基礎知識和業務邏輯面試，只要你回答的不是特別特別差，面試官通常會說：“咱們寫個代碼吧”，這個時候就開始了演算法面試，也就是說，一輪技術面試=基礎知識和業務邏輯面試+演算法面試，
一次位元組跳動面試的感慨
前段時間，我曾面試位元組跳動，面試官的一道演算法題算是把我給難住了，給大家還原當時的面試場景如下：
面試官：給定單鏈表的頭結點 head，實作一個調整鏈表的函式，從鏈表尾部開始，以 K 個結點為一組進行逆序翻轉，頭部剩余結點不足一組時，不需要翻轉，（不能使用佇列或者堆疊作為輔助）
但是這個演算法題困擾了我很久，一直苦苦得不出答案，最后還是在面試官的提醒下才知曉正確的答案，
正確答案如下：
我們先定義一個 reverseKGroupPlus() 方法
public ListNode reverseKGroupPlus(ListNode head, int k) {
if (head == null || k <= 1) return head;
// 計算原始鏈表長度
int length = linkedLength(head);
if (length < k)
return head;
// 計算 offset
int offsetIndex = length % k;
// 原始鏈表正好可以由 K 分位 N 組，可直接處理
if (offsetIndex == 0) {
return reverseKGroup(head, k);
}
// 定義并找到 prev 和 offset
ListNode prev = head, offset = head;
while (offsetIndex > 0) {
prev = offset;
offset = offset.next;
offsetIndex--;
}
// 將 offset 結點子鏈表進行翻轉，再拼接回主鏈表
prev.next = reverseKGroup(offset, k);
return head;
}注意當鏈表長度正好可以用 K 分位 N 組時，我們直接處理，否者才需要后續復雜的邏輯，
代碼的注釋足夠清晰了，在腦子里過一遍代碼的執行流程應該能明白，為了幫助大家理解，我又畫了個示意圖，
假設以 head 為頭結點的鏈表長度是 10，K 為 4，那么計算下來 offset Index 就是 2，
找到 prev 和 offset 結點后，就可以將以 offset 結點為頭結點的子鏈表，進行 K 個一組翻轉鏈表的操作了，
此時，head 結點位起始的鏈表，就是我們計算后的結果，
面試官當時跟我交談3個小時，說演算法其實不算難，而且演算法是程式編程的基礎之一是一定要掌握的，給我推薦了一本演算法筆記，筆記領取方式：關注、轉發后私信小編【演算法】即可領取
筆記一共分為7個小節，詳細敘述了演算法的厲害之處，
- 排序和查找演算法
- 查找演算法
- 二叉樹
- 佇列和堆疊
- 字串
- 陣列
- 其它演算法
排序演算法
- 希爾排序
- 原地歸并的抽象方法
- 自頂向下的歸并排序
- 自底向上的歸并排序
- API
- 堆的演算法
- 堆排序
查找演算法
- 無序鏈表中的順序查找
- 有序陣列中的二分查找
- 二分查找的分析
- 二叉查找樹的基本實作
- 平衡查找樹的基本實作
- 紅黑樹的性質
- 散列函式
二叉樹
- 二叉樹中序遍歷
- 二叉樹的序列化和反序列化
- 子樹
- 最近公共祖先
- 二叉樹的層次遍歷
- 將二叉樹拆成鏈表
- 在二叉查找樹中插入節點
佇列和堆疊
- 帶最小值操作的堆疊
- 用堆疊實作佇列
- 有效的括號序列
- 簡化路徑
字串
- 羅馬數字轉整數
- 回文數
- 亂序字串
- 有效回文串
- 翻轉字串
- 最長無重復字符的子串
- 字串壓縮
- 比較字串
- 編輯距離1I
陣列
其它演算法
文末筆記領取方式
筆記領取方式：點贊+關注，加助理VX：mxx2020666，即可免費領取
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/173325.html
標籤：java