Codility NailingPlanks(Codness钉板)
问题描述
尝试了解Codility NailingPlanks的解决方案。
问题链接: https://app.codility.com/programmers/lessons/14-binary_search_algorithm/nailing_planks/
您将看到由N个整数组成的两个非空数组A和B。 这些数组代表N个板。更准确地说,A[K]是起点, B[K]第K−板的末尾。 接下来,您将看到一个由M个整数组成的非空数组C。这 数组表示M个钉子。更准确地说,C[i]是 你可以把I−TH钉子钉进去。 如果存在一个钉子C[i],我们称板子(A[K],B[K])为钉子 使得A[K]≤C[I]≤B[K]。 目标是找到必须使用的最少数量的钉子 直到所有的木板都钉好。换句话说,您应该找到一个 值J,使得所有木板在仅使用第一个木板后都将被钉上钉子 J钉子。更准确地说,对于每个板(A[K],B[K]),使得0≤K <;N,应该存在一个钉子C[I],使得I<;J和A[K]≤C[I]≤ B[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
反映的,并且所有达到该索引的钉子都已经在将被锤打的钉子集中。
您可以将其与阿尔法-贝塔修剪进行比较。
这篇关于Codness钉板的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!
本文标题为:Codness钉板
基础教程推荐
- 设置 bean 时出现 Nullpointerexception 2022-01-01
- 降序排序:Java Map 2022-01-01
- “未找到匹配项"使用 matcher 的 group 方法时 2022-01-01
- 减少 JVM 暂停时间 >1 秒使用 UseConcMarkSweepGC 2022-01-01
- Java Keytool 导入证书后出错,"keytool error: java.io.FileNotFoundException &拒绝访问" 2022-01-01
- FirebaseListAdapter 不推送聊天应用程序的单个项目 - Firebase-Ui 3.1 2022-01-01
- 在 Libgdx 中处理屏幕的正确方法 2022-01-01
- 如何使用 Java 创建 X509 证书? 2022-01-01
- 无法使用修饰符“public final"访问 java.util.Ha 2022-01-01
- Java:带有char数组的println给出乱码 2022-01-01