前幾天博主剛去面試位元組跳動，面試官問了一些演算法題。已經記錄下來整理成文件了。去面試之前就聽說位元組跳動面試非常喜歡考演算法題，基本每輪技術面都會有演算法題，而且很難。
即將要去大廠面試的小夥伴可以採納一波。
位元組跳動演算法題
連結串列
面試題：反轉單向連結串列
題目需要將一個單向連結串列反轉。思路很簡單，使用三個變數；分別表示當前節點和當前節點的前後節點，雖然這題很簡單，但是卻是一道常考題
以下是實現該演算法的程式碼
var reverseList = function（head） { // 判斷下變數邊界問題 if （！head || ！head。next） return head // 初始設定為空，因為第一個節點反轉後就是尾部，尾部節點指向 null let pre = null let current = head let next // 判斷當前節點是否為空 // 不為空就先獲取當前節點的下一節點 // 然後把當前節點的 next 設為上一個節點 // 然後把 current 設為下一個節點，pre 設為當前節點 while（current） { next = current。next current。next = pre pre = current current = next } return pre }；
二叉樹遍歷
原理： 遞迴
function traversal（node，tempOrderTraversal） { if （node ！= null） { // tempOrderTraversal。push（node。value） 前序遍歷 if （node。left ！= null） { preOrderTraversal（node。left，tempOrderTraversal） } // tempOrderTraversal。push（node。value） 中序遍歷 if （node。right ！= null） { preOrderTraversal（node。right，tempOrderTraversal） } // tempOrderTraversal。push（node。value） 後序遍歷 } }
不能使用遞迴時，則使用棧就是JS的陣列push、pop
// 非遞迴遍歷 var kthSmallest = function（root， k） { const tempArr = ［］； let result； tempArr。push（root）； while （tempArr。length > 0） { result = tempArr。pop（）； if （result。value == k） break； if （result。left ！= null） tempArr。push（result。left）； if （result。right ！= null） tempArr。push（result。right）； } return result； }；
點選免費領取前端最新面試資料
按位操作
1）按位與
每一位都為 1，結果才為 1
8 & 7 // -> 0 // 1000 & 0111 -> 0000 -> 0
2）按位或
其中一位為 1，結果就是 1
8 | 7 // -> 15 // 1000 | 0111 -> 1111 -> 15
3）按位異或
每一位都不同，結果才為 1
8 ^ 7 // -> 15 8 ^ 8 // -> 0 // 1000 ^ 0111 -> 1111 -> 15 // 1000 ^ 1000 -> 0000 -> 0
從以上程式碼中可以發現按位異或就是不進位加法
面試題：兩個數不使用四則運算得出和
這道題中可以按位異或，因為按位異或就是不進位加法， 8 ^ 8 = 0 如果進位了，就是 16 了，所以我們只需要將兩個數進行異或操作，然後進位。那麼也就是說兩個二進位制都是 1 的位置，左邊應該有一個進位 1，所以可以得出以下公式 a + b = （a ^ b） + （（a & b） << 1） ，然後透過迭代的方式模擬加法
function sum（a， b） { if （a == 0） return b if （b == 0） return a let newA = a ^ b let newB = （a & b） << 1 return sum（newA， newB） }
堆排序
堆排序利用了二叉堆的特性來做，二叉堆通常用陣列表示，並且二叉堆是一顆完全二叉樹（所有葉節點（最底層的節點）都是從左往右順序排序，並且其他層的節點都是滿的）。二叉堆又分為大根堆與小根堆。
大根堆是某個節點的所有子節點的值都比他小
小根堆是某個節點的所有子節點的值都比他大
堆排序的原理就是組成一個大根堆或者小根堆。以小根堆為例，某個節點的左邊子節點索引是 i * 2 +1 ，右邊是 i * 2 + 2 ，父節點是 （i - 1） /2 。
首先遍歷陣列，判斷該節點的父節點是否比他小，如果小就交換位置並繼續判斷，直到他的父節點比他大
重新以上操作 1，直到陣列首位是最大值
然後將首位和末尾交換位置並將陣列長度減一，表示陣列末尾已是最大值，不需要再比較大小
對比左右節點哪個大，然後記住大的節點的索引並且和父節點對比大小，如果子節點大就交換位置
重複以上操作 3 - 4 直到整個陣列都是大根堆。
以下是實現該演算法的程式碼
function heap（array） { checkArray（array）； // 將最大值交換到首位 for （let i = 0； i < array。length； i++） { heapInsert（array， i）； } let size = array。length； // 交換首位和末尾 swap（array， 0， ——size）； while （size > 0） { heapify（array， 0， size）； swap（array， 0， ——size）； } return array； } function heapInsert（array， index） { // 如果當前節點比父節點大，就交換 while （array［index］ > array［parseInt（（index - 1） / 2）］） { swap（array， index， parseInt（（index - 1） / 2））； // 將索引變成父節點 index = parseInt（（index - 1） / 2）； } } function heapify（array， index， size） { let left = index * 2 + 1； while （left < size） { // 判斷左右節點大小 let largest = left + 1 < size && array［left］ < array［left + 1］ ？ left + 1 ： left； // 判斷子節點和父節點大小 largest = array［index］ < array［largest］ ？ largest ： index； if （largest === index） break； swap（array， index， largest）； index = largest； left = index * 2 + 1； } }
以上程式碼實現了小根堆，如果需要實現大根堆，只需要把節點對比反一下就好。
樹的深度
面試題：樹的最大深度
題目需要求出一顆二叉樹的最大深度
以下是實現該演算法的程式碼
var maxDepth = function（root） { if （！root） return 0 return Math。max（maxDepth（root。left）， maxDepth（root。right）） + 1 }；
對於該遞迴函式可以這樣理解：一旦沒有找到節點就會返回 0，每彈出一次遞迴函式就會加一，樹有三層就會得到3。
快速排序
快速排序的基本思想：透過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。
快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體演算法描述如下：
從數列中挑出一個元素，稱為 “基準”（pivot）；
重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分割槽退出之後，該基準就處於數列的中間位置。這個稱為分割槽（partition）操作；
遞迴地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。
以下是實現該演算法的程式碼
function quickSort（arr， left， right） { var len = arr。length， partitionIndex， left =typeof left ！=‘number’ ？ 0 ： left， right =typeof right ！=‘number’ ？ len - 1 ： right； if （left < right） { partitionIndex = partition（arr， left， right）； quickSort（arr， left， partitionIndex-1）； quickSort（arr， partitionIndex+1， right）； } return arr； } function partition（arr， left ，right） { // 分割槽操作 var pivot = left， // 設定基準值（pivot） index = pivot + 1； for （var i = index； i <= right； i++） { if （arr［i］ < arr［pivot］） { swap（arr， i， index）； index++； } } swap（arr， pivot， index - 1）； return index-1； } function swap（arr， i， j） { var temp = arr［i］； arr［i］ = arr［j］； arr［j］ = temp； }
文末免費領取前端最新面試資料
完整版資料已經為大家整理好了，希望對你們的學習有所幫助！
獲取方式：
