【技术-Java】Java后端携程笔试(2021年9月9日晚)
赛码网,三道编程题。提前二十多分钟交的卷,,第二题通过率36%想了半天想不出来哪出问题了,裂开。
第一题: 目录命令
【时间限制】: 3000MS 内存限制: 589824KB
【题目描述】: 你需要编写一个程序来模拟目录的操作,一开始,你在根目录"\",一共有两种命令: ● cd s: s为一个目录名,表示从当前工作目录的路径进入名为s的目录。
特别地,"cd .."(即s=="..")表示返回上一级目录,若当前已为根目录,则无视该次操作。数据保证若s不为"..",则一定为小写字母组成的长度不超过10的字符串。 ● pwd: 表示查看当前工作目录的路径,你需要输出这个路径。 【输入描述】 第一个行是一个整数n,表示一共会有n个操作。 接下来每行是一条命令,命令的种类为问题描述中的二种之一。 注意,测试用例中cd s的操作,中间有空格。 输出描述 对于每个"pwd"命令,你需要单行输出当前的工作路径。 【样例输入】 7 cd a cd b pwd cd .. pwd cd .. pwd
【样例输出】 \a\b \a \ (提示 1<=n<=300)
通过率100%:
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
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Scanner sc = new Scanner(System.in);
List<String> list = new ArrayList<>();
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
String line = sc.nextLine();
String[] strs = line.split(" ");
if ("cd".equals(strs[0])) {
if ("..".equals(strs[1])) {
if (!list.isEmpty()) {
list.remove(list.size() - 1);
}
} else {
list.add("\\" + strs[1]);
}
} else if ("pwd".equals(strs[0])) {
if (list.isEmpty()) {
System.out.println('\\');
} else {
StringBuilder sb = new StringBuilder();
for (String s : list) {
sb.append(s);
}
System.out.println(sb);
}
}
}
}
}
第二题:分段
时间限制: 3000MS 内存限制: 589824KB
【题目描述】 有一个长度为n的序列A,序列中的第i个数为A[i] (1<=i<=n),现在你可以将序列分成至多连续的k段。
对于每一段,我们定义这一段的不平衡度为段内的最大值减去段内的最小值。显然,对于长度为1的段,其不平衡度为0。
对于一种合法的分段方式(即每一段连续且不超过k段),我们定义这种分段方式的不平衡度为每一段的不平衡度的最大值。
现在你需要找到不平衡度最小的分段方式,输出这种分段方式的不平衡度即可。 【输入描述】 第一行两个空格隔开的整数n,k,分别表示序列的长度和最多可分成的段数。 第二行是n个用空格隔开的整数,第i个数表示A[i]的值。 【输出描述】 一行一个整数,表示最小的不平衡度。 样例输入 5 3 3 5 5 2 5 样例输出 2 提示 数据范围:1<=n<=100000, 1<=A[i]<=100000 输入样例1 5 3 3 5 5 2 5 输出样例1 2 解释 最终分为[3 5 5] [2] [5],该种分段方式的不平衡度为2。
这道题我只AC了36%
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
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
int m = Integer.parseInt(s[0]); //m个数
int n = Integer.parseInt(s[1]); //最多分成n段
String[] strs = br.readLine().split(" ");
List<Integer> list = new ArrayList<>();
list.add(Integer.parseInt(strs[0]));
for (int i = 1; i < m; i++) {
if (strs[i].equals(strs[i - 1])) {
continue;
}
list.add(Integer.parseInt(strs[i]));
}
System.out.println(minValue(list, n));
}
public static int minValue(List<Integer> nums, int n) {
if (n >= nums.size()) {
return 0;
}
int[] dif = new int[nums.size() - 1];
for (int i = 1; i < nums.size(); i++) {
dif[i - 1] = Math.abs(nums.get(i) - nums.get(i - 1));
}
Arrays.sort(dif);
return dif[dif.length - n]; // 输出第n大的即可
}
}
第三题:消除连续的1
时间限制: 3000MS 内存限制: 589824KB
【题目描述】 现在给你一个长度为n的01序列,你可以通过消除连续的1的序列来获取一定的分数。 题目中将给你若干个长度和分数的对应关系,你需要正确求解出对应的答案。 例如:现在给你一个长度为12的01序列111111011111。 现在给你如下可以获取得分的消除方式: 消除三个连续的1,获取得分10 消除四个连续的1,获取得分15 对于前面的六个连续的1,你的消除方案有两种: 消除一次连续的四个1,获得得分15,或者进行两次连续的三个1消除,获取得分20. 对于后面的五个连续的1,你有两种消除方案: 消除一次连续的四个1,获得得分15,或者消除一次连续的三个1,获得得分10 上述方案中可以获得的最大分数是20 + 15 = 35. 你的任务就是设法获得最大的消除分数。 请注意:不一定需要把所有的1的消除完毕,我们的目标是最大化分数而不是最大化消除个数。 【输入描述】 第一行两个空格隔开的正整数n,m,分别表示01串的长度和消除规则的数量。 接下来一行字符串长度为n,每个字符只能是0或者1中的一种。 接下来m行,每行两个空格隔开的正整数k, x,为消除连续的k个1可以获得的分数x 输出描述 输出可以获得的最大分数。 样例输入 11 2 11111101111 3 10 4 15 样例输出 35 提示 n <= 100000, m <= 100 保证对于每个规则,k和x都在[1, 100]之间。
这道题是完全背包的变种,通过率100%
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
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String ss = br.readLine();
String[] sss = ss.split(" ");
int line = Integer.parseInt(sss[1]);
char[] nums = br.readLine().toCharArray(); // 01序列
int[][] wvs = new int[line + 1][2];
for (int i = 1; i <= line; i++) {
String[] wv = br.readLine().split(" ");
wvs[i][0] = Integer.parseInt(wv[0]);
wvs[i][1] = Integer.parseInt(wv[1]);
}
List<Integer> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] == '0') {
continue;
}
int W = 0;
while (i < nums.length && nums[i] == '1') {
W++;
i++;
}
list.add(W);
i--;
}
int res = 0;
for (Integer W : list) {
res += maxValue(W, wvs);
}
System.out.println(res);
}
public static int maxValue(int V, int[][] wv) {
int N = wv.length - 1;
int[] dp = new int[V + 1];
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
if (j >= wv[i][0]) {
dp[j] = Math.max(dp[j - wv[i][0]] + wv[i][1], dp[j]);
}
}
}
return dp[V];
}
}
最后祝大家机会多多,offer多多!
喜欢的点个赞,谢谢,手残党码了半天字;