🏀Van 的编程小站

Appearance

笔试记录 ​

米哈游 ​

  1. 给一个数组，数组的价值为相邻项的最大乘积，要求数组可以任意相邻项对调，求数组的最大价值。例如[3,1,10],对调 3 和 1,3*10 为最大，返回 30。

    直接遍历，然后求元素和前一个和前两个的乘积，输出最大值即可

  2. 背包问题，背包容量 m，有 n 个物体，物品体积和价值.... ，但是有约束，存在 k 个约束，物品互斥，例如物品 1 物品 2 不能同时存在，物品 2 和物品 3 不能同时存在，求能够装下的最大价值。

    用 set 存储一个遍历过的物体，然后用 map 存储约束，然后回溯算法就可以做出来了

  3. 无向图，规定一个节点与其他节点相邻的边数为该节点的度数，同时规定一个具有奖励的节点值 x。首先由 xiaoyo 操作，然后再是玩家操作，他两循环进行直到一方获胜，或者无法完成操作。具体操作如下：从所有点中选择度为 1 的点，如果该点为 x 则当轮玩家获胜（输出玩家名，并退出），否则删除该节点及节点对应的边，继续循环直到有玩家获胜，或无法完成。 如果没有度为 1 的点，则输出 Draw，游戏退出。

    如果一开始该节点度为一，则直接 xiao'you 胜利，dfs，维护一个队列（如果删去某个节点可以使另一个节点度为一就加入队列），求最多要几次才能清空队列，并且队列里存在目标节点

文远知行 ​

  1. 给定一个和为 0 的数组，然后每次可以使 下标为 i 的元素减 1，并且使下标为 j 的元素加一，如果 i>j，则需要支付一枚金币，求数组元素全为 0 最小花费

    用一个值存储前面的正数减去负数的值，如果当前元素为负数且绝对值大于这个值，就使结果加上两者之差并且使该值为 0

  2. 力扣改编，用最少的箭射爆所有气球
  3. 一辆容量为 t 的货车，给定一个价格数组，距离数组，求到目的地最小花费 贪心即可

美团 ​

  1. 给定一个密码数组和正确密码，然后从最短的密码开始尝试，尝试过的密码不会再尝试，求最小次数和最多次数

    用两个 set，一个存储比目标密码短密码，一个存储跟目标密码一样长的密码

  2. 给定一个长为 n 的数组，数组每个元素都比 n 小，然后 每次可以做下面操作中的一个：
    1. 花费 x 删去第一个元素
    2. 花费 k * mex 删去整个数组，mex 数组为未出现的最小非负整数 求最小花费
  1. 然后对数组进行排序并遍历求出最小未出现的 mex 和用一个 map 存储每个元素出现次数
  2. mex 为 0 直接输出 0
  3. 遍历数组，用 xSum 表示删去元素的花费，用 res 表示 xSum + k* mex 的最小花费
  4. 如果 当前元素小于 mex: 出现次数为 1，就重新计算 mex 值和 res ，否则出现次数减一
  5. 遍历终止条件为删去所有的 0，直接输出 xSum 与 res 的相比的较小值

大疆 ​

  1. 用两种方式实现容器宽度为屏幕宽度，高度为屏幕高度，头部宽度为屏幕宽度，高度 200px，文章主体宽度自适应，高度自适应，侧边栏宽度 500px ，高度自适应
  2. 给定一个电池容量 x，一个二维数组，包含每个物品的重量和距离出发地的距离，求飞机能带的最大重量，耗电量为 重量乘距离

    背包或者回溯都可以

  3. 实现有缓存时间的 LRU

科大讯飞 ​

  1. 金字塔给出 一个正整数，然后输出倒序金字塔
sh
如 5
输出
55555
5555
555
55
5
  1. 给一堆数字，按顺序压入栈，如果栈顶元素和要压入的元素值一样，则合并为值 +1，求栈最后元素是什么样，如：1,1,2,3,4,5 就变成 6 了

    思路就是设一个变量为结果数组，两层循环，一层循环用 while ，判断条件是结果数组不为空并且栈顶与要压入栈中的数字相等，就弹出一个元素并且数字加一，循环结束将这个数字压入结果数组

  2. 给一个数组，然后假设起点为 x，你每次可以选择与左边的元素合并或者与右边的元素合并，值为两者之和，并且与你合并的元素的值必须大于你，求 从分别从 0 到 n 为起点的最大值是多少,如: 2 1 3 就是 2 6 3，因为从 0 和 2 为起点的都无法合并，从 1 为起点，先合并左边再合并右边

    思路就是回溯算法，求先合并左边和先合并右边哪个值最大，然后取最大就好 不可以贪心，因为比如 1 6 2 3 1 就会出问题，答案是 7 6 8 3 4

腾讯音乐笔试 ​

  1. 给定一个链表，定义一个优美链表的形式：假设相临元素为 a_i-1 a_i 则必须满足 —— a_i-1 不等于零 a_i 等于零，或者 a_i-1 等于零 a_i 不等于零，定义一个合并操作，将相邻两个元素合并，然后权值取其中较大的，问最少需要几次
  2. 给定一个二叉树，希望你将它补齐为完全二叉树
  3. 给定一个数组和一个数字 m，要求你在数组中添加从 1 到 m 之间所有的数字，并且要使最终数组的相邻元素绝对值之差的和最小
  4. 给定一个一个叶节点的数组和所有叶节点值得数组，要求通过这个构造一个哈夫曼树，叶节点数组元素的形式为 010 这种二进制编码，其中 0 表示向左 1 表示向右

拼多多 ​

  1. 实现一个时间分片机制求数字和，给定一个 n，然后你需要编写一个函数，采用累加的方式求和，并且每次任务只能执行 15ms，如果超过，则需要用宏任务挂起，避免阻塞浏览器。

    返回一个 Promise 和 lastDate 存储宏任务执行开始时间，然后每次调用累加函数时都检查 Date.now 减去 lastDate ，如果大于，则调用一个 setTimeout 执行累加函数并且将 lastDate 更新为现在的时间，否则直接执行函数

  2. 检查字符串是否有效，匹配 () [] {}
  3. 实现一个消息队列，可以注册消息，为不同消息注册任务，消息到达时候消费消息，把所有消息相关的任务执行，然后实现一个预请求和一个请求函数，请求函数设置一个 apiName 和一个超时时间，如果超时时间内消息队列收到或者已有消息，则采用缓存，并在返回数据中标明是缓存，否则直接请求并等待，然后返回数据标明不是缓存
  • 消息队列用两个 map ，一个存储数据，一个存储任务。
  • 在消息到到达时，检查是否有相关任务，有的话则清空，否则存储。
  • 注册函数时，检查是否有数据，有则直接使用并删除数据，否则存储任务
  • 请求函数用一个 promise ，然后 setTimeout ，如果超时，直接 reject promise，然后在消息队列注册一个函数，函数 resolve promise ，然后将 promise 返回，链式调用一个 catch 负责发送一个真实请求

淘天 ​

  1. 求最长递增子序列，并且要求后一个元素比前一个元素的平方大
  2. 有一个数组，每次从队首弹出一个元素花费为 x，将剩下的数组全部清空花费为剩下的数组极差乘于 y，求清空数组最小花费
  3. 给定一个区间，求区间内有多少个子序列为 red ，比如 rerrded ，1 到 7 区间为 5

小红书 ​

  1. 给定一个二维商品数组，其中每个元素第一个为评价分数，第二个为价格，给定一个一个评价阈值，求购买所有评价大于等于评价阈值的商品需要多少钱
  2. 给定一个书籍的二维数组，每个元素的第一个为类别（1 或者 2），第二个为是否可移动，假如一个书籍与前边的书籍种类不同，凌乱度加一，求最小凌乱度
  3. 给定一个长度为 n 字符串（那个字符为 R 或者 B），然后给定 n - 1 的输入，每个输入为一个边（就是 两个相连的节点值），求删去一个 R，剩下的各个孤岛中 B 最多有多少个

招商银行 ​

  1. 求下面哪个函数不能实现一个输出数组值为undefined的下标
js
for (let i = 0; i < arr.length; i++) {
  const a = arr[i];
  if (a == null) console.log(i);
}

arr.forEach((e) => {
  if (e == null) console.log(i);
});

for (let i in arr) {
  if (a == null) console.log(i);
}
for (let [i, v] of arr.entries()) {
  if (v == null) console.log(i);
}
  1. 获取页面中的 id 为 toggle 的按钮，并绑定一个函数实现深色背景和浅色背景的不停来回切换
  2. 用 CSS 实现一个充电宝效果

携程 ​

  1. 给定 n,m,k，求从 1 到 n 组成的字符串中，最长子序列长度为 m 的字典序最大的子串是什么？
  2. 给定一个长度为 n 全是有 0 和 1 组成的字符串，有操作每次可以将 [0 , i] 的字符串全部取反，假设这个字符串需要 x 次操作将字符串全部变为 1，那么我们称这个字符串的权值是 x，求字符串有多少个权值为奇数并且长度为奇数的子字符串（包括本身）
  3. 给定 n,m,k，求从 0 到 n 组成的 m 位数有多少个是大于 k 的
  4. 给定n,m,k，和一个长度为 n 的数组 arr，每次操作可以使第 i 个元素 a_i = a_i - 1， 求最少需要几次操作可以使数组的每一个长度为 m 的连续子数组的元素和大于 k

去哪儿 ​

  1. 给定一个长度为 n 的数组和 k，求最多可以删去几个元素并且保证数组的元素和大于 k
  2. 手写 Promise
  3. 给定 n 个长度为 m 的字符串数组，求如何选取可以使其组成一个回文字符串
js
// input: 'fff', 'acm', 'mca'
// output: 2, 1, 3

备案号：闽ICP备2024028309号-1

Copyright © 2024-present @Wchvan