外观
携程集团
约 4164 字大约 14 分钟
2025-02-27
携程集团
2个小时：4道编程题
第一题：dfs？
题目描述
一个 n * m 的网格图 ，左上角为 (0, 0)，右下角为 (n-1, m-1)，格子 (i, j) 有价值为 a[i][j] = j + i * m 的宝物。
游游从左上角 (0,0) 为起点，每一步可以走到上下左右四个方向的相邻格子。
每到达一个格子，就能获取价值为 a[i][j] 宝物。需要注意的是，在到达某个格子获取宝物后，这个格子的宝物会在 游游离开这个格子之后 再次刷新。
现在给出一个整数 k，表示游游最多走 k 步。
问：游游最多能获得多少价值的宝物？
输入描述 第一行包含一个整数 q，表示询问个数。
接下来 q 行，每行三个整数 n m k (1<=n, m, k<=10000, n+m >=2)，表示矩阵大小和限制步数。
输出描述 输出包含 q 行，每行一个整数，表示每次询问的结果。
示例 输入 1 2 2 5 输出 12
说明：
2*2 的网格图 ，其中 a[0][0] =0, a[0][1]=1. a[1][0]=2. a[1][1]=3.
因为k=5, 只能走5步，
最优方案：（0, 0）->(1,0)->(1,1)->(1.0)->(1,1)->(1,0)
宝物总和是 12核心问题：
- 步数限制：游游只能走
k步，因此应当利用这些步数，通过某些高价值格子反复来回获取宝物。 - 不需要走新的路径：游游在步数有限的情况下，可以通过来回走动在同一个格子上获取更多宝物值，而不是一直走新路径。
解决方案：
我们可以使用广度优先搜索（BFS），并在 k 步内找到最多能够访问的格子，同时每次访问格子时都累加宝物值。
重新设计的BFS算法：
- 队列：每个队列中的元素包含当前的位置
(x, y)，已经走过的步数，以及当前收集到的宝物总价值。 - 广度优先搜索：每次从当前格子向四个方向扩展，每次访问到一个新格子时，累加宝物值。并且游游可以重复访问某些格子，从而获取更多的宝物值。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class TreasureCollector {
// 定义方向数组，分别表示上下左右移动
private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 计算格子的宝物价值
private static int getValue(int i, int j, int m) {
return j + i * m;
}
// 使用BFS来计算游游在最多 k 步内能够获取的最大宝物值
private static int getMaxTreasure(int n, int m, int k) {
// BFS队列，存储当前位置及已走的步数和当前获得的宝物值
Queue<int[]> queue = new LinkedList<>();
// 初始位置为 (0, 0)，步数为 0，初始宝物价值为 getValue(0, 0)
queue.offer(new int[]{0, 0, 0, getValue(0, 0, m)}); // 格式为 [x, y, steps, currentTreasure]
int maxTreasure = 0;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
int steps = current[2];
int currentTreasure = current[3];
// 更新最大宝物值
maxTreasure = Math.max(maxTreasure, currentTreasure);
// 如果已经达到最大步数，停止搜索
if (steps == k) continue;
// 向四个方向移动
for (int[] direction : DIRECTIONS) {
int newX = x + direction[0];
int newY = y + direction[1];
// 判断是否越界
if (newX >= 0 && newX < n && newY >= 0 && newY < m) {
// 每次到达新格子时，宝物值累加
queue.offer(new int[]{newX, newY, steps + 1, currentTreasure + getValue(newX, newY, m)});
}
}
}
return maxTreasure;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int q = scanner.nextInt(); // 输入的询问个数
for (int i = 0; i < q; i++) {
int n = scanner.nextInt(); // 矩阵行数
int m = scanner.nextInt(); // 矩阵列数
int k = scanner.nextInt(); // 最大步数
// 计算最大宝物价值
int result = getMaxTreasure(n, m, k);
System.out.println(result);
}
scanner.close();
}
}过了 26% ...
第二题：贪心
n个数字 构成了一个可重集合，进行以下操作： 每一次操作你都可以任选集合中 最大值-最小值<=k 的 m 个数字，然后删去这 m 个数字中的最小值，并把其他的数字放回集合中。 若无法选出符合条件的 m个数，则无法继续操作。
你可以无限次进行这个操作，直到没法操作为止。
要使得最后留下的数最少，请求出进行上面的操作后留下的最少的数字数量。
输入描述：第一行三个整数n，m，k。第二行n个整数代表初始可重集合中的元素a_i。 输出描述：一个整数，代表操作后留下的最少的数字数量。 示例1输入： 4 3 3 1 2 3 6 示例1输出： 3 示例1说明：最多只能进行一次操作，即选中 1 2 3，然后删去 1。 剩余的数为 2 3 6，由于最大值和最小值之差大于 3，因此无法继续操作。
题目解析：
- 操作规则：每次你可以选择集合中最大值与最小值差值小于等于
k的m个数，删除其中的最小值，剩下的m-1个数回到集合中。 - 目标：进行尽可能多的操作，最后留下最少的数字。
思路：
贪心策略：每次尽可能选择符合条件的数字，并删除最小值。为了实现这个目标，数组中的数字需要排序，这样我们可以容易地找到符合条件的一组数字进行删除操作。
分组操作：我们从排序后的数组中选择连续的
m个数字，确保这些数字的最大值和最小值的差小于等于k。如果找到这样的组，就执行删除最小值的操作，并继续尝试处理剩下的数组。终止条件：当无法找到符合条件的
m个数时，结束操作，输出剩余的数字数量。
贪心算法步骤：
- 排序：将数组从小到大排序，便于后续进行分组处理。
- 遍历数组：每次从排序后的数组中找到符合条件的一组
m个数（最大值与最小值之差小于等于k）。 - 删除最小值：从当前组中删除最小值，并将剩余的
m-1个数放回集合中。 - 继续处理：重复这个过程直到无法再找到符合条件的组。
import java.util.*;
public class MinimizeRemainingNumbers {
public static int minimizeRemaining(int n, int m, int k, int[] nums) {
// 先将数组排序
Arrays.sort(nums);
// 用于记录已处理的元素索引
boolean[] removed = new boolean[n];
int remaining = n;
// 遍历整个数组，尝试找到符合条件的组
for (int i = 0; i <= n - m; i++) {
// 如果当前数字已经被删除，跳过
if (removed[i]) continue;
// 判断从 i 开始的 m 个数是否符合条件
if (nums[i + m - 1] - nums[i] <= k) {
// 符合条件，将最小值删掉
removed[i] = true;
remaining--; // 删除最小值，减少一个剩余的数字
}
}
return remaining;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入数据
int n = sc.nextInt(); // 数字个数
int m = sc.nextInt(); // 每次选择的数字个数
int k = sc.nextInt(); // 最大值和最小值之差的限制
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt(); // 输入数字
}
// 计算并输出结果
int result = minimizeRemaining(n, m, k, nums);
System.out.println(result);
sc.close();
}
}优化思路：
双指针方法：我们可以使用双指针（滑动窗口）来优化遍历过程。在排序的数组中，使用一个窗口来维护符合条件的
m个数的范围，这样可以减少重复的判断，提升效率。- 左指针
left指向当前窗口的起始位置，右指针right向右扩展，直到窗口中的最大值和最小值之差大于k。 - 当窗口内的数字个数大于等于
m时，可以进行删除操作，移除窗口中的最小值（即left指针指向的数字），然后更新窗口。
- 左指针
一次遍历：我们可以在一次遍历中通过滑动窗口的方式，确定能够删除的数字，优化代码的时间复杂度。
可以优化的方向：
减少窗口管理的复杂度：当前的双指针滑动窗口已经将遍历过程压缩到了
O(n)，但每次满足条件后，我们会立即删除一个数字并移动左指针。我们可以改为直接跳过一段已经确定的符合条件的数字，避免不必要的重复操作。减少删除操作次数：可以通过直接从窗口的末尾往回检查，找到能够删除的最小值段，而不是每次删除一个最小值。
import java.util.*;
public class MinimizeRemainingNumbers {
public static int minimizeRemaining(int n, int m, int k, int[] nums) {
// 先将数组排序
Arrays.sort(nums);
int remaining = n; // 剩余的数字个数
int left = 0; // 左指针
while (left <= n - m) { // 保证至少能选出 m 个数
int right = left + m - 1; // 找到符合条件的 m 个数的末尾
// 检查这 m 个数的最大值和最小值之差是否小于等于 k
if (nums[right] - nums[left] <= k) {
remaining--; // 删除最小值
left++; // 移动左指针
} else {
left++; // 当前不满足条件，直接跳过
}
}
return remaining;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入数据
int n = sc.nextInt(); // 数字个数
int m = sc.nextInt(); // 每次选择的数字个数
int k = sc.nextInt(); // 最大值和最小值之差的限制
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt(); // 输入数字
}
// 计算并输出结果
int result = minimizeRemaining(n, m, k, nums);
System.out.println(result);
sc.close();
}
}第三题：二分
游游有n 个人组成的合唱团，第 i 个人的能力值为 ai 。
现在将 n 个人排成一排，游游有 k 次训练的机会，让不超过 l 个连续的人能力人变为任意值。
如果合唱团的实力是所有人能力值的最小值。你可以帮助游游求出合唱团的实力的最大值是多少吗？
输入描述 第一行三个整数 n, m, k, 表示人数,训练次数,每次训练的最大长度 第二行个整数 ai ,表示第 i 个人的能力值
输出描述 一个整数表示合唱团实力最大值。
示例： 输入：
8 2 3
7 4 11 2 1 4 7 5输出：
5说明：让区间[2,4],[4,6]变成11，这样可以使最小值为5
import java.util.Scanner;
public class ChorusPower {
// 判断是否能够通过不超过 k 次训练将最小的实力提升到 target
public static boolean canAchieveMinimum(int[] a, int n, int k, int l, int target) {
int needed = 0; // 记录所需训练次数
int i = 0;
while (i < n) {
if (a[i] < target) {
needed++;
i += l; // 跳过 l 个位置
} else {
i++; // 当前值满足条件，继续下一个
}
if (needed > k) { // 如果已经超过可用训练次数，返回 False
return false;
}
}
return needed <= k;
}
// 二分搜索合唱团实力的最大值
public static int maxChorusPower(int n, int k, int l, int[] a) {
int left = Integer.MAX_VALUE;
int right = Integer.MIN_VALUE;
// 找到数组中的最小值和最大值，作为二分查找的边界
for (int value : a) {
left = Math.min(left, value);
right = Math.max(right, value);
}
right++; // 由于二分查找的右边界需要是一个不可行的值，故设为 right + 1
// 二分查找
while (left < right) {
int mid = (left + right + 1) / 2;
if (canAchieveMinimum(a, n, k, l, mid)) {
left = mid; // 可以实现，尝试更大的值
} else {
right = mid - 1; // 不可以实现，尝试更小的值
}
}
return left;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取输入
int n = sc.nextInt(); // 队伍人数
int k = sc.nextInt(); // 可进行的训练次数
int l = sc.nextInt(); // 每次训练影响的人数
int[] a = new int[n]; // 每个人的实力值
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt(); // 读取每个人的实力
}
// 计算并输出结果
int result = maxChorusPower(n, k, l, a);
System.out.println(result);
sc.close();
}
}第四题：二分
n名员工，这n名员工的初始位置在a[i]，办公室的位置在p。
有k个通行证，这k个通行证的位置在b[i]，每个位置有且只有一个通行证。这个位置的通行证如果被拿走了，这里就没有通行证了，其他员工无法在这个位置拿到通行证了。
员工上班之前必须拿到通行证，每个通行证只能供一个人使用，一个位置上最多只有一个通行证。员工的初始位置可能和通行证的初始位置相同。
每名员工必须有通行证才能进办公室(员工先要去b[i]拿到通行证，然后再去办公室地点p)，员工移动一单位距离需要花费一单位时间。
请问这个员工都达到办公室的最短时间是多少。
输入描述： 第一行三个整数n,k,p。 第二行n个整数a[i]。 第三行k个整数b[i] 输出描述: 2 4 50 20 100 60 10 40 80 输出： 50 说明： 位置在20的人应该拿走位于40的通行证，然后将其带到位于位置在50的办公室。他花了30单位时间的时间。位置在100的人可以拿起位置在80的通行证，并随身去办公室。 他花了50单位时间。 因此，在50单位时间后，每个人都在办公室。
这是一个匹配问题，涉及到员工从他们的初始位置出发，先去通行证的地点拿到通行证，然后再前往办公室。目标是找到最优的匹配方案，使所有员工都能以最短的时间到达办公室。
问题分解：
- 每个员工
a[i]需要先前往某个通行证b[i]的位置，拿到通行证后，再去办公室p。 - 每个员工去取通行证和再去办公室的总时间为：
|a[i] - b[j]| + |b[j] - p|，即从员工的位置到通行证的位置的时间，加上从通行证位置到办公室的时间。 - 我们需要为每个员工找到一个最优的通行证分配方案，使得所有员工到达办公室的最大时间最小化。
思路：
- 排序：将员工的位置
a[i]和通行证的位置b[i]都进行排序，这样可以减少不必要的匹配尝试。 - 二分查找：使用二分法来猜测一个最小的可能的最大时间
t，然后判断是否存在一种分配方案，使得所有员工在t时间内到达办公室。 - 双指针匹配：使用双指针方法进行匹配，判断当前的猜测时间
t是否足够让所有员工到达办公室。
import java.util.Arrays;
import java.util.Scanner;
public class MinimizeMaxTime {
// 判断给定的时间限制 t 下，是否可以让每个员工在时间 t 内拿到通行证并到达办公室
public static boolean canReachWithinTime(int[] employees, int[] passes, int n, int k, int p, int t) {
int j = 0; // 用来遍历通行证的位置
// 尝试为每个员工分配通行证
for (int i = 0; i < n; i++) {
// 找到一个符合时间限制的通行证
while (j < k && Math.abs(employees[i] - passes[j]) + Math.abs(passes[j] - p) > t) {
j++;
}
// 如果没有找到符合时间限制的通行证，返回 false
if (j >= k) {
return false;
}
j++; // 分配当前通行证给员工 i
}
return true; // 所有员工都能在时间 t 内拿到通行证并到达办公室
}
// 计算员工们到达办公室所需的最短时间
public static int minimizeMaxTime(int n, int k, int p, int[] employees, int[] passes) {
// 将员工的位置和通行证的位置都排序
Arrays.sort(employees);
Arrays.sort(passes);
// 二分查找最大时间 t 的范围
int left = 0;
int right = Integer.MAX_VALUE;
while (left < right) {
int mid = (left + right) / 2;
if (canReachWithinTime(employees, passes, n, k, p, mid)) {
right = mid; // 能实现，尝试更短的时间
} else {
left = mid + 1; // 不能实现，增加时间限制
}
}
return left;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取输入
int n = sc.nextInt(); // 员工人数
int k = sc.nextInt(); // 通行证数量
int p = sc.nextInt(); // 办公室的位置
int[] employees = new int[n]; // 员工初始位置
int[] passes = new int[k]; // 通行证位置
for (int i = 0; i < n; i++) {
employees[i] = sc.nextInt(); // 员工位置
}
for (int i = 0; i < k; i++) {
passes[i] = sc.nextInt(); // 通行证位置
}
// 计算并输出结果
int result = minimizeMaxTime(n, k, p, employees, passes);
System.out.println(result);
sc.close();
}
}