3.11 美团前端笔试 美团笔试

分享两个算法题的思路，第一个完全ac，第二个完全没ac，结束了检查的时候发现第一行注释忘记解开了，难怪说最后几分钟一直测不过去。但是思路我觉得是对的，大家可以看看，欢迎大家 点赞 留言 讨论。

第一题：100%ac比较简单：给思路并举例

1. 找出每段的长度，111 222 33333
2. 推进一个新数组，[3,3,4]
3. 然后对新数组每项除以二向下取证进行累加累加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_)