東莞易思訓(xùn)教育

7x24小時(shí)咨詢熱線

400-660-3310

當(dāng)前位置 : 好學(xué)校 東莞易思訓(xùn)教育 學(xué)習(xí)資訊 資訊詳情

前端面試題匯總之算法和應(yīng)用

2021-08-06

前端面試題匯總之算法和應(yīng)用。正在從事Web前端工作和想要換工作的小伙伴們來看一看吧。

前端面試題匯總之算法和應(yīng)用

3.1隨機(jī)洗牌算法

題目:隨機(jī)打亂數(shù)組里的元素,元素不能在原來的位置

letarr1=[1,2,3,4,5,6,7,8,9,10]

functionshuffle(array){

for(leti=array.length-1;i>=0;i--){

letrandomIndex=Math.floor(Math.random()*(i+1));[array[i],

array[randomIndex]]=[array[randomIndex],array[i]]}

returnarray;}

shuffle(arr1)

Fisher–Yatesshuffle洗牌算法:從后往前遍歷,取當(dāng)前的數(shù)和前面的一個(gè)隨機(jī)下標(biāo)的數(shù)交換位置。

3.2兩個(gè)雞蛋與100層樓

題目:兩個(gè)軟硬程度一樣但未知的雞蛋,它們有可能都在一樓就摔碎,也可能從一百層樓摔下來沒事。有座100層的建筑,要你用這兩個(gè)雞蛋確定哪一層是雞蛋可以安全落下的最 高位置??梢运に閮蓚€(gè)雞蛋。在有限層數(shù)和蛋數(shù)的情況下,求即使最壞情況下需要的最少判斷次數(shù)。

這是一道動(dòng)態(tài)規(guī)劃的題目,首先假設(shè)f[n][m]表示從m層樓扔n個(gè)雞蛋,找到的安全位置的最少判斷次數(shù)。如果第 一個(gè)雞蛋第 一次從[1,i]中任選第j層扔下,如果碎了,就必須從[1,j-1]挨著試,也就是dp[1][j-1];如果不碎的話,那么還要在[j,i]層繼續(xù)扔,即dp[2][i-j]。最壞情況下則取max(dp[1][j-1],dp[2][i-j])次。

根據(jù)方程寫出解法:

functionegg(floor){

//dp[1][i]=i,dp[2][i]=i最差的情況預(yù)處理數(shù)據(jù)

letdp=Array.from(newArray(3),

()=>Array.from({length:floor+1},(v,k)=>k))

for(leti=1;i<=floor;i++){

for(letj=1;j

dp[2][i]=Math.min(dp[2][i],1+Math.max(dp[1][j-1],dp[2][i-j]));

}}

returndp[2][floor]}

如果給的是n個(gè)雞蛋,用下面的解法:

functionfloorEgg(egg,floor){

if(egg<1||floor<1)

return0//初始化數(shù)組,值為最壞的次數(shù)

letdp=Array.from(newArray(egg+1).keys(),x=>Array.from({length:floor+1},(v,k)=>x&&k))

//構(gòu)建dp數(shù)組for(leti=2;i<=egg;i++){

for(letj=1;j<=floor;j++){

for(letk=1;k

dp[i][j]=Math.min(dp[i][j],1+Math.max(dp[i-1][k-1],dp[i][j-k]));

}

}}

returndp[egg][floor]}

收藏
分享到:

相關(guān)課程

相關(guān)資訊

東莞易思訓(xùn)教育

東莞易思訓(xùn)教育

認(rèn)證等級(jí)

信譽(yù)良好,可安心報(bào)讀

東莞易思訓(xùn)教育

已獲好學(xué)校V2信譽(yù)等級(jí)認(rèn)證

信譽(yù)值

  • (60-80)基礎(chǔ)信譽(yù)積累,可放心報(bào)讀
  • (81-90)良好信譽(yù)積累,可持續(xù)信賴
  • (91-100)充分信譽(yù)積累,推薦報(bào)讀

與好學(xué)校簽訂讀書保障協(xié)議:

  • 100%
  • 37
  • 1903
在線咨詢
;