华为OD机试真题 JavaScript 实现【找出通过车辆最多颜色】【2023Q1 100分】

华为OD机试真题 JavaScript 实现【找出通过车辆最多颜色】【2023Q1 100分】-LMLPHP

一、题目描述

在一个狭小的路口，每秒只能通过一辆车，假如车辆的颜色只有3种，找出n秒内经过的最多颜色的车辆数量。

三种颜色编号为0、1、2。

二、输入描述

第一行输入的是通过的车辆颜色信息 [0 1 1 2] 代表4秒钟通过的车辆颜色分别是0 1 1 2；

第二行输入的是统计时间窗，整型，单位为秒。

三、输出描述

输出指定时间窗内经过的最多颜色的车辆数量。

四、解题思路

输入车辆颜色集合；
输入统计时间窗；
定义一个map，存储不同颜色的车的个数；
先初始化窗口，i相当于右指针；
如果已经存在此颜色，则再次+1；
如果首次出现，则为1；
当超出统计时间窗，取出脱离窗口的车型颜色；
如果map中已经存在，则-1；
算下时间窗内，相同车型出现的最大个数；

五、JavaScript算法源码

function calculate(colors, windowSize) {
    const n = colors.length;
    const colorCount = new Map();
    let max = 0;

    for (let i = 0; i < n; i++) {
        const color = colors[i];

        if (colorCount.has(color)) {
            colorCount.set(color, colorCount.get(color) + 1);
        } else {
            colorCount.set(color, 1);
        }

        if (i >= windowSize) {
            const leftColor = colors[i - windowSize];
            if (colorCount.has(leftColor)) {
                colorCount.set(leftColor, colorCount.get(leftColor) - 1);
                if (colorCount.get(leftColor) === 0) {
                    colorCount.delete(leftColor);
                }
            }
        }

        max = Math.max(max, colorCount.get(color));
    }

    return max;
}

六、效果展示

1、输入

0 1 2 0 2 2 1
4

2、输出

3、说明

一共7台车，肉眼可见，4秒内通过最多的车是2，一共3台，故输出3。