字节跳动笔试-万万没想到之抓捕孔连顺

我叫王大锤,是一名特工。我刚刚接到任务:在字节跳动大街进行埋伏,抓捕恐怖分子孔连顺。和我一起行动的还有另外两名特工,我提议

我们在字节跳动大街的N个建筑中选定3个埋伏地点。
为了相互照应,我们决定相距最远的两名特工间的距离不超过D。
我特喵是个天才! 经过精密的计算,我们从X种可行的埋伏方案中选择了一种。这个方案万无一失,颤抖吧,孔连顺!
……
万万没想到,计划还是失败了,孔连顺化妆成小龙女,混在cosplay的队伍中逃出了字节跳动大街。只怪他的伪装太成功了,就是杨过本人来了也发现不了的!

请听题:给定N(可选作为埋伏点的建筑物数)、D(相距最远的两名特工间的距离的最大值)以及可选建筑的坐标,计算在这次行动中,大锤的小队有多少种埋伏选择。
注意:

  1. 两个特工不能埋伏在同一地点
  2. 三个特工是等价的:即同样的位置组合(A, B, C) 只算一种埋伏方法,不能因“特工之间互换位置”而重复使用

输入描述:

第一行包含空格分隔的两个数字 N和 D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000)

第二行包含N个建筑物的的位置,每个位置用一个整数(取值区间为[0, 1000000])表示,从小到大排列(将字节跳动大街看做一条数轴)

输出描述:

一个数字,表示不同埋伏方案的数量。结果可能溢出,请对 99997867 取模
输入例子1:

4 3
1 2 3 4
1
2

输出例子1:

4

例子说明1:

可选方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)

输入例子2:

5 19
1 10 20 30 50

输出例子2:

1

例子说明2:

可选方案 (1, 10, 20)

算法思路:

使用双指针窗口滑动),通过固定窗口的末尾位置,可以保证窗口移动过程不会出现重复,然后从末尾位置前面的若干个数中(假设有 nums 个,并且最小的数也满足 pos[end] - pos[start] <= d )选取两个数(加上末尾位置的数共三个),这则是一个组合问题,即 nums 个数中选两个,C(nums,2) == nums * (nums - 1) / 2,最后再加起来就是最终答案。

代码实现:

public class Test2 {
    /*
     4 3
     1 2 3 4
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = sc.nextInt();
        sc.nextLine();
        int[] pos = new int[n];
        for (int i = 0; i < n; i++) {
            pos[i] = sc.nextInt();
        }
        sc.nextLine();
        sc.close();
        // 固定窗口的末尾位置,这样就可以保证窗口移动过程不会出现重复,
        // 因为下一次判断至少和上次的末尾位置不一样。
        // 然后从末尾位置的前面选取两个位置,加上末尾正好三个位置
        int start = 0;
        long ans = 0;
        // 末尾从下标 2 开始
        for (int end = 2; end < n; end++) {
            // 因为每次固定窗口的末尾位置,且数组升序,
            // 越往右找越能找到一个位置的数 满足 pos[end] - pos[start] <= d
            while (start < end && (pos[end] - pos[start]) > d) {
                start++;
            }
            // 除了末尾的位置,其前面有 nums 个数可选,
            long nums = end - start;
            // 组合问题,为 C(nums,2) == nums * (nums - 1) / 2
            ans += nums * (nums - 1) / 2;
        }
        System.out.println(ans % 99997867);

        //======================
        // 回溯算法,可求具体的可选方案
        // dfs(0, pos, d);
        // System.out.println(res.size());
        // res.forEach(list -> {
        //     list.forEach(integer -> System.out.print(integer + " "));
        //     System.out.println();
        // });
    }

    private static List<List<Integer>> res = new LinkedList<>();
    private static List<Integer> path = new LinkedList<>();

    public static void dfs(int idx, int[] pos, int d) {
        if (path.size() == 3 && path.get(2) - path.get(0) <= d) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int i = idx; i < pos.length; i++) {
            path.add(pos[i]);
            dfs(i + 1, pos, d);
            path.remove(path.size() - 1);
        }
    }
}

Q.E.D.


以无限为有限,以无法为有法