1、(數組連續和):
這段代碼是解決“數組連續和”的問題。它提供了一個Java類Main
,其中包含main
方法和getResult
方法,用于計算給定數組中有多少個連續區間的和大于等于給定值x
。
main
方法首先讀取數組的長度n
和閾值x
,然后讀取數組nums
中的元素。接著,調用getResult
方法并打印結果。
getResult
方法使用前綴和數組preSum
來高效地計算連續區間的和。前綴和數組preSum[i]
表示數組中前i
個元素的和。通過遍歷數組并使用雙指針技術(在這里是兩個索引l
和r
),代碼可以找到所有滿足條件的連續區間。當當前區間的和大于等于x
時,由于數組中的數都是正整數,可以確定從當前右指針r
開始向左直到數組末尾的所有區間的和也都大于等于x
。因此,可以將計數器count
增加相應的數量,并將左指針l
向右移動以繼續尋找下一個區間。
2、(求最多可以派出多少支團隊):
這段代碼是解決“求最多可以派出多少支團隊”的問題。它提供了一個Java類Main
,其中包含main
方法和getResult
方法,用于計算在給定最低能力值要求下,最多可以組成多少支團隊。
main
方法首先讀取總人數n
,然后讀取每個人的能力值數組power
,最后讀取團隊要求的最低能力值minPower
。接著,調用getResult
方法并打印可以派出的團隊數量。
getResult
方法首先對能力值數組進行升序排序。然后使用雙指針技術,從數組的兩端開始,先計算能夠單獨組隊的人數(即能力值大于等于minPower
的人數)。接著,從左指針l
開始,嘗試與右指針r
配合,形成能力值總和大于等于minPower
的團隊。如果兩個人的能力值之和小于minPower
,則左指針l
向右移動,尋找下一個可能的團隊組合。
package OD223;import java.util.Scanner;/*** @description 數組連續和* @level 6* @score 100*//*** 題目描述* 給定一個含有N個正整數的數組, 求出有多少個連續區間(包括單個正整數), 它們的和大于等于x。* <p>* 輸入描述* 第一行兩個整數N x(0 < N <= 100000, 0 <= x <= 10000000)* <p>* 第二行有N個正整數(每個正整數小于等于100)。* <p>* 輸出描述* 輸出一個整數,表示所求的個數。* <p>* 注意:此題對效率有要求,暴力解法通過率不高,請考慮高效的實現方式。*/
// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);//數組個數int n = sc.nextInt();//需要大于等于xint x = sc.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = sc.nextInt();}System.out.println(getResult(nums, x));}//有多少個連續數組和大于等于xpublic static long getResult(int[] nums, int x) {long len = nums.length;long count = 0;//因為有效率要求,不能每次都求和,用前綴和來表示long[] preSum = new long[(int) (len + 1)];//preSum[i]表示前面i個數的和for (int i = 1; i <= len; i++) {preSum[i] = preSum[i - 1] + nums[i - 1];}//while循環int l = 0;int r = 1;while (r <= len) {long sum = preSum[r] - preSum[l];if (sum >= x) {//[l,r]區間的和已經大于x了,則[l,r,....len-1]區間的和必定大于x (都是正整數)count += len - r + 1;//窗口滑動l++;r = l + 1;} else {r++;}}return count;}}
package OD226;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;/*** @description 求最多可以派出多少支團隊* @level 5* @score 100*//*** 題目描述* 用數組代表每個人的能力,一個比賽活動要求參賽團隊的最低能力值為N,每個團隊可以由1人或者2人組成,且1個人只能參加1個團隊,計算出最多可以派出多少只符合要求的團隊。* <p>* 輸入描述* 第一行代表總人數,范圍1-500000* 第二行數組代表每個人的能力* 數組大小,范圍1-500000* 元素取值,范圍1-500000* 第三行數值為團隊要求的最低能力值,范圍1-500000* 輸出描述* 最多可以派出的團隊數量*/
// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);//代表總人數int n = sc.nextInt();//每個人的能力值int[] power = new int[n];for (int i = 0; i < n; i++) {power[i] = sc.nextInt();}//團隊要求最低能力值int minPower = sc.nextInt();System.out.println(getResult(power, minPower));}//最多可以派出多少團隊 能一個人滿足的就一個人組隊public static int getResult(int[] power, int minPower) {int n = power.length;//升序排列Arrays.sort(power);//雙指針int l = 0;int r = n - 1;int count = 0;//先記錄單人組隊while (r >= l && power[r] >= minPower) {count++;r--;}//把小于<=minPower的兩兩分組 盡可能多while (l < r) {int sum = power[l] + power[r];//如果此時無法組隊,則l位置的不可能組隊成功if (sum < minPower) {l++;} else {//組隊成功count++;l++;r--;}}return count;}
}