#水清# 学校

APP 内打开

【技术-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%：

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 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%

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 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 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%