"左神算法中级班笔记,包含有序数组覆盖问题与捆绑交易问题的解法"
这篇笔记记录了两个算法问题的解决方案,分别对应于"左神算法中级班"的学习内容。第一个问题是关于有序数组的覆盖,第二个问题涉及苹果的捆绑交易,寻找最小袋数。
### 有序数组覆盖问题
给定一个有序数组`arr`,我们需要用长度为`L`的绳子覆盖数组中的点。这个问题可以通过遍历数组并利用二分查找来解决。关键在于找到距离当前点`i`最近且小于等于`arr[i]-L`的点。`nearestIndex`函数使用二分查找在指定范围内找到满足条件的最左位置。遍历数组,每次更新最大覆盖数`res`,最终返回`res`作为结果。
```java
// 长度为L的绳子最多覆盖几个点
public static int maxPoint(int[] arr, int L) {
int res = 1;
for (int i = 0; i < arr.length; i++) {
// 找出最左值得索引
int nearest = nearestIndex(arr, i, arr[i] - L);
res = Math.max(res, i - nearest + 1);
}
return res;
}
// 在arr[0..R]范围上,找满足>=value的最左位置
public static int nearestIndex(int[] arr, int R, int value) {
int L = 0;
int index = R;
// 二分查找
while (L < R) {
int mid = L + ((R - L) >> 1);
if (arr[mid] >= value) {
index = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
return index;
}
```
### 苹果的捆绑交易问题
小虎希望购买恰好`n`个苹果,但商店只有6个和8个一袋的苹果。目标是找到最少的袋数。这个问题可以通过数学规律和试探法来解决。首先,计算8个一袋苹果的袋数,然后处理6个一袋的情况。对于剩余的苹果,如果超过24个,则可以直接返回,因为25个苹果中可以分配24个给8个一袋的,相当于只剩1个。通过不断调整和尝试,可以找到最小的袋数。
```java
// 返回最小使用多少袋子
public static int minBags(int apple) {
if (apple < 0) {
return -1;
}
int bag6 = -1;
int bag8 = apple / 8;
// 具体逻辑...
}
```
这两个问题展示了在算法设计中如何利用有序性、二分查找以及数学规律来优化解决方案。在实际编程挑战和面试中,这样的技巧和思维方式是非常有价值的。