前端面試題匯總之算法和應用

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

3.1隨機洗牌算法

題目：隨機打亂數(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洗牌算法：從后往前遍歷，取當前的數(shù)和前面的一個隨機下標的數(shù)交換位置。

3.2兩個雞蛋與100層樓

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

這是一道動態(tài)規(guī)劃的題目，首先假設f[n][m]表示從m層樓扔n個雞蛋，找到的安全位置的最少判斷次數(shù)。如果第 一個雞蛋第 一次從[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最差的情況預處理數(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個雞蛋，用下面的解法：

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))

//構建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]}