猿辅导第二批前端笔试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
实现思路：
- Set对每个脚本文件的哈希值去重
- 把每个脚本文件的哈希值存储到数组中，并排序
- 统计每个哈希值出现的次数，得到次数等于m的，就说明是共有的
- 以字符串形式输出
代码实现：
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%
- 构建矩阵
- 遍历得到上三角元素
- 遍历异或得到结果
代码实现：
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编程来不及做啊...