🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员

✨ 本系列打算持续跟新饿了么近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。

❤️ 01.K小姐的生日派对

问题描述

K小姐要举办一个生日派对,她邀请了 $n$ 个好朋友。每个朋友都准备了一份礼物,其中第 $i$ 个朋友的礼物价值为 $a_i$。

K小姐想知道,这些礼物中一共有多少种不同价值的礼物。但是她不希望统计那些太便宜的礼物,所以她不会统计价值为 $1$ 的礼物。

输入格式

第一行包含一个正整数 $n$,表示朋友的人数。

第二行包含 $n$ 个正整数 $a_1,a_2,\cdots ,a_n$,表示每个朋友礼物的价值。

输出格式

输出一个整数,表示有多少种不同价值的礼物(不包括价值为 $1$ 的礼物)。

样例输入

3
20 2 4

样例输出

3

数据范围

• $1\le n\le 2\times 10^5$
• $1\le a_i\le 2\times 10^5$

题解

这道题的关键是要统计出有多少种不同的礼物价值,但不包括价值为 $1$ 的礼物。我们可以用一个集合(set)来存储所有出现过的礼物价值,这样可以自动去重。

具体步骤如下:

1. 读入朋友人数 $n$ 和所有礼物价值 $a_i$。
2. 将所有礼物价值存入一个集合中,这样可以自动去重。
3. 如果集合中有价值为 $1$ 的礼物,就将其删除。
4. 输出集合的大小,即为不同价值礼物的数量。

时间复杂度 $O(n)$,空间复杂度 $O(n)$。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()n = int(input())
gifts = set(map(int, input().split()))
if 1 in gifts:gifts.remove(1)
print(len(gifts))

• Java

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());String[] arr = br.readLine().split(" ");Set<Integer> gifts = new HashSet<>();for (String s : arr) {gifts.add(Integer.parseInt(s));}gifts.remove(1);System.out.println(gifts.size());}
}

• Cpp

#include <iostream>
#include <set>using namespace std;int main() {int n;cin >> n;set<int> gifts;for (int i = 0; i < n; i++) {int x;cin >> x;gifts.insert(x);}gifts.erase(1);cout << gifts.size() << endl;return 0;
}

🧡02.K小姐的珠宝盒

问题描述

K小姐有一个由 $n$ 颗宝石组成的珠宝盒。每颗宝石都有一个能量值 $a_i$。

现在她想对珠宝盒进行 $Q$ 次查询。每次查询时,她会选择一个区间 $[l,r]$,然后给出一个能量阈值 $k$。她想知道在区间 $[l,r]$ 中,是否存在一个位置 $i$,使得将区间 $[l,i]$ 中所有宝石的能量值进行按位或运算的结果等于 $k$。如果存在这样的位置 $i$,她希望知道最小的 $i$ 是多少;如果不存在,则输出 $-1$。

输入格式

第一行包含两个正整数 $n$ 和 $Q$,分别表示宝石的数量和查询的次数。

第二行包含 $n$ 个正整数 $a_1,a_2,\cdots ,a_n$,表示每颗宝石的能量值。

接下来 $Q$ 行,每行包含三个正整数 $l,r,k$,表示一次查询。

输出格式

对于每次查询,输出一行一个整数,表示答案。如果不存在满足条件的位置 $i$,则输出 $-1$。

样例输入

5 5
3 2 3 3 6
1 2 3
1 5 7
1 4 7
2 2 2
2 3 7

样例输出

1
5
-1
2
-1

数据范围

• $1\le n,Q\le 10^6$
• $1\le l\le r\le n$
• $0\le a_i,k<2^{30}$

题解

本题可以使用前缀或和二分查找来解决。

首先预处理出一个二维数组 $cnt$,其中 $cnt[i][j]$ 表示在前 $i$ 个数中,第 $j$ 位二进制表示中 $1$ 的个数。可以通过以下方式计算:

$$cnt[i][j]=\{\begin{array}{ll}cnt[i-1][j]+1& a[i]\text{ 的第 }j\text{ 位为 }1\\ cnt[i-1][j]& \text{otherwise}\end{array}$$

然后对于每次查询 $[l,r,k]$,我们可以通过 $cnt$ 数组快速求出区间 $[l,r]$ 中每一位二进制表示中 $1$ 的个数。具体地,第 $j$ 位二进制表示中 $1$ 的个数为 $cnt[r][j]-cnt[l-1][j]$。

接下来,我们在区间 $[l,r]$ 上进行二分查找,每次取中点 $mid$:

• 如果区间 $[l,mid]$ 中每一位二进制表示中 $1$ 的个数都大于等于 $k$ 在对应位置上的二进制表示中 $1$ 的个数,说明 $mid$ 有可能是答案,我们继续在左半区间 $[l,mid]$ 上二分查找;
• 否则,说明 $mid$ 不可能是答案,我们在右半区间 $[mid+1,r]$ 上继续二分查找。

最后,我们检查二分查找的结果 $i$ 是否满足条件,如果满足则输出 $i$,否则输出 $-1$。

时间复杂度 $O((n+Q)\log n)$,空间复杂度 $O(n)$。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()def main():n, q = map(int, input().split())gems = list(map(int, input().split()))cnt = [[0] * 32 for _ in range(n + 1)]for i, val in enumerate(gems):for j in range(32):if val >> j & 1:cnt[i + 1][j] = cnt[i][j] + 1else:cnt[i + 1][j] = cnt[i][j]def check(left, right, k):bits = [0] * 32for j in range(32):bits[j] = cnt[right][j] - cnt[left - 1][j]for j in range(32):if k >> j & 1:if bits[j] == 0:return Falsereturn Truefor _ in range(q):l, r, k = map(int, input().split())left, right = l, rwhile left < right:mid = (left + right) >> 1if check(l, mid, k):right = midelse:left = mid + 1if check(l, left, k):print(left)else:print(-1)if __name__ == "__main__":main()

• Java

import java.io.*;
import java.util.*;public class Main {static int[][] cnt;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] input = br.readLine().split(" ");int n = Integer.parseInt(input[0]);int q = Integer.parseInt(input[1]);int[] gems = new int[n];input = br.readLine().split(" ");for (int i = 0; i < n; i++) {gems[i] = Integer.parseInt(input[i]);}cnt = new int[n + 1][32];for (int i = 0; i < n; i++) {for (int j = 0; j < 32; j++) {if ((gems[i] >> j & 1) == 1) {cnt[i + 1][j] = cnt[i][j] + 1;} else {cnt[i + 1][j] = cnt[i][j];}}}while (q-- > 0) {input = br.readLine().split(" ");int l = Integer.parseInt(input[0]);int r = Integer.parseInt(input[1]);int k = Integer.parseInt(input[2]);int left = l, right = r;while (left < right) {int mid = (left + right) >> 1;if (check(l, mid, k)) {right = mid;} else {left = mid + 1;}}if (check(l, left, k)) {System.out.println(left);} else {System.out.println(-1);}}}static boolean check(int left, int right, int k) {int[] bits = new int[32];for (int j = 0; j < 32; j++) {bits[j] = cnt[right][j] - cnt[left - 1][j];}for (int j = 0; j < 32; j++) {if ((k >> j & 1) == 1) {if (bits[j] == 0) {return false;}}}return true;}
}

• Cpp

#include <iostream>
#include <vector>using namespace std;vector<vector<int>> cnt;bool check(int left, int right, int k) {vector<int> bits(32);for (int j = 0; j < 32; j++) {bits[j] = cnt[right][j] - cnt[left - 1][j];}for (int j = 0; j < 32; j++) {if (k >> j & 1) {if (bits[j] == 0) {return false;}}}return true;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, q;cin >> n >> q;vector<int> gems(n);for (int i = 0; i < n; i++) {cin >> gems[i];}cnt.assign(n + 1, vector<int>(32));for (int i = 0; i < n; i++) {for (int j = 0; j < 32; j++) {if (gems[i] >> j & 1) {cnt[i + 1][j] = cnt[i][j] + 1;} else {cnt[i + 1][j] = cnt[i][j];}}}while (q--) {int l, r, k;cin >> l >> r >> k;int left = l, right = r;while (left < right) {int mid = (left + right) >> 1;if (check(l, mid, k)) {right = mid;} else {left = mid + 1;}}if (check(l, left, k)) {cout << left << '\n';} else {cout << -1 << '\n';}}return 0;
}

本题的关键是利用前缀和快速求出任意区间内每一位二进制表示中 $1$ 的个数,然后再结合二分查找找到满足条件的最小位置 $i$。预处理前缀和数组的时间复杂度为 $O(n\log C)$,其中 $C$ 为数据范围,本题中 $C=2^{30}$。每次二分查找的时间复杂度为 $O(\log n)$,共进行 $Q$ 次查询,因此总时间复杂度为 $O((n+Q)\log n)$。

🤍 03.K小姐的旅行计划

问题描述

K小姐计划去 $n$ 个城市旅行。这些城市之间有 $m$ 条双向道路相连,每条道路都有一个美景值 $w$。

K小姐希望选择一些道路,使得最终所有城市恰好被分成两个连通块。她可以获得所有被选择的道路的美景值之和。

现在K小姐想知道,她能获得的最大的美景值是多少?如果初始时这些城市已经形成了两个或更多的连通块,则输出 $-1$。

输入格式

第一行包含两个正整数 $n$ 和 $m$,分别表示城市的数量和道路的数量。

接下来 $m$ 行,每行包含三个正整数 $u,v,w$,表示城市 $u$ 和城市 $v$ 之间有一条美景值为 $w$ 的道路。

输出格式

输出一个整数,表示K小姐能获得的最大美景值。如果初始时这些城市已经形成了两个或更多的连通块,则输出 $-1$。

样例输入

3 3
1 2 4
2 3 3
1 3 2

样例输出

7

数据范围

• $2\le n\le 10^5$
• $0\le m\le 10^5$
• $1\le u,v\le n$
• $1\le w\le 10^9$

题解

本题可以使用 Kruskal 算法求解最小生成树。我们可以先将所有道路按照美景值从小到大排序,然后依次考虑每条道路:

• 如果当前道路连接的两个城市已经在同一个连通块中,那么选择这条道路会形成环,因此不能选择。
• 否则,选择这条道路,将两个城市所在的连通块合并。

在选择道路的过程中,我们需要记录最后一条被选择的道路的美景值 $maxv$。当算法结束时:

• 如果所有城市最终形成了一个连通块,那么我们需要删除最后一条被选择的道路,答案为 $total-maxv$,其中 $su$ 为所有道路的美景值之和。
• 如果所有城市最终形成了两个连通块,那么答案为 $su$。
• 如果所有城市最终形成了三个或更多的连通块,那么答案为 $-1$。

时间复杂度 $O(m\log m)$,空间复杂度 $O(n)$。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(10**6)def find(p, x):if p[x] != x:p[x] = find(p, p[x])return p[x]def main():n, m = map(int, input().split())roads = []total = 0for _ in range(m):u, v, w = map(int, input().split())roads.append((u, v, w))total += wroads.sort(key=lambda x: x[2])p = list(range(n + 1))cnt = nmaxv = 0for u, v, w in roads:u = find(p, u)v = find(p, v)if u != v:p[u] = vtotal -= wcnt -= 1maxv = max(maxv, w)if cnt == 1:print(total + maxv)elif cnt == 2:print(total)else:print(-1)if __name__ == "__main__":main()

• Java

import java.io.*;
import java.util.*;public class Main {static int[] p;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] input = br.readLine().split(" ");int n = Integer.parseInt(input[0]);int m = Integer.parseInt(input[1]);int[][] roads = new int[m][3];long total = 0;for (int i = 0; i < m; i++) {input = br.readLine().split(" ");roads[i][0] = Integer.parseInt(input[0]);roads[i][1] = Integer.parseInt(input[1]);roads[i][2] = Integer.parseInt(input[2]);total += roads[i][2];}Arrays.sort(roads, (a, b) -> a[2] - b[2]);p = new int[n + 1];for (int i = 1; i <= n; i++) {p[i] = i;}int cnt = n;int maxv = 0;for (int[] road : roads) {int u = find(road[0]);int v = find(road[1]);if (u != v) {p[u] = v;total -= road[2];cnt--;maxv = Math.max(maxv, road[2]);}}if (cnt == 1) {System.out.println(total + maxv);} else if (cnt == 2) {System.out.println(total);} else {System.out.println(-1);}}static int find(int x) {if (p[x] != x) {p[x] = find(p[x]);}return p[x];}
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;vector<int> p;int find(int x) {if (p[x] != x) {p[x] = find(p[x]);}return p[x];
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;vector<vector<int>> roads(m, vector<int>(3));long long total = 0;for (int i = 0; i < m; i++) {cin >> roads[i][0] >> roads[i][1] >> roads[i][2];total += roads[i][2];}sort(roads.begin(), roads.end(), [](const vector<int>& a, const vector<int>& b) {return a[2] < b[2];});p.resize(n + 1);for (int i = 1; i <= n; i++) {p[i] = i;}int cnt = n;int maxv = 0;for (auto& road : roads) {int u = find(road[0]);int v = find(road[1]);if (u != v) {p[u] = v;total -= road[2];cnt--;maxv = max(maxv, road[2]);}}if (cnt == 1) {cout << total + maxv << '\n';} else if (cnt == 2) {cout << total << '\n';} else {cout << -1 << '\n';}return 0;
}

写在最后

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。