聊一聊前端算法面試(遞歸)
我要評論寫在前面
今天來聊一聊前端面試中出現(xiàn)頻率非常高的一種算法思想——「遞歸」。
先看下幾個常見的面試題：
- 假如樓梯有n個臺階，每次可以走1個或2個臺階，請問走完這n個臺階有幾種走法❓
- 如何用遞歸思想實現(xiàn)深拷貝❓
- 如何用遞歸思想實現(xiàn)數(shù)組的扁平化❓
你可以先思考一下如何回答上邊的問題🤔，然后帶著答案來閱覽接下來的內(nèi)容。
如何編寫遞歸代碼❓
遞歸思想在前端面試中非常常見，除了上面的一些題目之外，二叉樹的前中后序遍歷，斐波那契數(shù)列等都用到了遞歸的思想。簡單地理解遞歸就是：自己調(diào)用自己。那如何編寫遞歸的代碼呢❓ 在筆者看來：
主要有兩個關(guān)鍵步驟：
- 寫出遞歸公式
- 找到終止條件
先來看個簡單的例子：如何求1+2+3+4+...+n的和？相信用for循環(huán)的方法大家都知道如何編寫：
function sum(n) {
var total = 0
for (int i = 1; i <= n; i++) {
total = total + i
}
return total
}
那如何改為遞歸的寫法呢？
第一步： 寫出遞歸公式
細心觀察就會發(fā)現(xiàn)，其實就是n與n-1和n-2的關(guān)系
sum(n) = sum(n-1) + n ··· ··· ··· sum(100) = sum(99) + 100 sum(99) = sum(98) + 99 ··· ··· ··· sum(5) = sum(4) + 5 sum(4) = sum(3) + 4 sum(3) = sum(2) + 3 sum(2) = sum(1) + 2 sum(1) = 1
將如上轉(zhuǎn)化成遞歸公式就是
function sum(n) {
return sum(n-1) + n
}
第二步：找出終止條件
遞歸公式寫出來了，那么遞歸代碼就完成了一大半。現(xiàn)在來看一下上述問題的終止條件是什么呢，即sum（1）= 1；
結(jié)合遞歸公式和終止條件，1+2+3+4+...+n求和的遞歸代碼如下:
function sum(n) {
if( n ===1 ) return 1
return sum(n-1) + n
}
面試題1： 樓梯問題
假如樓梯有n個臺階，每次可以走1個或2個臺階，請問走完這n個臺階有幾種走法❓
按照我們上面的思路，先寫出遞歸公式。那這道題我們?nèi)绾稳フ页鲞f歸公式呢。假設(shè)有3個臺階，我們可以有3種走法：
1 1 1
1 2
2 1
第一種是每次都是走1個臺階。第二種是第一步走1個臺階，第二步走2個臺階。第三種是第一步走2個臺階，第二步走1個臺階。
寫出遞歸公式：
那如果有n個臺階呢？我們認(rèn)真思考下就會發(fā)現(xiàn)，第1步的走法有兩類：第一種是第一步走1個臺階，第二種是第二步走2個臺階。所以n個臺階的走法就可以分為：走完1個臺階后的n-1種走法，加上走完2個臺階后的n-2種走法，用遞歸公式表示就是:
function climbStairs(n) {
return climbStairs(n - 1) + climbStairs(n - 2)
}
找到終止條件：
climbStairs(n) = climbStairs(n-1) + climbStairs(n-2) climbStairs(n-1) = climbStairs(n-2) + climbStairs(n-3) ··· ··· ··· climbStairs(5) = climbStairs(4) + climbStairs(3) climbStairs(4) = climbStairs(3) + climbStairs(2) climbStairs(3) = climbStairs(2) + climbStairs(1) climbStairs(2) = 2 climbStairs(1) = 1
從上面的推導(dǎo)可以看出：終止條件為：
climbStairs(2) = 2 climbStairs(1) = 1
綜上所述，解決爬樓梯的代碼如下：
function climbStairs(n) {
if (n == 1) return 1
if (n == 2) return 2
return climbStairs(n-1) + climbStairs(n-2)
}
當(dāng)然，可以對上述題目做一個memorize操作，性能會好很多：
var calculated = []
function climbStairs(n) {
if(n == 1) {
return 1
}else if (n == 2) {
return 2
}else {
if(!calculated[n-1]){
calculated[n-1] = climbStairs(n-1)
}
if(!calculated[n-2]){
calculated[n-2] = climbStairs(n-2)
}
return calculated[n-1] + calculated[n-2]
}
}
解決完爬樓梯問題之后，思考下斐波那契數(shù)列問題的求解，有木有發(fā)現(xiàn)是一樣的問題和思路：）
面試題2：實現(xiàn)深拷貝
如何用遞歸思想實現(xiàn)深拷貝❓如果要實現(xiàn)深拷貝那么就需要考慮將對象的屬性, 與屬性的屬性,都拷貝過來, 這種情況下就非常適合使用遞歸思想來解決，在拷貝的適合判斷屬性值的類型，如果是對象則遞歸調(diào)用deeplClone函數(shù)，否則直接返回該屬性值：
var deepCopy = function(obj) {
if (typeof obj !== 'object') return;
// // 根據(jù)obj的類型判斷是新建一個數(shù)組還是對象
var newObj = obj instanceof Array ? [] : {};
for (var key in obj) {
if (obj.hasOwnProperty(key)) {
newObj[key] = typeof obj[key] === 'object' ? deepCopy(obj[key]) : obj[key];
}
}
return newObj;
}
面試題3：如何把數(shù)組拍平
如何用遞歸思想實現(xiàn)數(shù)組的扁平化❓即如何把[1, [2], [3, [4, [5]]]]拍平得到[1,2,3,4,5]❓
const flatten = (arr) => {
let result = [];
arr.forEach((item, i, arr) => {
// 若為數(shù)組,遞歸調(diào)用 faltten,并將結(jié)果與result合并
if (Array.isArray(item)) {
result = result.concat(flatten(item));
} else {
result.push(arr[i])
}
})
return result;
};
const arr = [1, [2, [3, 4, 5]]];
console.log(flatten(arr)); // [1, 2, 3, 4, 5]
總結(jié)
編寫遞歸代碼的關(guān)鍵在于找出遞歸公式和終止條件，最后將它們翻譯成代碼。遞歸代碼雖然比較簡潔。但是也有很多弊端，如性能不是很高效，這時候要做memorize等一些操作來優(yōu)化性能。容易產(chǎn)生堆棧溢出等問題，所以我們在寫代碼的時候要注意這些。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
- 這篇文章主要介紹了百度面試算法題目與參考答案,總結(jié)分析了位圖、排序、鏈表、二叉樹等操作的原理與相關(guān)實現(xiàn)技巧,需要的朋友可以參考下2019-09-06
- 這篇文章主要介紹了華為筆試算法面試題與參考答案,結(jié)合實例形式分析了基于C++的字符串轉(zhuǎn)換、判斷、排序等算法相關(guān)操作技巧,需要的朋友可以參考下2019-09-05