一篇帶給你Web前端算法面試題
時間復雜度分析
當問題規模數據大量增加時，重復執行的次數也必定會增加，那么我們就有必要關心執行次數是以什么樣的數量級增加，這也是分析時間復雜度的意義，是一個非常重要衡量算法好快的事前估算的方法
常見的時間復雜度：
- O(1)：常數階的復雜度，這種復雜度無論數據規模如何增長，計算時間是不變的。
const increment = n => n++
- O(n)：線性復雜度，線性增長。
// 最典型的例子就是線性查找
const linearSearch = (arr,target) = {
for (let i = 0;i<arr.length;i++){
if(arr[i] === target) return 1;
}
return -1;
}
- O(logn)：對數復雜度，隨著問題規模的增長，計算時間會對數級增長，典型的例子是歸并查找。
- O(nlogn)：線性對數復雜度，計算時間隨數據規模呈線性對數級增長，典型的例子是歸并排序。
- O(n^2)：平方級復雜度，典型就是雙層循環的時候，代表應用是冒泡排序算法。
常見的排序算法
常見的排序算法這里總結四種最具代表性的：
冒泡排序
冒泡排序是一種簡單的排序算法，它需要重復的走訪序列，一次只比較兩個數據，如果順序錯誤則交換這兩個數據，直到沒有在需要交換的數據，走訪結束，具體算法描述如下：
比較相鄰元素，如果第一個比第二個大，就交換他們兩個依次走訪執行第一步，那么第一趟后，最后的元素應該是最大的數重復走訪，直到排序完成。
const bubbleSort = arr => {
console.time('bubbleSort耗時');
let len = arr.length;
for(let i = 0;i<len;i++){
for(let j = 0;j<len-i-1;j++){
if(arr[j]>arr[j+1]){
[arr[j],arr[j+1]] = [arr[j+1],arr[j]]
}
}
}
console.timeEnd('bubbleSort耗時');
return arr
}
冒泡排序改進方案：
方案一：設置一個標記變量pos，用來記錄每次走訪的最后一次進行交換的位置，那么下次走訪之后的序列便可以不再訪問。
const bubbleSort_pos = arr => {
console.time('bubbleSort_pos耗時')
let i = arr.length - 1;
while(i > 0){
let pos = 0;
for(var j=0;j<i;j++){
if(arr[j]>arr[j+1]){
pos = j;
[arr[j],arr[j+1]] = [arr[j+1],arr[j]];
}
}
i = pos;
}
console.timeEnd('bubbleSort_pos耗時')
return arr;
}
方案二：傳統冒泡一趟只能找到一個最大或者最小值，我們可以考慮在利用每趟排序過程中進行正向和反向冒泡，一次可以得到一個最大值和最小值，從而使排序趟數幾乎減少一半。
const bubbleSort_ovonic = arr => {
console.time('bubbleSort_ovonic耗時')
let low = 0;
let height = arr.length -1;
let tmp,j;
while(low < height){
for(j=low;j<height;++j){ // 正向冒泡，找到最大值
if(arr[j] > arr[j+1]){
[arr[j],arr[j+1]] = [arr[j+1],arr[j]];
}
}
--height;
for(j=height;j>low;--j){ // 反向冒泡，找到最小值
if(arr[j] < arr[j-1]){
[arr[j-1],arr[j]] = [arr[j],arr[j-1]]
}
}
++low;
}
console.timeEnd('bubbleSort_ovonic耗時')
return arr;
}
以上提供兩種改進冒泡的思路，耗時在這只是進行粗略對比，并不完全確定好壞，相比之下改進后的冒泡時間復雜度更低，下圖實例展示結果耗時更短。
快速排序
快速排序是分治策略的經典實現，也是對冒泡排序的改進，出現頻率較高，基本思路是經過一趟排序，把數據分割成獨立的兩部分，其中一部分數據要比另一部分都小，然后按此方法繼續排序，以達到整個序列有序，具體算法描述如下：
從數組中挑出一個元素作為"基準"分區：所有比基準小的值放前面，而比基準大的值放后面，基準處于數列中間位置按照此方法依次排序(遞歸)，以達到序列有序。
// 遞歸方法的其中一種形式
const quickSort = (arr) => {
if(arr.length <= 1){ return arr };
let pivotIndex = Math.floor(arr.length/2);
let pivot = arr.splice(pivotIndex,1)[0]; // 確定基準
let left = [] , right = [];
for(let i = 0;i<arr.length;i++){
if(arr[i]<pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot],quickSort(right));
}
希爾排序
第一個突破O(n^2)的排序算法;是簡單插入排序的改進版;與插入排序的不同點在于，它會優先比較距離較遠的元素。希爾排序又叫做增量縮小排序，核心在于間隔序列的設定，既可以提前設定好間隔序列，也可以動態的定義間隔序列，后者是《算法(第四版)》中提出的，實現如下：
選擇一個增量序列t1,t2...tk，其中ti>tj，tk=1按增量序列個數k，對序列進行k趟排序每趟排序根據對應的增量ti，將待排序列分割成長度為m的若干子序列，然后分別對各子表進行直接插入排序。僅當增量因子為1時，整個序列作為一個表來處理，表長度即為整個序列的長度。
const shellSort = arr => {
console.time('shellSort耗時')
let len = arr.length,
gap = 1,
temp;
while(gap < len/5){ gap = gap*5+1 } // 動態定義間隔序列
for(gap; gap > 0; gap = Math.floor(gap/5)){
for(let i = gap;i<len;i++){
temp = arr[i];
for(var j=i-gap; j>=0&&arr[j]>temp; j-=gap){
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
console.timeEnd('shellSort耗時');
return arr;
}
歸并排序
歸并排序不受輸入數據的影響，時間復雜度始終都是O(nlogn)，但代價是需要額外的內存空間。歸并排序也是分治法的經典體現，先使子序列有序，再使子序列段間有序，若將兩個有序表合并成一個有序表，稱為2-路歸并。實現如下：
將長度為n的序列，分成兩個長度為n/2的子序列對這兩個子序列分別采用歸并排序將兩個排序好的子序列合并成最終排序序列。
const merge = (left,right) => {
let result = [];
while(left.length && right.length){
if(left[0] <= right[0]){
result.push(left.shift());
}else{
result.push(right.shift());
}
}
while(left.length)
result.push(left.shift());
while(right.length)
result.push(right.shift());
return result;
}
const mergeSort = arr => {
let len = arr.length;
if(len < 2) return arr;
let middle = Math.floor(len / 2),
left = arr.slice(0,middle),
right = arr.slice(middle);
return merge(mergeSort(left),mergeSort(right));
}
常見的查找算法
線性查找
線性查找較簡單，只需要簡單遍歷即可。
const linearSearch = (arr,target) => {
for(let i =0;i<arr.length;i++){
if(arr[i] === target) return i
}
return -1
}
時間復雜度：最佳情況O(n)，最差情況O(n)，平均情況O(n)
二分查找法
也叫作折半查找，要求查找表的數據實現線性結構存儲，還要求查找表中的順序是有序的
實現思路如下：
首先設兩個指針，low表示最低索引，height表示最高索引然后取中間位置索引，判斷middle處的值是否是要查找的數字，是則查找結束;比所求值較小就把low設為middle+1，較大則把height設為middle-1然后到新分區繼續查找，直到找到或者low>height找不到要查找的值結束。
const binarySearch = (arr,target) => {
let height = arr.length - 1;
let low = 0;
while(low <= height){
let middle = Math.floor((low+height)/2)
if(target < arr[middle]){
height = middle - 1
}else if(target > arr[middle]){
low = middle + 1
}else{
return middle
}
}
return -1
}
時間復雜度分析：最佳情況O(logn)，最差情況O(logn)，平均情況O(logn)。
參考：damonare。
二叉樹的遍歷方式
二叉樹遍歷有四種方式：先序遍歷，中序遍歷，后序遍歷，層序遍歷。
前序遍歷：先訪問根節點，然后前序遍歷左子樹，再前序遍歷右子樹。
中序遍歷：先中序遍歷左子樹，然后訪問根節點，最后遍歷右子樹。
后序遍歷：從左到右，先葉子后結點的方式遍歷訪問左子樹，最后訪問根節點。
層序遍歷：從根結點從上往下逐層遍歷，在同一層，按從左到右的順序對結點逐個訪問。
實現二叉樹的層序遍歷
有兩種通用的遍歷樹的策略：
深度優先遍歷(DFC)
正如名字一樣，深度優先遍歷采用深度作為優先級，從某個確定的葉子，然后再返回根到另個分支，有細分為先序遍歷，中序遍歷和后序遍歷
廣度優先遍歷(BFC)
廣度優先按照高度順序一層一層訪問整棵樹，高層次的結點會比低層的結點先訪問到
// 通過迭代方式實現
const levelOrder = function(root) {
const res = [];
const stack = [{ index: 0, node: root }];
while (stack.length > 0) {
const { index, node } = stack.pop();
if (!node) continue;
res[index] = res[index] ? [...res[index], node.val] : [node.val];
stack.push({ index: index + 1, node: node.right });
stack.push({ index: index + 1, node: node.left });
}
return res;
};
