本文介紹了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釘板的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，
