2023春招算法题汇总（2）

Author：baiyucraft

BLog： baiyucraft’s Home

0312 拼多多 春招实习

第一题：飞机大战

题目

多多最近下载了一款飞机大战的游戏，多多可以通过游戏上的不同发射按键来控制飞机发射子弹：

按下 A 键,飞机会发射出 2 枚子弹，每个子弹会对命中的敌人造成 1 点固定伤害，但不能作用于同个敌人。

按下 B 键,飞机会发射出 1 枚子弹，子弹会对命中的敌人造成巨额伤害并瞬间将其秒杀。

多多是个游戏高手，总是能操控子弹命中想要命中的敌人。这个游戏—共有 T 个关卡，消灭当前关卡全部敌人后,发射出去多余的子弹会消失，游戏会自动进入下一个关卡。

假设每个关卡都会在屏幕中同时出现 N 个敌人，这 N 个敌人所能承受的伤害也已经知道。多多想知道，每个关卡自己最少按几次发射按键就可以将敌人全部消灭？

输入描述

第一行输入一个固定数字 T （1≤T≤10001 \le T \le1000)表示关卡的总数量 N （1≤N≤2001 \le N \le 200）表示每个关卡出现的敌人数量。

接下来 T 行，每行有 N 个数字 D1, D2, ..... Dn（1≤Di≤2001 \le D_i \le 200）分别表示这 N 个敌人所能承受的伤害。

输出描述

结果共有 N 行，每行一个数字，分别表示对于这个关卡，最少按几次发射按键就可以将敌人全部消灭。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 输入
3 3
1 2 1
2 3 2
1 2 3
// 输出
2
3
3
// 说明
游戏共有3个关卡，每个关卡会出现3个敌人。
第一个关卡，先按下A建控制子弹消灭第1个和第3个敌人后，再按下B键消灭第二个敌人。所以最少按2次。
第二个关卡，按下3次B键分别消灭这3个敌人。
第三个关卡，按下3次B键分别消灭这3个敌人。也可以按3次A建,敌人剩余承受伤害的变化为:[1, 2, 3] -> [1, 1, 2] -> [1, 0, 1] -> [0, 0, 0]

代码

每个等级，比较总长度和总数

1
2
3
4
5
6
7
const { readlinesNum } = require('../utils/read');
const [[T, N], ...levels] = readlinesNum();
console.log(T, N, levels);

const ans = levels.map((level) => Math.min(Math.ceil(level.reduce((sum, num) => sum + num, 0) / 2), level.length));

console.log(ans.join(' '));

第一题：飞机大战

题目

又到了团建的时间，多多君负责安排这次的团建活动。

多多君准备了三个活动（分别编号 A 、 B 和 C )，每个活动分别有人数上限以及每个人参加的费用。

参加团建的有 N 个人(分别编号 1~N ），每个人先投票选择若干个意向的活动，最终每个人只能参加其中一个。

多多君收集完投票结果后，发现如何安排成为了大难题：如何在满足所有人的意向的情况下，使得活动的总费用最少。

于是多多君找到了擅长编程的你,希望你能帮助找到个合理的团建计划。

输入描述

第一行，一个整数 N ，代表准备参加活动的人数。(1 ≤N≤1001\ \le N \le 100)

接下来 N 行，每行一个由 "ABC" 组成的字符串，其中第 i 行表示第 i 个人投票了哪几个活动。

(输入保证字符串非空，且由大写的 "ABC" 字符组成)

最后 3 行，每行两个整数，分别表示三个活动的人数上限以及每个人参加的费用。

(人数上限以及参与活动的费用均为不超过 100 的正整数)

输出描述

输出共 2 行

如果能满足所有人的要求,第一行输出 "YES” ，第二行输出最少的总费用。

如果不能满足所有人的要求,第一行输出 "NO"，第二行输出最多能满足多少人。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 输入
5
A
B
C
AB
ABC
2 1
2 2
2 3
// 输出
YES 9
// 输入
5
A
B
C
AB
AB
1 1
2 2
3 3
// 输出
NO 4

代码

最小费最大流（领悟）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
const { readlines } = require('../utils/read');
const [N, ...rest] = readlines();
const n = Number(N); const people = rest.slice(0, N);
// 人数上限以及每个人参加的费用
const abc = rest.slice(N).map(item => item.map(Number));
console.log(N, people, abc);

// 图 的邻接表表示法，总共 源点 + 人 + 活动 + 汇点
const graph = Array.from({ length: n + 5 }, () => []);
// 图 的边集表示法
const edges = [];

// x, y为两端点，z为容量，w为费用
const addEdge = (u, v, z, w) => {
  edges.push([u, v, z, w]);
  edges.push([v, u, 0, -w]);
  graph[u].push(edges.length - 2);
  graph[v].push(edges.length - 1);
};

const spfa = (source, sink) => {
  // dist 表示源点到各个点的最短距离
  const dist = { [source]: 0 };
  // visited 表示该点是否已经访问过
  const visited = {};
  // in_queue 表示该点是否已经在队列中
  const inQueue = { [source]: true };
  // pre_edge 表示该点的上一条边在 edges 中的下标
  const preEdge = { [source]: -1 };
  // 初始化队列，将源点加入队列中
  const q = [source];
  // 当队列不为空时，进行循环
  while (q.length) {
    // 取出队首元素
    const u = q.shift();
    // 将该点标记为不在队列中
    inQueue[u] = false;
    // 将该点标记为已经访问过
    visited[u] = true;
    // 遍历该点的所有出边
    graph[u].forEach(i => {
      // [u, v, z, w] 表示边的两个端点，容量，费用
      const [u, v, z, w] = edges[i];
      // 如果容量大于 0，且从源点到 u 的距离加上 u 到 v的距离 小于从源点到 v 的距离
      const [du, dv] = [dist[u], dist[v] || Infinity];
      if (z > 0 && du + w < dv) {
        // 更新从源点到 v 的距离，更新 v 的上一条边在 edges 中的下标
        dist[v] = du + w; preEdge[v] = i;
        // 如果 v 不在队列中，将 v 加入队列中
        if (!inQueue[v]) {
          q.push(v);
          inQueue[v] = true;
        }
      }
    });
  }
  return [visited[sink] || false, dist, preEdge];
};

const mcmf = (source, sink) => {
  // 最大流，最小费用
  let maxFlow = 0; let minCost = 0;

  while (true) {
    // res 表示是否存在增广路
    const [res, dist, preEdge] = spfa(source, sink);
    // 如果不存在增广路，退出循环
    if (!res) break;
    // flow 表示增广路上的最小容量
    let flow = Infinity;
    // u 表示当前节点
    let u = sink;
    // 从汇点向前遍历，找到增广路上的最小容量
    while (u !== source) {
      // i 表示当前节点的上一条边在 edges 中的下标
      const i = preEdge[u];
      // 更新 flow
      flow = Math.min(flow, edges[i][2]);
      // 更新 u
      u = edges[i][0];
    }
    // 更新最大流
    maxFlow += flow;
    // 更新最小费用
    minCost += flow * dist[sink];
    // 从汇点向前遍历，更新边的容量
    u = sink;
    while (u !== source) {
      // i 表示当前节点的上一条边在 edges 中的下标
      const i = preEdge[u];
      // 更新边的容量
      edges[i][2] -= flow;
      // 更新反向边的容量
      edges[i ^ 1][2] += flow;
      // 更新 u
      u = edges[i][0];
    }
  }
  return [maxFlow, minCost];
};

// 计算 活动 到 汇点 的 容量 以及 费用
const [nums, costs] = abc.reduce((acc, cur, index) => {
  const [num, cost] = cur;
  acc[0][1 + n + index] = num;
  acc[1][1 + n + index] = cost;
  return acc;
}, [{}, {}]);

// 定义 A B C 三种活动在 图 中的 端点号
const peoAcvMap = { 'A': n + 1, 'B': n + 2, 'C': n + 3 };
people.forEach((person, index) => {
  // 源点 到 people 的边
  addEdge(0, index + 1, 1, 0);
  const activ = Array.from(person).map(c => peoAcvMap[c]);
  // people 到 活动的边
  activ.forEach(act => addEdge(index + 1, act, 1, costs[act]));
});
// 活动 到 汇点
addEdge(n + 1, n + 4, nums[n + 1], 0);
addEdge(n + 2, n + 4, nums[n + 2], 0);
addEdge(n + 3, n + 4, nums[n + 3], 0);

// console.log(graph, edges);

// 从源点到汇点的最大流和最小费用
const source = 0; const sink = n + 5 - 1;
const [maxFlow, minCost] = mcmf(source, sink);
if (maxFlow === n) console.log('YES', minCost);
else console.log('NO', maxFlow);

第三题：客流量分析

题目

多多君开了一家自助餐厅，为了更好地管理库存，多多君每天需要对之前的客流量数据进行分析，并根据客流量的平均数和中位数来制定合理的备货策略。

输入描述

第一行一个整数 N ，表示餐厅营业总天数（0<N≤2000000 \lt N \le 200000）。

第二行共 N 个整数,分别表示第 i 天的客流量 R （0<R≤10000000 \lt R \le 1000000）。

输出描述

输出共两行:

第一行长度为 N ，其中第 i 个值表示前 i 天客流量的平均值，第二行长度为 N ，其中第 i 个值表示前 i

天客流量的中位数。

示例

1
2
3
4
5
6
// 输入
5
1 2 3 4 10
// 输出
1 2 2 3 4
1 2 2 3 3

代码

用堆存储，快速计算中位数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
const { readlinesNum } = require('../utils/read');
const [N, nums] = readlinesNum();
console.log(N, nums);

// 大顶堆
class MaxHeap {
  constructor() {
    this.heap = [];
  }

  // 插入元素
  insert(value) {
    this.heap.push(value);
    let index = this.heap.length - 1;
    // 上浮，与父节点比较，如果大于父节点，则交换位置
    while (index > 0 && this.heap[index] > this.heap[Math.floor((index - 1) / 2)]) {
      [this.heap[index], this.heap[Math.floor((index - 1) / 2)]] = [this.heap[Math.floor((index - 1) / 2)], this.heap[index]];
      index = Math.floor((index - 1) / 2);
    }
  }

  // 删除堆顶元素
  delete() {
    if (this.heap.length === 0) {
      return null;
    }
    const max = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      let index = 0;
      while (index * 2 + 1 < this.heap.length) {
        const left = index * 2 + 1;
        const right = index * 2 + 2;
        let larger = left;
        if (right < this.heap.length && this.heap[right] > this.heap[left]) {
          larger = right;
        }
        if (this.heap[index] < this.heap[larger]) {
          [this.heap[index], this.heap[larger]] = [this.heap[larger], this.heap[index]];
          index = larger;
        } else {
          break;
        }
      }
    }
    return max;
  }

  // 获取堆顶元素
  getMax() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }
  getLength() {
    return this.heap.length;
  }
}

// small存储较大的一半（小顶堆），large存储较小的一半（大顶堆）
// 保证 small > large
const small = new MaxHeap(); const large = new MaxHeap();
const avgs = []; const mids = [];
nums.reduce((sum, cur, index) => {
  // 平均数
  sum += cur;
  avgs.push(Math.round(sum / (index + 1)));
  // 中位数
  if (small.getLength() !== large.getLength()) {
    small.insert(-cur);
    large.insert(-small.delete());
  } else {
    large.insert(cur);
    small.insert(-large.delete());
  }
  const mid = small.getLength() !== large.getLength() ? -small.getMax() : (large.getMax() - small.getMax()) / 2;
  mids.push(mid);
  return sum;
}, 0);

console.log(avgs.join(' '));
console.log(mids.join(' '));
DataStructure
#数据结构 #JavaScript #招聘
2023春招算法题汇总（2）
http://baiyucraft.top/DataStructure/DataStructure-interviewAlgorithm-2.html
作者
baiyucraft
发布于
2023年3月29日
许可协议