字节跳动-建筑物组合滑动窗口溢出问题

JAY.LIN 收录于未分类

2025-03-12 约 789 字预计阅读 2 分钟

https://bing.ee123.net/img/rand?artid=146198320

字节跳动 —— 建筑物组合(滑动窗口+溢出问题)

原题描述：

题目精炼 ：

给定N个建筑物的位置和一个距离D，选取3个建筑物作为埋伏点，找出所有可能的建筑物组合，使得每组中的建筑物之间的最大距离不超过D。最后，输出不同埋伏方案的数量并对99997867取模。

识别问题 ：

由于此题的建筑物是一个单调递增的数组（单调性），并且使用 “同向双指针” 来维护一段区间，保证（判断条件）：

1）right - left +1 >= 3

2）buildings[right] - buildings[left] <= D

3）right < buildings.length 或者 left < buildings.lengrh - 2

因此，我们可以使用“滑动窗口”来求解。

滑动窗口解题思路：

1）左右指针初始化

int left = 0;
int right = 2;

2）满足条件进窗口

注意，要先判断right是否小于数组长度，否则会越界

while(right < buildings.length && buildings[right] - buildings[left] <= D){
    right++;
}

3）更新结果

此处涉及到求解组合数量问题，为了防止一段区间内，子集重复的问题，每次以buildings[left]为基准，在剩余的buildings中选取两个进行组合，公式为

$https://latex.csdn.net/eq?C%28n%2C%202%29%20%3D%20%5Cbinom%7Bn%7D%7B2%7D%20%3D%20%5Cfrac%7Bn%21%7D%7B2%21%28n-2%29%21%7D%20%3D%20%5Cfrac%7Bn%28n-1%29%7D%7B2%7D$

但是，此处涉及到两个很大的整数相乘，会出现溢出的问题，因此我们可以使用更大的整数类型，将n*(n-1)转换为long类型，并对每次累加后的结果%99997867 防止溢出。

int n = right - left - 1;
long p =((long)n *(n-1))>>1;
count =(count + p)%99997867;

当因为right>=buildings.length而跳出循环时，说明此时没有更大的值了，收集完结果后要对right–，使得right始终停留在最右边界，从而可以继续判断，等待left缩小窗口

if(right >= buildings.length){
    right--;
}

4）出窗口

left++;

其中，进窗口，更新结果，出窗口是一个不断循环的过程，因此，最终代码为：

import java.util.Scanner;
public class ByteDance_BuildingCombinations {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int D = in.nextInt();
        int[] buildings = new int[N];
        for (int i = 0; i < N; i++) {
            buildings[i] = in.nextInt();
        }
        long count = slide(buildings,D);

        System.out.println(count);
    }

    public static long slide(int[] buildings, int D){
        long count = 0;
        int left = 0;
        int right = 2;

        while(left < buildings.length - 2){
            while(right < buildings.length && buildings[right] - buildings[left] <= D){
                right++;
            }

            int n = right - left - 1;
            long p =((long)n *(n-1))>>1;
            count =(count + p)%99997867;

            if(right >= buildings.length){
                right--;
            }
            left++;
        }
        return count;
    }
}

目录

字节跳动-建筑物组合滑动窗口溢出问题

字节跳动 —— 建筑物组合(滑动窗口+溢出问题)