Zoom 8.10前端两道编程题
- 我看后端等其他方向已经有了好多解法的帖子了；前端的两道题目，虽然有大佬给出了做法提示，但还没有一个解法，所以这里总结了大佬们的观点，给出以下解法。
- 当然，主要还是作为自己的记录贴，所以为了给自己看懂，有些口语化的描述；这是事后总结的，通过了几个示例，所以我也不能保证能AC；供有需要的小伙伴参考，如果有问题也欢迎指出来。
- 笔试是ACM模式，这里是核心代码模式了，所以一些输入做了简化处理。
- 我下次做笔试前一定要休息好！
一、不要互相嘲笑
- 当时脑子蒙蒙的，想着保证Tom的起点不变，后面只要按照jerry的变化来就好了，所以求jerry的变化，再推出tom的最佳结果，再与实际结果比较，就知道改哪几个了。
- 但是谁跟你说起点不变了？？所以，`最佳思路是把tom和jerry的成绩看成两条线，只要这两条线平行即可。所以只要最少次修改tom的成绩，使得两条平行即可`
- 这个做法和力扣2364. 统计坏数对的数目的思路很像，我那天双周赛就没做出来，可惜没有及时补上！
// tom:[1,2,-5,1,3] jerry:[-1,0,3,-1,1]
function howToChange(tom, jerry) {
let delat = new Map(), maxCount = 0;
for(let i = 0; i < tom.length; i++) {
let res = tom[i] - jerry[i];
if(delat.has(res)) {
delat.set(res, delat.get(res) + 1)
} else {
delat.set(res, 1)
}
maxCount = Math.max(maxCount, delat.get(res))
}
return tom.length - maxCount;
}
console.log(howToChange([1,2,-5,1,3], [-1,0,3,-1,1])); 二、社团的管理总量
- 题目描述就有点复杂，社团的管理模式是树状的，根节点即最大boss是Monika，其序号为1，每个节点的管理数量是子节点的兴趣种类 + 子节点的管理数量[听着很像递归]，最终求的是这个社团总的管理数量，即每个boss的管理数量的累加，还不是Monika的管理数量哦！
- 输入也比较复杂了，当时看着这个输入就有点懵懵的。其实要做两件事，首先构建树；然后遍历树求管理数量[即所有子节点的爱好种类]
- 首先是输入的人数n；字符串s表示每个人的兴趣用字母代替；然后是每个人的上下级关系。
- 注意那个上下级关系并不会指明谁是领导[我当时以为没法构建关系了，但是题干中说了Monika序号为1，他是最高领导即根节点，所以可以按序推导出其他的点。但是给的数据不是按序的，还要排序吗？还是从根节点了慢慢搜索比较，一层一层建构吧]
- 但是也没有说1的下面一定是2吧？如果说1的下面是3，3的下面是2，那就给我的遍历带来麻烦了。[我忘了题目怎么说的，就按简单的来处理了] 先找1的子节点，比如说2、3；然后找2的子节点、3的子节点……。
- 我觉得递归那里处理得不太好，有很多重复计算的过程，或许可以添加一个备忘录吧？但是map是从根节点开始遍历的，不是从最底下开始的，所以我也不知道怎么加这个备忘录
-
console.log(ohMyMonika(5, 'abccd', ['1 2', '2 3', '2 4', '2 5'])); // 5 console.log(ohMyMonika(1, 'ab', ['1 2'])); // 1 function ohMyMonika(n, s, rArr) { // 用map来记录关系; count记录整理了的条数，当count === rArr.length时即整理完毕了 let nodeVal = 1, map = new Map(), count = 0; while(count < rArr.length) { let childArr = [] map.set(nodeVal, childArr) for(let i = 0; i < rArr.length; i++) { if(rArr[i].includes(nodeVal)) { // 把子节点取出来 let index = rArr[i].indexOf(nodeVal); let val = (index === 0? parseInt(rArr[i][2]):parseInt(rArr[i][0])); // 把子节点存到map中去 childArr.push(val) count++; // 反手炸掉指挥部，即下次不要再遍历到相同的值了，所以赋个别的值改掉他 rArr[i] = 'boom' } } nodeVal++; } // 循环结束后，map即树就构建完了 console.log(map); // 遍历构建总的管理量————应该有递归的，但是我想不清楚 // 题目要求管理量是累加的，比如Monika的子节点是2，则Monika的管理量是直接管理的节点2和2的管理的点 let sum = 0 for(let item of map.keys()) { let res = getRes(item); sum += res; } return sum function getRes(item) { // 最末端的节点就返回0 if(!map.has(item)) { return 0 } else { let sum = 0; let arr = map.get(item); // 使用set来过滤相同的值 let set = new Set(); for(let item1 of arr) { sum += getRes(item1) set.add(s[item1 - 1]) } return sum + set.size; } } }
类似资料：