8月28日 小红书前端笔试

这次笔试编程题记录一下，【考试没写出来，考试后看别人代码后琢磨明白了，特别是第一题【排队】不知道为什么只对了27%】，对了，想问一下牛友们，在赛码网写编程题的时候，超时是不是不会报超时，只会报答案错误吗？

一对一

时间限制： 3000MS
内存限制： 589824KB
题目描述：
某公司正在组织新员工团建，其中一项活动是两两配对进行石头剪刀布。
因为新员工来自不同的学校和专业，他们许多人之间并不熟悉，但他们之间的朋友关系形成了一棵树。
即若将朋友关系描述为一张无向图，则这张无向图中任意两点之间有且仅有一条路径。为了避免尴尬，组织者希望互为朋友的配对数量尽可能多。
现在他希望你求出互为朋友的配对数量最多能有多少。
输入描述
第一行有一个偶数n(2 <= n <= 1000)，代表有n个新员工。
第二行有n - 1个空格隔开的数，第i个数ai代表编号为i + 1的新员工与编号为ai的员工互为朋友。
输入保证新员工之间的朋友关系形成了一棵树
输出描述
输出在所有可能的配对方案中，互为朋友的配对数量最多是多少。
样例输入
6
1 2 2 3 3
样例输出
2
提示
如样例中，一共有6个新员工，朋友关系有以下五个(1, 2), (2, 3), (2, 4), (3, 5), (3, 6)。
可以证明无论如何匹配这6个人， 最多只能有两对是互为朋友的，因此输出2。

function oneToOne(n, nums) {
  let map = new Map();
  for (let i = 0; i < nums.length; i++) {
    map.set(i + 2, nums[i])
  }
  let list = Array.from(map);
  let count = 0;
  while (list.length > 0) {
    let target = 0;
    // 获取map的所有values并转成数组
    let values = Array.from(map.values());
    //要删除的键
    let del = []

    for (let item of list) {
      //如果是叶子节点
      if (!target && !values.includes(item[0])) {
        target = item;
        count += 1;
        break;
      }
    }
    for (let item of list) {
      //删除target节点或者与target节点对应节点有关系的节点  切断关系
      if (target && item[0] == target[0] || item[1] == target[1] || item[0] == target[1] || item[1] == target[0]) {
        del.push(item[0])
      }
    }

    //删除键
    for (let i = 0; i < del.length; i++) {
      map.delete(del[i])
    }
    list = Array.from(map)
  }
      console.log(count);
}
oneToOne(6, [1, 2, 2, 3, 3])

法术 【这道题之前的思路应该是超时了】

法术
时间限制： 3000MS
内存限制： 589824KB
题目描述：
小明是一名魔法师，他会n种法术，其中第i种法术的威力为ai，他经常通过双手各自释放一种法术来提升威力，
能得到的威力值为双手各自释放的法术的威力的乘积，但是他还不够强大，双手释放的两种法术必须是不同的，即不能双手释放同一种法术。
这天他接到了一个任务，需要释放威力值至少为K才能完成，他想请你帮他算一算，在两只手都释放法术的情况下，共有多少方案能达到威力值K。
每种方案可记作（u，v），u≠v，其威力值为au * av，（u，v）和（v，u）会被视为不同的方案。

输入描述
第一行两个正整数n和K，表示法术数量和威力值需求。

第二行为n个正整数a1, a2,......an，其中ai表示第i个法术的威力为ai。

输出描述
输出威力值至少为K的方案数。

let s = read_line().split(" ");
let [n, k] = s;
let nums = [];
let count = 0;
nums = read_line().split(" ").map(v => parseInt(v));
function fs(nums) {
  //从小到大排序
  nums.sort((a, b) => a - b);
  let i = 0, j = nums.length - 1;
  while (i < j) {
    let value = nums[i] * nums[j];
    if (value >= k) {
      //如果nums[i]和nums[j]相乘大于等于value，那么i后面的元素与j节点相乘都会大于等于value
      //所以可以 算出 i到j之间有多少个节点，然后再乘以2，因为 (u,v)和(v,u)都算新的方案
      count += (j - i) * 2;
      j--;
    } else {
      //如果nums[i]*nums[j]<k，说明nums[i]太小了，需要往右挪一下
      i++;
    }
  }
  console.log(count);

}
fs(nums);

排队

这道题不知道为什么只过了27%，难道思路不是先排序，然后遍历找嘛？？

时间限制： 3000MS
内存限制： 589824KB
题目描述：
在遥远的国度有一位国王，他每天的工作都十分繁忙，因为每天都有许多大臣来向他汇报各种信息等。
这天有n位大臣来汇报信息，其中第i位的序号为i，为了更有效的完成每天的工作，国王决定给每位大臣汇报的事情按重要性进行一个排序，
让各位大臣按排序依次汇报。首先对每人的汇报在m个方面各评估一个重要性，然后每个汇报的重要性就是m个方面的重要性之和，重要性越高的汇报会排在越前面，
对于重要性相同的，则按大臣的序号排序，越小的在越前面。这时，序号为id的大臣找到了你，他想请你帮他计算一下他排在第几个。
输入描述
第一行三个正整数n、m和id，表示大臣数量、重要性方面数量和来找你帮忙的大臣序号。
接下来n行每行m个正整数，第i行为ai1, ai2,......aim，其中aij表示序号为i的大臣的汇报在第j个方面的重要性。
输出描述
输出一行一个正整数ans，表示序号为i的大臣排在第ans位。
样例输入
3 3 2
90 90 90
80 100 90
80 85 85
样例输出
2
提示
1 ≤ n ≤ 500, 1 ≤ m ≤ 500, 1 ≤ aij ≤ 100。