今晚字节的前端笔试题有人来聊聊嘛
感觉有点难啊……两个小时，这个时间是不是有点短啊……😥
我先放一下我写的……
小伙伴们，看到了来讨论一下吧
第一题
题目
如果用户A和B互动不少于3次，就认为A和B为豆油。如果A和B是豆油，B和C是豆油，那么A和C互为豆油。定义豆油瓶就是直系间接碰头组成的群体。
N*M的矩阵M，代表互动次数，如果M[i][j]=5，那么第i个和第j个用户互动过5次，为0表示没有互动。
对于i=j，同一个用户，互动次数，记成0，计算并输出所有豆油瓶的数目
比如输入
040
406
060
输出1
因为第一个和第二个用户互动超过3次，互为豆油，第二个和第三也互为豆油，所以1和3互为间接豆油，三个用户都在同一个豆油瓶里，返回1.
露珠的解法：
写的DFS。不过只通过了20%，写了我四十多分钟……结果20%，好尴尬……
//处理输入
let num=parseInt(readline());
let arr=[];//二维数组保存
for(let i=0;i<num;i++){
let temp=readline().split(' ');
arr[i]=new Array();
for(let j=0;j<temp.length;j++){
arr[i][j]=parseInt(temp[j]);
}
}
//输出
console.log(getBottleNum(arr));
//四个方向
var directions=[[1,0,-1,0],[0,1,0,-1]];
//获取豆油瓶的数目
function getBottleNum(arr){
if(!arr) return 0;//为空就没瓶
let ans=0;
let visited=[];//用来记录有没有被访问过
//处理一下visited
for(let i=0;i<arr.length;i++){
visited[i]=new Array();
for(let j=0;j<arr[0].length;j++){
visited[i][j]=false;
}
}
//执行
for(let i=0;i<arr.length;i++){
//调用一次dfs就搜索完一个区域，此时ans+1；
for(let j=0;j<arr[0].length;j++){
if(arr[i][j]<3&& visited[i][j]==false){
ans+=dfs(arr,visited,i,j);
}
}
}
return ans;
}
//DFS
function dfs(arr,visited,x,y){
if(x<0||x>=arr.length||y<0||y>=arr[0].length){return 0;}//不可以越界
let directions=[[1,0,-1,0],[0,1,0,-1]];//放外面还不能执行这啥IDE……
visited[x][y]=true;
for(let i=0;i<4;i++){
//上下左右遍历
let xx=x+directions[0][i];
let yy=y+directions[1][i];
if(xx>=0&&xx<arr.length&&yy>=0&&yy<arr[0].length&&visited[xx][yy]==false&&arr[xx][yy]<3){
visited[xx][yy]=true;
dfs(arr,visited,xx,yy);
}
}
return 1;
} 第二题
题目
原型花园有n个入口，修路，穿过花园。要求每个入口只能有一条路，所有的路都不会相交，求所有可行的方法总数。
额，就是卡特兰数
不知道哪里有问题，只通过了70%……有小伙伴AC了吗？求帮看看是哪里没有考虑到啊
//处理输入
let input=parseInt(readline());
console.log(getPathnum(input));
//C(2n，n)/n+1
function getPathnum(num){
let n=num/2;
let result=C(num,n)/(n+1);
return result%1000000007;
}
function C(x,n){
let ret=1;
for(let i=1;i<=n;i++){
ret=ret*(x-i+1)/i;
}
return ret;
} 第三题
题目
4*4数组实现 2048游戏，上下左右分开处理
合并的通用方法我也不太会写，有没有小伙伴写出来的，想看看你们的代码😥
第四题
题目
有很多糖果，每一个糖果的甜度记为a[n]，如果i和j的甜度最大公约数>1,贼糖果i和j之间有桥梁连接
比如说20 50 22 74 9 63 输出4
因为20-50-22-74两两之间有公约数2，所以有边， 9-63最大公约数是3，与其他的数公约数是1，没有边
露珠的思路
我的想法是维护一个n*n的数组，记录下这个点能获取的最大糖果数目，然后依次放
思路有了，但是我写的不对…😂我算法太菜了
下面这个肯定是错的。。。枯了
想看看大佬们的代码咋写的……会有人发嘛……想看看
//处理输入
let num=readline();
let input=readline.split(' ');
let arr=input.map((item)=>{parseInt(item);});
console.log(getCandyNum(arr));
//来不及调试了，大致思路就是这样，维护一个二维数据，记录下这个点能获取的最大糖果数目
//然后取出最大的就好了orzzzzz
function getCandyNum(arr){
let status=[];//维护一个二维数组，记录
for(let i=0;i<arr.length;i++){
status[i]=new Array();
if(let j=0;j<arr.length;j++){
if(i==j){status[i][j]=1;}
if(GCD(arr[i],arr[j])>1){
status[i][j]=max(status[i][j-1],status[i-1][j])+1;
}
else{
status[i][j]=max(status[i][j-1],status[i-1][j]);
}
}
}
return Math.max(status)
}
//求两个数的最大公约数
function GCD(a,b){
let temp;
whilr(b!=0){
temp=a%b;
a=b;
b=temp;
}
return a;
} 
投递同程旅行等公司10个岗位 >
