3.11 美团前端笔试 美团笔试
分享两个算法题的思路，第一个完全ac，第二个完全没ac，结束了检查的时候发现第一行注释忘记解开了，难怪说最后几分钟一直测不过去。但是思路我觉得是对的，大家可以看看，欢迎大家 点赞 留言 讨论。
第一题：100%ac比较简单：给思路并举例
- 找出每段的长度，111 222 33333
- 推进一个新数组，[3,3,4]
- 然后对新数组每项除以二向下取证进行累加累加1+ 1+ 2 = 4
// let inchar = '111222333';
// let inchar = '11551111';
let ch_ = [],index = 0;
let left = inchar[0];
let sum = 1;
for (let i = 1,len = inchar.length; i< len; i++){
if(left != inchar[i] ){
ch_[index++] = sum;
sum = 1;
left = inchar[i];
}else if(left == inchar[i]){
sum++;
}
if( i == len-1){
ch_[index++] = sum;
}
}
let num = 0;
ch_.forEach(item=>{
num += Math.floor(item/2);
})
console.log(ch_,num)
第二题：我把思路模拟成了，罐子里面丢糖果，不用管一一对应的问题。由于没有ac，仅供参考
关于时间复杂度：
中间两个while循环其实分别总共运行了，ch1的长度次，ch2的长度次 虽然他们是嵌套，其实你看他有shift()方法，执行一次，数组的长度就减一了，真实的运行次数就是数组长度次； 总的复杂度是： O(len) 开始for循环遍历天数 +O(ch1.length) + O(ch2.length) 两个while次数 + O(len) 最后遍历天数
近似理解O(n)即可
et n = read_line();
let char1 = gets(200020);
let char2 = gets(200020);
let ch1 = char1.split(' ')
let ch2 = char2.split(' ')
// let n = 3
// let ch1 = [2,1,5]
// let ch2 = [6,3,7];
let index = 0,step=0;
let arr = Array(100000).fill(0);
ch1.sort();
ch2.sort();
let len = ch2[ch2.length-1];
let max = 0
//确定每个时刻的的共有流行
for(let i=0; i< len; i++){
// console.log('22')
//出现就加+
while(ch1[0] == i){
step++;
if(max<step) {//几率同时能看到的最大值
max = step;
}
ch1.shift();
}
arr[i] = step;
//离开一个就减一
while(ch2[0] == i){
step--;
ch2.shift();
}
}
let sum_ = 0;
//遍历每天
for(let i=0; i< len; i++){
if(max == arr[i]){
sum_++;
}
}
//输出答案
console.log(max,sum_)
