笔试笔试2024携程春季笔试真题
玦尘本文为原创内容，转载请注明出处并附带原文链接。感谢您的尊重与支持！
1.游游的you子串
题目描述
游游拿到了一个字符串，她想重排这个字符串后，使得该字符串包含尽可能多的”you”连续子串。你能帮帮她吗？
输入描述
一个仅包含小写字母的字符串，长度不超过10^5
输出描述
一个整数，表示重排后的字符串最多包含多少个”you”子串。
输入示例
yyoouuuu
输出示例
2
提示信息
重新排列过后，最多包含2个”you”子串
时间限制：c/c++：1s， 其他语言：2s
参考答案：
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.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
int countY = 0, countO = 0, countU = 0;
for (char c : s.toCharArray()) {
if (c == 'y') {
countY++;
} else if (c == 'o') {
countO++;
} else if (c == 'u') {
countU++;
}
}
int minCount = Math.min(countY, Math.min(countO, countU));
System.out.println(minCount);
}
}
|
2.游游的树上操作
题目描述
游游拿到了一棵树，她每次操作可以选择两个相邻的节点使得它们同时加 1。游游想知道能否用有限的操作次数使得所有节点的奇偶性相同？如果可以，请输出“Yes”，如果不行，请输出“No”。
共有q次询问。
输入描述
第一行输入一个整数q，代表询问次数。
对于每次询问，首先第一行输入一个正整数n，代表树的节点数量；第二行输入n个正整数ai，代表每个节点的初始权值；接下来n-1行，每行输入两个正整数u、v，代表节点u和节点v有一条边连接。
1 <= n <= 10^5
1 <= ai <= 10^9
1 <= u, v <= n
保证q次询问的所有节点数量之和不大于 200000。
输出描述
输出共q行，表示每次询问的结果，如果能变成奇偶一致（要么全奇数，要么全偶数）则输出“Yes”，否则输出“No”
输入示例
2
4
1 2 2 3
1 2
2 3
3 4
4
1 2 3 3
1 2
2 3
2 4
输出示例
Yes
No
提示信息
时间限制：c/c++：1s，java/go：3s，其他语言：8s。
参考答案：
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
| import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; ++i) {
nums[i] = sc.nextInt();
}
for (int i = 0; i < n - 1; ++i) {
sc.nextInt();
sc.nextInt();
}
int oddCount = 0;
for (int num : nums) {
if (num % 2 != 0) {
oddCount++;
}
}
if (oddCount % 2 == 0 || (n - oddCount) % 2 == 0) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
}
|
3.游游的数组推平
题目描述
游游拿到了一个数组，她每次操作可以任选一个元素加 1 或者减 1。游游想知道，将所有元素都变成和ai相等需要操作最少多少次？你需要回答i∈[0,n-1]的结果。i为数组的下标。
输入描述
第一行输入一个正整数n ∈ [1, 10^5]，代表数组的大小。第二行输入n个正整数ai ∈ [1, 10^9]，代表数组的元素。
输出描述
输出n行，分别代表i ∈ [0,n-1]的结果。
输入示例
3
2 1 4
输出示例
3
4
5
提示信息
数组变成[2,2,2]需要操作 3 次，变成[1,1,1]需要操作 4 次，变成[4,4,4]需要操作 5 次。
每次操作都是独立的。
时间限制：c/c++：1s，其他语言：3s。
参考答案：
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
| import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] queries = new int[n];
for (int i = 0; i < n; i++) {
queries[i] = sc.nextInt();
}
int[] sortedArr = Arrays.copyOf(queries, n);
Arrays.sort(sortedArr);
long[] prefixSum = new long[n + 1];
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + sortedArr[i];
}
long[] ans = new long[n];
for (int i = 0; i < n; i++) {
int x = queries[i];
int t = lowerBound(sortedArr, x);
long leftCost = 1L * x * t - prefixSum[t];
long rightCost = prefixSum[n] - prefixSum[t] - 1L * x * (n - t);
ans[i] = leftCost + rightCost;
}
for (long res : ans) {
System.out.println(res);
}
}
private static int lowerBound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
|
4.游游的数组压缩
题目描述
游游拿到了一个数组，她希望你将数组相同的相邻元素压缩在一起。你能帮帮她吗？
给定的数组是已经被压缩了一部分的形式，请你继续将其压缩到不能再压缩为止。举个例子，数组[2,3,5,5,5,3]会被压缩成[2(1),3(1),5(3),3(1)]。
输入描述
一个字符串，代表待压缩的数组。字符串长度n ∈ [2, 10^5]，且括号内的数ai ∈ [1, 10^9]。数组中每个元素的值域范围是bi ∈ [-10^9, 10^9]
输出描述
一个字符串，表示压缩后的数组。
输入示例
[1(2),1(1),-1(3)]
输出示例
[1(3),-1(3)]
提示信息
输入的字符串一定包含[]。含义见题意描述。
时间限制：c/c++：1s，其他语言：3s。
参考答案：
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
| import java.util.*;
public class Main {
public static void main(String[] args) {
final long INF = (long) 1e10;
Scanner sc = new Scanner(System.in);
String xxx = sc.nextLine();
String[] ops = xxx.substring(1, xxx.length() - 1).split(",");
List<String> opsList = new ArrayList<>(Arrays.asList(ops));
opsList.add(INF + "(0)");
List<String> res = new ArrayList<>();
long cur = INF;
long count = 0;
for (String s : opsList) {
if (s.isEmpty()) break;
int j = s.indexOf('(');
long x = Long.parseLong(s.substring(0, j));
long y = Long.parseLong(s.substring(j + 1, s.length() - 1));
if (x == cur || cur == INF) {
cur = x;
count += y;
} else {
res.add(cur + "(" + count + ")");
cur = x;
count = y;
}
}
System.out.print("[");
System.out.print(String.join(",", res));
System.out.println("]");
}
}
|
