携程笔试0313
模拟
1
2
3
4
5
6
7
8
9
10
11
12
13
| import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
int cnt = 0;
for (int i = 0; i < s.length(); i += cnt) {
System.out.print(s.charAt(i));
cnt++;
}
}
}
|
贪心
将数字按从大到小排序，然后每次将当前值+索引+1就是得分，比较所有得分取最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int t = 0; t < T; t++) {
int n = sc.nextInt();
long[] nums = new long[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextLong();
}
Arrays.sort(nums);
long ans = 0;
for (int i = n - 1; i >= 0; i--) {
ans = Math.max(ans, nums[i] + (n - i));
}
System.out.println(ans);
}
}
}
|
java让数组降序排序还需要将数组转换成Integer型的，非常麻烦。
1
2
3
4
5
6
7
8
9
10
|
int[] arr = {10, 5, 3, 8, 12, 1};
Integer[] integerArray = Arrays.stream(arr)
.boxed()
.toArray(Integer[]::new);
Arrays.sort(integerArray, Collections.reverseOrder());
|
滑动窗口
- 质因子个数计算： 对于数组中的每个数，我们需要计算它的质因子个数。我们可以用一个类似筛法的算法来预处理每个数的质因子个数，这样在处理输入数据时就能迅速得到每个数的质因子个数。
- 滑动窗口： 我们需要找到一个长度为 k 的子数组，将它删除，剩下的数组的权值和最大。由于删除子数组后的数组权值和最大化，实际上等价于找到一个长度为 k 的子数组，其质因子个数和最小，然后从总和中减去这个最小值。
具体步骤：
- 首先，计算每个数的质因子个数，并存储到一个数组 weight 中。
- 计算整个数组的权值和。
- 使用滑动窗口来找到长度为 k 的子数组，其权值和最小。
- 最后，输出总权值和减去最小子数组权值和的结果。
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
| import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
int[] primeCnt = calPrimeCnt(10000);
long total = 0;
int[] weight = new int[n];
for (int i = 0; i < n; i++) {
weight[i] = primeCnt[nums[i]];
total += weight[i];
}
long cur = 0;
for (int i = 0; i < k; i++) {
cur += weight[i];
}
long minWeight = cur;
for (int i = k; i < n; i++) {
cur = cur - weight[i - k] + weight[i];
minWeight = Math.min(minWeight, cur);
}
System.out.println(total - minWeight);
}
public static int[] calPrimeCnt(int maxNum) {
int[] cnt = new int[maxNum + 1];
for (int i = 2; i <= maxNum; i++) {
if (cnt[i] == 0) {
for (int j = i; j <= maxNum; j += i) {
cnt[j]++;
}
}
}
return cnt;
}
}
|
- 时间复杂度：O(n + maxNum * log(maxNum))
- 空间复杂度：O(n + maxNum)
并查集
核心是计算树中有多少条简单路径的权值为偶数，路径的权值是路径上所有节点权值的最大公约数（GCD）。通过并查集（Union-Find）将所有具有相同特性（即权值为偶数）的节点归为同一组，减少计算复杂度。
- 初始化并查集：创建一个并查集 g，每个节点初始时是自己的父节点。
- 遍历树的每条边：对每条边 (x, y)，判断节点 x 和节点 y 的权值是否都为偶数。如果都为偶数，则将它们合并成一个连通块，因为路径上的 GCD 会是偶数。
- 统计每个连通块中的偶数节点数量：使用 find 操作找到每个节点所属的连通块，然后统计每个连通块中偶数节点的数量。
- 计算每个连通块的路径数量：对于每个连通块，如果该连通块中有 k 个偶数节点，则该连通块贡献的路径数是 C(k, 2) + k，即所有可能的两节点路径数加上每个节点单独的路径数。
- 输出最终结果：输出所有连通块贡献的路径数的和，得到最终的答案。
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
| import java.util.*;
public class Main {
static int[] father;
public static int find(int x) {
if (father[x] == x) return x;
return father[x] = find(father[x]);
}
public static void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
father[rootX] = rootY;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
father = new int[n + 1];
for (int i = 1; i <= n; i++) {
father[i] = i;
}
for (int i = 1; i < n; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
if (arr[u - 1] % 2 == 0 && arr[v - 1] % 2 == 0) {
union(u, v);
}
}
long[] cnt = new long[n + 1];
long answer = 0;
for (int i = 1; i <= n; i++) {
if (arr[i - 1] % 2 == 0) {
int root = find(i);
cnt[root]++;
}
}
for (int i = 1; i <= n; i++) {
if (cnt[i] > 0) {
answer += cnt[i] * (cnt[i] - 1) / 2 + cnt[i];
}
}
System.out.println(answer);
}
}
|
总结
携程的题目也不难，除了最后一道题不太会写。
并查集（Disjoint Set Union, DSU）
并查集是一种数据结构，用来处理一些不交集（disjoint sets）的合并及查询问题。并查集的基本操作包括 查找（Find）和 合并（Union）。它的主要应用场景是处理一些元素的合并和查询，例如 连接问题，连通性问题 等。
主要操作：
- **
find(x)**：查找元素 x 所在的集合的代表元素（根节点），即查找一个元素属于哪个集合。
- **
union(x, y)**：将两个集合合并成一个集合，即将元素 x 和 y 所在的两个集合合并。
- **
connected(x, y)**：判断两个元素是否在同一个集合中（即是否连通）。
关键技巧：
- 路径压缩（Path Compression）：在执行
find 操作时，将路径上的所有节点都直接连接到根节点，以加速后续的查找操作。
- 按秩合并（Union by Rank/Size）：在执行
union 操作时，总是将较小的树合并到较大的树下，以保持树的平衡，减少树的高度，从而减少查找的时间复杂度。
这两个技巧可以大大提高并查集的效率，确保其操作时间接近常数时间。
并查集的应用场景
并查集主要用于 动态连通性问题，也就是说，当我们面对一组元素，我们需要处理这些元素间的合并和查询操作时，适合用并查集。以下是一些典型问题：
连通性问题：判断图中两个节点是否连通。
- 比如在一个图中，判断两个点是否在同一个连通分量中。
图的连通分量数量：找出一个无向图中的连通分量数量。
动态连通性问题：在一个动态变化的图中，处理边的增删操作，快速判断两个节点是否连通。
网络问题：在某些情况下，多个计算机之间的网络连接问题也可以通过并查集解决，判断哪些计算机在同一个网络中。
集合合并问题：在一些集合合并的应用中，使用并查集可以帮助我们高效地处理合并和查询操作。
并查集代码模板（包括路径压缩和按秩合并）
以下是一个典型的并查集模板，包含路径压缩和按秩合并：
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
| public class UnionFind {
private int[] father;
private int[] rank;
public UnionFind(int n) {
father = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
father[i] = i;
rank[i] = 0;
}
}
public int find(int x) {
if (father[x] != x) {
father[x] = find(father[x]);
}
return father[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
father[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
father[rootX] = rootY;
} else {
father[rootY] = rootX;
rank[rootX]++;
}
}
}
public boolean connected(int x, int y) {
return find(x) == find(y);
}
}
|
代码说明：
- 初始化：我们通过一个
father 数组表示每个节点的父节点，rank 数组表示树的深度（用于按秩合并）。每个节点最初的父节点是它自己，秩是 0。
- **
find(x)**：查找操作，使用路径压缩优化。每次递归查找时，将路径上的节点直接连接到根节点，以加速未来的查找。
- **
union(x, y)**：合并操作，使用按秩合并。通过比较两个集合的秩，将较小的树合并到较大的树下，从而保持树的平衡，减少树的深度。
- **
connected(x, y)**：判断 x 和 y 是否在同一个集合中，只需要比较它们的根节点是否相同。
复杂度分析：
- 时间复杂度：由于路径压缩和按秩合并的使用，
find 和 union 操作的时间复杂度接近 **O(α(n))**，其中 α(n) 是阿克曼函数的反函数，它增长非常慢，接近常数时间。因此，通常可以认为这两个操作是常数时间。
- 空间复杂度：并查集的空间复杂度是 **O(n)**，主要用于存储
father 和 rank 数组。
总结：
- 并查集 是一种非常高效的数据结构，尤其适合解决 动态连通性 问题，常用于图算法、集合合并等问题。
- 通过 路径压缩 和 按秩合并 技巧，可以使得
find 和 union 操作接近常数时间。
- 应用场景 包括：图的连通性问题、集合合并问题、网络连通问题等。
通过这种方法，很多与连通性相关的问题都可以高效地解决。