编程题

1.降序的子数组最大元素和

给你一个正整数组成的数组nums，返回nums中一个降序子数组的最大可能元素和。

子数组是数组中的一个连续数字序列。

已知子数组[nums l, nums l+1, … , nums r-1, nums r]，若对所有l (1<=i<r)，nums i>nums i+1都成立，则称这一子数组为降序子数组。注意，大小为1的子数组也视作降序子数组。

补充说明

1 <= nums.length <= 100

1<= nums[i]<= 100

示例1

输入

[50,10,20,30,5,10]

输出

60

说明

[50,10]是元素和最大的降序子数组，最大元素和为60。

示例2

输入

[50,30,20]

输出

100

说明
[50,30,20]是元素和最大的降序子数组，最大元素和为100。

题解

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] arr = new int[n];// temp 用于临时存储当前递减子序列的和int temp = 0;// sum 用于存储最大的递减子序列的和，最终结果int sum = 0;for (int i = 0; i < n; i++) {arr[i] = scanner.nextInt();}// ptrIndex 作为指针，遍历数组 arrint ptrIndex = 0;// 当指针 ptrIndex 还在数组范围内时，循环继续while (ptrIndex <= n - 1) {// 将当前指针指向的元素值赋给 temp，作为当前递减子序列的起始值temp = arr[ptrIndex];// 内层循环：寻找从 ptrIndex 开始的最长递减子序列while (ptrIndex < n - 1 && arr[ptrIndex] > arr[ptrIndex + 1]) {ptrIndex++;// 将新的元素值加到 temp 中，更新当前递减子序列的和temp += arr[ptrIndex];}// 递减子序列结束，指针向后移动一位，开始寻找下一个递减子序列ptrIndex++;//更新最大的递减子序列的和 sumif (sum < temp) {sum = temp;}}System.out.println(sum);scanner.close();}
}

2.覆盖房屋的最小加热半径(leetcode475)

冬季已经来临。你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在，给出位于一条水平线上的房屋houses和供暖器heaters的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

注意：

所有供暖器heaters都遵循你的半径标准，加热的半径也—样。

示例1

输入

[1,2,3],[2]

输出

1

示例2

输入

[1,2,3,4],[1,4]

输出

1

题解

import java.util.Arrays;public class Main {public int findRadius(int[] houses, int[] heaters) {// 1. 将供暖器位置数组排序，方便使用二分查找Arrays.sort(heaters);// 2. 初始化最小加热半径为 0int radius = 0;// 3. 遍历每个房屋for (int house : houses) {// 4. 使用二分查找找到距离当前房屋最近的供暖器位置int heaterIndex = findNearestHeater(heaters, house);// 5. 计算当前房屋需要的加热半径int currentRadius = Math.abs(heaters[heaterIndex] - house);// 6. 更新最小加热半径radius = Math.max(radius, currentRadius);}// 7. 返回最小加热半径return radius;}private int findNearestHeater(int[] heaters, int house) {int left = 0;int right = heaters.length - 1;int ans = 0; //存储下标while(left <= right){int mid = left + (right - left) / 2;if(heaters[mid] == house){return mid;} else if(heaters[mid] < house){left = mid + 1;} else {right = mid -1;}ans = left;}if (ans == 0) {return 0;  //房屋在供暖器左侧，第一个供暖器最近} else if (ans == heaters.length) {return heaters.length - 1; //房屋在所有供暖器右侧，最后一个供暖器最近} else {//比较房屋到左右两个供暖器的距离，选择最近的供暖器if(Math.abs(heaters[ans] - house) < Math.abs(heaters[ans -1] - house)){return ans;} else {return ans -1;}}}
}

3.鸡蛋掉落(leetcode887)

给你k枚相同的鸡蛋，并可以使用一栋从第1层到第n层共有n层楼的建筑。

已知存在楼层f，满足0<=f<=n，任何从高于f的楼层落下的鸡蛋都会碎，从f楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层x扔下（满足1<=x<=n)。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中重复使用这枚鸡蛋。

请你计算并返回要确定f确切的值的最小操作次数是多少？

补充说明

提示：

1<=k<=100

1<=n<=10^4

示例1

输入

1,2

输出

2

说明

输入：

k=1,n=2

输出：

2

解释：

鸡蛋从1楼掉落。如果它碎了，肯定能得出f=0。
否则，鸡蛋从2楼掉落。如果它碎了，肯定能得出f＝1。

如果它没碎，那么肯定能得出f=2。
因此，在最坏的情况下我们需要移动2次以确定f是多少。

示例2

输入

2,6

输出

3

示例3

输入

3,14

输出

4

题解

public class Main {public int superEggDrop(int k, int n) {// dp[i][j] 表示 i 个鸡蛋，j 层楼时，最坏情况下的最少尝试次数int[][] dp = new int[k + 1][n + 1];// 初始化：// 0 层楼，无论多少个鸡蛋，都不需要尝试for (int i = 1; i <= k; i++) {dp[i][0] = 0;}// 1 个鸡蛋，j 层楼，最坏情况要尝试 j 次for (int j = 1; j <= n; j++) {dp[1][j] = j;}// 状态转移：// 从 2 个鸡蛋，2 层楼开始计算for (int i = 2; i <= k; i++) {for (int j = 1; j <= n; j++) {dp[i][j] = Integer.MAX_VALUE; // 初始化为最大值// 二分查找优化尝试的楼层，寻找最优解int left = 1, right = j;while (left <= right) {int mid = left + (right - left) / 2;// 鸡蛋碎了：需要在 mid-1 层楼往下寻找，鸡蛋数量减少 1int broken = dp[i - 1][mid - 1];// 鸡蛋没碎：需要在 j-mid 层楼往上寻找，鸡蛋数量不变int notBroken = dp[i][j - mid];// 取最坏情况下的尝试次数int temp = Math.max(broken, notBroken) + 1;// 更新 dp[i][j]，取最小值dp[i][j] = Math.min(dp[i][j], temp);// 二分查找，调整方向if (broken > notBroken) {right = mid - 1; // 碎了的情况代价更大，尝试往低楼层找} else {left = mid + 1; // 没碎的情况代价更大，尝试往高楼层找}}}}// 返回 k 个鸡蛋，n 层楼时，最坏情况下的最少尝试次数return dp[k][n];}
}