笔试

日期：2025.11.07

考查形式：在线笔试，临场出题，有面试官监督，时长1小时。

第一题

题目

二叉树每层最右节点 (二叉树的右视图)

解法

1. 简单解：BFS+层序遍历，时间复杂度O(N)，空间复杂度O(W)，W是二叉树最大宽度
2. 最优解：DFS，空间复杂度O(H)，H是树高

第二题

题目

实现一个 JSON.stringify，功能尽可能完善

解法

考察递归、边界处理、循环引用、Date对象、字符串转移、toJSON方法

第三题

题目

微信团队组织员工去公园郊游，需要从租车点租赁自行车。已知以下信息：

• 团队共有 n 名员工，每名员工随身携带的现金金额记录在数组 people 中（people[i] 表示第 i 名员工的现金，people 长度为 n，且所有元素非负）；
• 租车点共有 m 辆可租赁的自行车，每辆自行车的租金记录在数组 rent 中（rent[j] 表示第 j 辆自行车的租金，rent 长度为 m，且所有元素正整数）；
• 团队还有一笔公共活动经费 S（S 非负，可用于补充租车费用）。

租车规则：

1. 每辆自行车只能租赁一次（租出后不可重复租赁）；
2. 每名员工最多仅需使用一辆自行车（即一名员工的现金最多用于支付一辆自行车的部分 / 全部租金，不可拆分用于多辆车）；
3. 租赁一辆自行车的前提是：支付的总金额（个人现金 + 公共经费，或仅个人现金，或仅汇总现金 + 公共经费，需符合各小题约束）不低于该自行车的租金。

请根据以下 3 个不同的资金使用约束，分别计算团队最多能租赁的自行车数量。

1. 资金可互相借 + 可用公共预算：员工之间的现金可无限制汇总（即所有员工的现金合并为总个人资金），同时可使用公共经费 S。求在该约束下，团队最多能租赁的自行车数量。
2. 资金不可互相借 + 不可用公共预算：员工之间的现金不可拆借（每名员工仅能使用自己的现金），且不可使用公共经费 S。求在该约束下，团队最多能租赁的自行车数量。
3. 资金不可互相借 + 可用公共预算：员工之间的现金不可拆借（每名员工仅能使用自己的现金），但可使用公共经费 S（若某员工的现金不足以支付某辆自行车的租金，差额部分可由公共经费补充，但公共经费总额有限）。求在该约束下，团队最多能租赁的自行车数量。

解法

第一问

• 贪心策略：要租最多车，需优先选租金最低的车（用最少的钱覆盖最多车辆）。
• 步骤：
  1. 计算总可支配资金 = 所有员工现金之和（sum(people)） + 公共经费 S；
  2. 将租金数组 rent 按升序排序；
  3. 从排序后的租金数组中依次选取车辆，累计花费，直到总花费超过总可支配资金，此时已选的车辆数即为答案。

第二问

• 贪心策略：让 “现金多的员工” 优先租 “租金低的车”，最大化匹配数量。
• 步骤：
  1. 将员工现金数组 people 按降序排序（优先用现金多的人）；
  2. 将租金数组 rent 按升序排序（优先租便宜的车）；
  3. 用双指针匹配：i 指向当前现金最多的员工（people[i]），j 指向当前租金最低的车（rent[j]）；
  4. 若 people[i] >= rent[j]（该员工能承担租金），则租这辆车（count +=1，i +=1，j +=1）；若不能，则该员工无法租车（i +=1）；
  5. 直到 i 遍历完所有员工或 j 遍历完所有车，此时 count 即为答案。

第三问

• 贪心策略：优先租 “租金最低” 的车，并用 “个人现金尽可能多承担”，差额用公共经费补（最大化 S 的利用效率）。
• 步骤：
  1. 将员工现金数组 people 按升序排序（优先用现金少的人，避免现金多的人浪费在便宜车上）；
  2. 将租金数组 rent 按升序排序（优先租便宜的车）；
  3. 用双指针匹配：i 指向当前现金最少的员工（people[i]），j 指向当前租金最低的车（rent[j]）；
  4. 计算差额 diff = rent[j] - people[i]：
     • 若 diff <= 0（员工现金足够）：直接租车（count +=1，i +=1，j +=1）；
     • 若 diff > 0（需用公共经费补）：若 S >= diff（经费足够补差额），则租车（count +=1，S -= diff，i +=1，j +=1）；若经费不足，则无法租这辆车（j +=1，尝试下一辆更贵的？不，贪心是优先便宜的，所以此时应放弃这辆车，因为更贵的车需要更多经费，更不可能）；
  5. 直到 i 遍历完员工或 j 遍历完车或 S 耗尽，此时 count 即为答案。