java - Codility NailingPlanks
问题描述
试图了解 Codility NailingPlanks 的解决方案。
问题链接: https ://app.codility.com/programmers/lessons/14-binary_search_algorithm/nailing_planks/
给定两个由 N 个整数组成的非空数组 A 和 B。这些阵列代表 N 个木板。更准确地说,A[K] 是第 K 个木板的开始,B[K] 是结束。
接下来,给定一个由 M 个整数组成的非空数组 C。这个数组代表 M 个钉子。更准确地说,C[I] 是您可以敲入第 I 个钉子的位置。
如果存在钉子 C[I] 使得 A[K] ≤ C[I] ≤ B[K],我们说木板 (A[K], B[K]) 被钉牢。
目标是找到在钉完所有木板之前必须使用的最少钉子数量。换句话说,您应该找到一个值 J,这样所有木板都将在仅使用前 J 个钉子后被钉牢。更准确地说,对于每个满足 0 ≤ K < N 的木板 (A[K], B[K]),应该存在一个钉子 C[I],满足 I < J 和 A[K] ≤ C[I] ≤乙[K]。
解决方案链接: https ://github.com/ZRonchy/Codility/blob/master/Lesson12/NailingPlanks.java
import java.util.Arrays;
class Solution {
public int solution(int[] A, int[] B, int[] C) {
// the main algorithm is that getting the minimal index of nails which
// is needed to nail every plank by using the binary search
int N = A.length;
int M = C.length;
// two dimension array to save the original index of array C
int[][] sortedNail = new int[M][2];
for (int i = 0; i < M; i++) {
sortedNail[i][0] = C[i];
sortedNail[i][1] = i;
}
// use the lambda expression to sort two dimension array
Arrays.sort(sortedNail, (int x[], int y[]) -> x[0] - y[0]);
int result = 0;
for (int i = 0; i < N; i++) {//find the earlist position that can nail each plank, and the max value for all planks is the result
result = getMinIndex(A[i], B[i], sortedNail, result);
if (result == -1)
return -1;
}
return result + 1;
}
// for each plank , we can use binary search to get the minimal index of the
// sorted array of nails, and we should check the candidate nails to get the
// minimal index of the original array of nails.
public int getMinIndex(int startPlank, int endPlank, int[][] nail, int preIndex) {
int min = 0;
int max = nail.length - 1;
int minIndex = -1;
while (min <= max) {
int mid = (min + max) / 2;
if (nail[mid][0] < startPlank)
min = mid + 1;
else if (nail[mid][0] > endPlank)
max = mid - 1;
else {
max = mid - 1;
minIndex = mid;
}
}
if (minIndex == -1)
return -1;
int minIndexOrigin = nail[minIndex][1];
//find the smallest original position of nail that can nail the plank
for (int i = minIndex; i < nail.length; i++) {
if (nail[i][0] > endPlank)
break;
minIndexOrigin = Math.min(minIndexOrigin, nail[i][1]);
// we need the maximal index of nails to nail every plank, so the
// smaller index can be omitted ****
if (minIndexOrigin <= preIndex) // ****
return preIndex; // ****
}
return minIndexOrigin;
}
}
我不明白****
解决方案中标有 的第 99-102 行。
我的问题是:
如果minIndexOrigin <= preIndex
, 那么它将使用preIndex
, 但如果preIndex
没有钉住当前的木板怎么办?
解决方案有一点错误吗?
解决方案
在这些行中处理的情况是,当您发现有一个钉住当前木板的索引时,该索引小于(或等于)我们需要能够钉另一个(先前分析的)木板的最低索引。在这种情况下,我们不需要进一步寻找当前的木板,因为我们知道:
- 我们可以钉木板
- 我们可以使用一个不大于我们真正需要用于另一个木板的索引的索引。
由于我们只对不同木板所需的最小索引中的最大索引感兴趣(即“最差”木板的索引),我们知道我们现在找到的索引不再重要:如果我们已经知道我们将至少使用所有的钉子preIndex
,我们知道该组中的一个钉子将钉在当前的木板上。我们可以退出循环并返回一个不会影响结果的“虚拟”索引。
注意调用循环中的效果:
result = getMinIndex(A[i], B[i], sortedNail, result);
在这个赋值之后,result
将等于result
调用之前的值:这块木板(A[i], B[i])
可以用更早的钉子钉住,但我们并不真正关心是哪个钉子,因为我们需要知道最坏的情况,即到现在为止反映result
,并且该索引之前的所有钉子都已经在将被锤击的钉子组中。
您可以将其与 alpha-beta 修剪进行比较。
推荐阅读
- datetime - 为什么 df.to_records 会在 datetime 是字符串时产生包装时间
- javascript - 使用 React 的 useReducer() 异步获取数据
- swift - 在 UIRepresentable 中向 MapKit 添加注释
- mysql - SQL 查询When Then 和 Count
- batch-file - SourceSafe 创建子项目并通过批处理文件脚本将文件添加到特定的项目目录中
- r - 根据近似的多个值过滤向量
- python - 从雅虎财经下载基础数据
- python - Python 输入和输出?
- python - 模块导入在 python 控制台(pycharm)中有效,但在终端上无效
- c# - 如何防止算术溢出破坏类的内部状态?