猿辅导第二批前端笔试8.26

题型：选择（15*3）+编程（30+30+40）=总分145，时间90分钟

选择题

前端不友好型，偏数据库计网操作系统，咔咔一顿乱做

编程题第一题：公共哈希值（100%）

题目大意：找到不同测试脚本公共哈希值
输入：第一行n为测试用例数量，每个测试用例包含：m脚本文件数量，剩余m行表示各个脚本文件哈希值，哈希值有多个且没排序，可能有重复
输出：按照字典顺序[划重点！！！]返回共有的哈希值字符串，多个用空格隔开
示例：
输入：

1
3
1 5 2 6
5 2 8
1 2 6

输出：

2

实现思路：

1. Set对每个脚本文件的哈希值去重
2. 把每个脚本文件的哈希值存储到数组中，并排序
3. 统计每个哈希值出现的次数，得到次数等于m的，就说明是共有的
4. 以字符串形式输出

代码实现：

function fn(m, files) {
    let nums = [];
    for (let file of files) {
        nums.push(...new Set(file))
    }
    nums.sort();   // 这里注意下，题目中说了按照字典顺序返回

    let map = new Map();

    for (let i of nums) {
        if (map.has(i)) {
            map.set(i, map.get(i)+1);
        } else {
            map.set(i, 1)
        }
    }

    let res = [...map.entries()].filter(item => item[1] === m).map(item => item[0]).join(' ');
    return res;
}

// test
let m = 3;
let files = [
    [1,5,2,6],
    [5,2,8],
    [1,2,6],
];

fn(m, files);   // '2'

编程题第二题：树每层节点最大差值（超时过60%）

题目大意：给一个非空树，求每一层节点value的大差值
输入：第一行n为测试用例数量，每个测试用例包含：m表示有m个节点，剩余m行包含id,parentId,value，其中根节点的父节点为0

示例：
输入：
输出：

1
5
1 0 12
2 1 1
3 1 45
4 3 5
5 2 1

输出：

0 44 4

解释：

          1(12)                 ------差值12-12 = 0
         /     \
        2(1)    3(45)           ------差值45-1 = 14
        /        \
       5(1)      4(5)           ------差值5-1 = 4

实现思路：迭代法实现层序遍历，超时了过了60%
代码实现：

function fn(trees) {
    trees.sort((a, b) => a[0]-b[0]);
    let stack = [trees[0]], res = [];

    while (stack.length) {
        let len = stack.length;
        let temp = [];
        while (len--) {
            let node = stack.shift();
            temp.push(node[2]);

            let child = trees.filter(item => item[1] === node[0]);
            stack.push(...child);
        }
        res.push([...temp]);
    }

    let p = [];
    for (let i of res) {
        let m1 = Math.max(...i);
        let m2 = Math.min(...i);

        p.push(m1-m2);
    }

    return p.join(' ');
}

// test
const trees = [
    [1,0,12],
    [2,1,1],
    [3,1,45],
    [4,3,5],
    [5,2,1],
]
console.log(fn(trees)); // '0 44 4'

编程题第三题：矩阵异或求值（超时过42.86%）

题目大意：给你一个m*m的矩阵，矩阵0,0的初始值是确定的，其余值根据行列递增，求异或结果，为了简便，只需要计算上三角即可，由于数字可能很大，所以要用BigInt进行处理
输入：一行包含m和st，m表示矩阵大小，st表示初始值
输出：数字表示异或结果
示例：
输入：

0 1 2
3 4 5
6 7 8

输出：

2 (0^1^2^3^4^6=2)

实现思路：暴力法，通过42.86%

1. 构建矩阵
2. 遍历得到上三角元素
3. 遍历异或得到结果

代码实现：

function fn(m, st) {
    let arr = [...new Array(m * m).keys()].map(item => item + st);
    let matrix = constrMatrix(arr, m, m)

    let res = [];
    for (let i = 0; i < m; i++) {
        let temp = matrix[i].slice(0, m - i)
        res.push(...temp);
    }

    let s = 0n;
    for (let i of res) {
        s ^= BigInt(i);
    }

    return Number(s)
}
function constrMatrix(arr, m, n) {
    let res = [];

    for (let i = 0; i < m; i++) {
        let temp = arr.slice(i * m, i * m + n);
        res.push([...temp]);
    }

    return res;
}


// test
let m = 3,st = 0;
console.log(fn(m, st)); // 2

总结

算法太渣了...只能想到最简单的方法，结果就是一直超时...
深深觉得一个半小时选择+3编程来不及做啊...