亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

聊一聊前端算法面試(遞歸)

  發(fā)布時(shí)間:2019-09-25 16:31:16   作者:慕晨同學(xué)   我要評(píng)論
這篇文章主要介紹了聊一聊前端算法面試(遞歸),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

寫在前面

今天來(lái)聊一聊前端面試中出現(xiàn)頻率非常高的一種算法思想——「遞歸」。

先看下幾個(gè)常見(jiàn)的面試題:

  1. 假如樓梯有n個(gè)臺(tái)階,每次可以走1個(gè)或2個(gè)臺(tái)階,請(qǐng)問(wèn)走完這n個(gè)臺(tái)階有幾種走法❓
  2. 如何用遞歸思想實(shí)現(xiàn)深拷貝❓
  3. 如何用遞歸思想實(shí)現(xiàn)數(shù)組的扁平化❓

你可以先思考一下如何回答上邊的問(wèn)題🤔,然后帶著答案來(lái)閱覽接下來(lái)的內(nèi)容。

如何編寫遞歸代碼❓

遞歸思想在前端面試中非常常見(jiàn),除了上面的一些題目之外,二叉樹的前中后序遍歷,斐波那契數(shù)列等都用到了遞歸的思想。簡(jiǎn)單地理解遞歸就是:自己調(diào)用自己。那如何編寫遞歸的代碼呢❓ 在筆者看來(lái):

主要有兩個(gè)關(guān)鍵步驟:

  • 寫出遞歸公式
  • 找到終止條件

先來(lái)看個(gè)簡(jiǎ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
}

那如何改為遞歸的寫法呢?

第一步: 寫出遞歸公式

細(xì)心觀察就會(huì)發(fā)現(xiàn),其實(shí)就是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
}

第二步:找出終止條件

遞歸公式寫出來(lái)了,那么遞歸代碼就完成了一大半?,F(xiàn)在來(lái)看一下上述問(wèn)題的終止條件是什么呢,即sum(1)= 1;

結(jié)合遞歸公式和終止條件,1+2+3+4+...+n求和的遞歸代碼如下:

function sum(n) {
    if( n ===1 ) return 1
    return sum(n-1) + n
}

面試題1: 樓梯問(wèn)題

假如樓梯有n個(gè)臺(tái)階,每次可以走1個(gè)或2個(gè)臺(tái)階,請(qǐng)問(wèn)走完這n個(gè)臺(tái)階有幾種走法❓

按照我們上面的思路,先寫出遞歸公式。那這道題我們?nèi)绾稳フ页鲞f歸公式呢。假設(shè)有3個(gè)臺(tái)階,我們可以有3種走法:

1 1 1
1 2
2 1

第一種是每次都是走1個(gè)臺(tái)階。第二種是第一步走1個(gè)臺(tái)階,第二步走2個(gè)臺(tái)階。第三種是第一步走2個(gè)臺(tái)階,第二步走1個(gè)臺(tái)階。

寫出遞歸公式:

那如果有n個(gè)臺(tái)階呢?我們認(rèn)真思考下就會(huì)發(fā)現(xiàn),第1步的走法有兩類:第一種是第一步走1個(gè)臺(tái)階,第二種是第二步走2個(gè)臺(tái)階。所以n個(gè)臺(tái)階的走法就可以分為:走完1個(gè)臺(tái)階后的n-1種走法,加上走完2個(gè)臺(tái)階后的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)然,可以對(duì)上述題目做一個(gè)memorize操作,性能會(huì)好很多:

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]
    }

}

解決完爬樓梯問(wèn)題之后,思考下斐波那契數(shù)列問(wèn)題的求解,有木有發(fā)現(xiàn)是一樣的問(wèn)題和思路:)

面試題2:實(shí)現(xiàn)深拷貝

如何用遞歸思想實(shí)現(xiàn)深拷貝❓如果要實(shí)現(xiàn)深拷貝那么就需要考慮將對(duì)象的屬性, 與屬性的屬性,都拷貝過(guò)來(lái), 這種情況下就非常適合使用遞歸思想來(lái)解決,在拷貝的適合判斷屬性值的類型,如果是對(duì)象則遞歸調(diào)用deeplClone函數(shù),否則直接返回該屬性值:

var deepCopy = function(obj) {
    if (typeof obj !== 'object') return;
    // // 根據(jù)obj的類型判斷是新建一個(gè)數(shù)組還是對(duì)象
    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ù)組拍平

如何用遞歸思想實(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)鍵在于找出遞歸公式和終止條件,最后將它們翻譯成代碼。遞歸代碼雖然比較簡(jiǎn)潔。但是也有很多弊端,如性能不是很高效,這時(shí)候要做memorize等一些操作來(lái)優(yōu)化性能。容易產(chǎn)生堆棧溢出等問(wèn)題,所以我們?cè)趯懘a的時(shí)候要注意這些。

以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

  • 百度面試算法題目與參考答案總結(jié)

    這篇文章主要介紹了百度面試算法題目與參考答案,總結(jié)分析了位圖、排序、鏈表、二叉樹等操作的原理與相關(guān)實(shí)現(xiàn)技巧,需要的朋友可以參考下
    2019-09-06
  • 華為筆試算法面試題與參考答案分析【基于C++】

    這篇文章主要介紹了華為筆試算法面試題與參考答案,結(jié)合實(shí)例形式分析了基于C++的字符串轉(zhuǎn)換、判斷、排序等算法相關(guān)操作技巧,需要的朋友可以參考下
    2019-09-05

最新評(píng)論