牛客網--位元組跳動面試題--萬萬沒想到之抓捕孔連順
博客說明
文章所涉及的資料來自互聯網整理和個人總結，意在于個人學習和經驗匯總，如有什么地方侵權，請聯系本人洗掉，謝謝！
來源
鏈接：萬萬沒想到之抓捕孔連順 來源：牛客網
題目
我叫王大錘，是一名特工，我剛剛接到任務：在位元組跳動大街進行埋伏，抓捕恐怖分子孔連順，和我一起行動的還有另外兩名特工，我提議
-
我們在位元組跳動大街的N個建筑中選定3個埋伏地點，
-
為了相互照應，我們決定相距最遠的兩名特工間的距離不超過D，
我特喵是個天才! 經過精密的計算，我們從X種可行的埋伏方案中選擇了一種，這個方案萬無一失，顫抖吧，孔連順！
……
萬萬沒想到，計劃還是失敗了，孔連順化妝成小龍女，混在cosplay的隊伍中逃出了位元組跳動大街，只怪他的偽裝太成功了，就是楊過本人來了也發現不了的！
請聽題：給定N（可選作為埋伏點的建筑物數）、D（相距最遠的兩名特工間的距離的最大值）以及可選建筑的坐標，計算在這次行動中，大錘的小隊有多少種埋伏選擇，
注意：
-
兩個特工不能埋伏在同一地點
-
三個特工是等價的：即同樣的位置組合(A, B, C) 只算一種埋伏方法，不能因“特工之間互換位置”而重復使用
輸入描述:
第一行包含空格分隔的兩個數字 N和D(1?≤?N?≤?1000000; 1?≤?D?≤?1000000)
第二行包含N個建筑物的的位置，每個位置用一個整數（取值區間為[0, 1000000]）表示，從小到大排列（將位元組跳動大街看做一條數軸）
輸出描述:
一個數字，表示不同埋伏方案的數量，結果可能溢位，請對 99997867 取模
輸入例子1:
4 3
1 2 3 4
輸出例子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)
思路
1、首先確定范圍，計算排列組合，從第三個數開始判斷，因為必須有三個數嘛，判斷違法的次數，如果當前數字不合法，那么違法的次數加一，那么每次的次數為（當前第幾個數-違法次數）x（當前第幾個數-違法次數）/ 2
2、累加每次范圍的次數，就可以得到全部的了
代碼
import java.util.Scanner;
/**
* @author guizimo
* @date 2020/7/17 10:04 下午
*/
public class zijie2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
int d = scanner.nextInt();
int[] position = new int[n];
scanner.nextLine();
for (int i = 0; i < n; i++) {
position[i] = scanner.nextInt();
}
run(n, d, position);
}
}
public static void run(int n, int d, int[] position) {
long sum = 0L;
long mod = 99997867;
for (int i = 0, j = 0; i < n; i++) {
//從第三個開始判斷，判斷是否違法，如果違法j++
while (i >= 2 && position[i] - position[j] > d) {
j++;
}
//計算合法的次數，n(n-i)/2
sum += (long) (i - j) * (long) (i - j - 1) / 2;
}
System.out.println(sum % mod);
}
}
感謝
牛客網
位元組跳動
以及勤勞的自己
關注公眾號： 歸子莫，獲取更多的資料，還有更長的學習計劃
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/140860.html
標籤：Java
上一篇：牛客網--位元組跳動面試題--萬萬沒想到之聰明的編輯
下一篇：delphi 呼叫網頁腳本