前端面试题汇总之算法和应用

前端面试题汇总之算法和应用。正在从事Web前端工作和想要换工作的小伙伴们来看一看吧。

3.1随机洗牌算法

题目：随机打乱数组里的元素，元素不能在原来的位置

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洗牌算法：从后往前遍历，取当前的数和前面的一个随机下标的数交换位置。

3.2两个鸡蛋与100层楼

题目：两个软硬程度一样但未知的鸡蛋，它们有可能都在一楼就摔碎，也可能从一百层楼摔下来没事。有座100层的建筑，要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最 高位置。可以摔碎两个鸡蛋。在有限层数和蛋数的情况下，求即使最坏情况下需要的最少判断次数。

这是一道动态规划的题目，首先假设f[n][m]表示从m层楼扔n个鸡蛋，找到的安全位置的最少判断次数。如果第 一个鸡蛋第 一次从[1,i]中任选第j层扔下，如果碎了，就必须从[1,j-1]挨着试,也就是dp[1][j-1];如果不碎的话，那么还要在[j,i]层继续扔，即dp[2][i-j]。最坏情况下则取max(dp[1][j-1],dp[2][i-j])次。

根据方程写出解法：

functionegg(floor){

//dp[1][i]=i,dp[2][i]=i最差的情况预处理数据

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//初始化数组，值为最坏的次数

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

//构建dp数组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]}