携程集团

携程集团

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算法：

1. 队列：每个队列中的元素包含当前的位置 (x, y)，已经走过的步数，以及当前收集到的宝物总价值。
2. 广度优先搜索：每次从当前格子向四个方向扩展，每次访问到一个新格子时，累加宝物值。并且游游可以重复访问某些格子，从而获取更多的宝物值。

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 个数回到集合中。
• 目标：进行尽可能多的操作，最后留下最少的数字。

思路：

1. 贪心策略：每次尽可能选择符合条件的数字，并删除最小值。为了实现这个目标，数组中的数字需要排序，这样我们可以容易地找到符合条件的一组数字进行删除操作。

2. 分组操作：我们从排序后的数组中选择连续的 m 个数字，确保这些数字的最大值和最小值的差小于等于 k。如果找到这样的组，就执行删除最小值的操作，并继续尝试处理剩下的数组。

3. 终止条件：当无法找到符合条件的 m 个数时，结束操作，输出剩余的数字数量。

贪心算法步骤：

1. 排序：将数组从小到大排序，便于后续进行分组处理。
2. 遍历数组：每次从排序后的数组中找到符合条件的一组 m 个数（最大值与最小值之差小于等于 k）。
3. 删除最小值：从当前组中删除最小值，并将剩余的 m-1 个数放回集合中。
4. 继续处理：重复这个过程直到无法再找到符合条件的组。

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();
    }
}

优化思路：

1. 双指针方法：我们可以使用双指针（滑动窗口）来优化遍历过程。在排序的数组中，使用一个窗口来维护符合条件的 m 个数的范围，这样可以减少重复的判断，提升效率。

   • 左指针 left 指向当前窗口的起始位置，右指针 right 向右扩展，直到窗口中的最大值和最小值之差大于 k。
   • 当窗口内的数字个数大于等于 m 时，可以进行删除操作，移除窗口中的最小值（即 left 指针指向的数字），然后更新窗口。
   • 一次遍历：我们可以在一次遍历中通过滑动窗口的方式，确定能够删除的数字，优化代码的时间复杂度。

   可以优化的方向：

2. 减少窗口管理的复杂度：当前的双指针滑动窗口已经将遍历过程压缩到了 O(n)，但每次满足条件后，我们会立即删除一个数字并移动左指针。我们可以改为直接跳过一段已经确定的符合条件的数字，避免不必要的重复操作。

3. 减少删除操作次数：可以通过直接从窗口的末尾往回检查，找到能够删除的最小值段，而不是每次删除一个最小值。

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 个人的能力值为 \(a_i\) 。

现在将 n 个人排成一排，游游有 k 次训练的机会，让不超过 \(l\) 个连续的人能力人变为任意值。

如果合唱团的实力是所有人能力值的最小值。你可以帮助游游求出合唱团的实力的最大值是多少吗？

输入描述 第一行三个整数 n, m, k, 表示人数,训练次数,每次训练的最大长度 第二行个整数 \(a_i\) ,表示第 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单位时间后，每个人都在办公室。

这是一个匹配问题，涉及到员工从他们的初始位置出发，先去通行证的地点拿到通行证，然后再前往办公室。目标是找到最优的匹配方案，使所有员工都能以最短的时间到达办公室。

问题分解：

1. 每个员工 a[i] 需要先前往某个通行证 b[i] 的位置，拿到通行证后，再去办公室 p。
2. 每个员工去取通行证和再去办公室的总时间为：|a[i] - b[j]| + |b[j] - p|，即从员工的位置到通行证的位置的时间，加上从通行证位置到办公室的时间。
3. 我们需要为每个员工找到一个最优的通行证分配方案，使得所有员工到达办公室的最大时间最小化。

思路：

1. 排序：将员工的位置 a[i] 和通行证的位置 b[i] 都进行排序，这样可以减少不必要的匹配尝试。
2. 二分查找：使用二分法来猜测一个最小的可能的最大时间 t，然后判断是否存在一种分配方案，使得所有员工在 t 时间内到达办公室。
3. 双指针匹配：使用双指针方法进行匹配，判断当前的猜测时间 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();
    }
}