本文介紹了Codness釘板的處理方法，對(duì)大家解決問題具有一定的參考價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧！
問題描述
嘗試了解Codility NailingPlanks的解決方案。
問題鏈接：
https://app.codility.com/programmers/lessons/14-binary_search_algorithm/nailing_planks/
您將看到由N個(gè)整數(shù)組成的兩個(gè)非空數(shù)組A和B。
這些數(shù)組代表N個(gè)板。更準(zhǔn)確地說，A[K]是起點(diǎn)，
B[K]第K?板的末尾。接下來，您將看到一個(gè)由M個(gè)整數(shù)組成的非空數(shù)組C。這
數(shù)組表示M個(gè)釘子。更準(zhǔn)確地說，C[i]是
你可以把I?TH釘子釘進(jìn)去。如果存在一個(gè)釘子C[i]，我們稱板子(A[K]，B[K])為釘子
使得A[K]≤C[I]≤B[K]。目標(biāo)是找到必須使用的最少數(shù)量的釘子
直到所有的木板都釘好。換句話說，您應(yīng)該找到一個(gè)
值J，使得所有木板在僅使用第一個(gè)木板后都將被釘上釘子
J釘子。更準(zhǔn)確地說，對(duì)于每個(gè)板(A[K]，B[K])，使得0≤K
<；N，應(yīng)該存在一個(gè)釘子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;
}
}
我看不懂解決方案中標(biāo)有****的第99-102行。
我的問題是：
如果minIndexOrigin <= preIndex，則它將使用preIndex，
但如果preIndex沒有釘住當(dāng)前的木板怎么辦？
解決方案是否有一點(diǎn)錯(cuò)誤？
推薦答案
在這些行中處理的情況是，當(dāng)您發(fā)現(xiàn)存在一個(gè)釘住當(dāng)前板的索引時(shí)，該索引小于(或等于)我們需要能夠釘住另一個(gè)(先前分析過的)板所需的最低索引。在這種情況下，我們不需要進(jìn)一步查找當(dāng)前的板，因?yàn)槲覀冎溃?/p>
我們可以釘木板
我們可以使用不大于其他板真正需要的索引的索引。
因?yàn)槲覀冎粚?duì)不同木板所需的最少索引中的最大索引感興趣(即，”最差”木板的索引)，所以我們知道現(xiàn)在找到的索引不再重要：如果我們已經(jīng)知道將使用至少到preIndex的所有釘子，我們知道該集合中的一個(gè)釘子將釘住當(dāng)前的木板。我們只需退出循環(huán)并返回一個(gè)不會(huì)影響結(jié)果的”偽”索引。
注意調(diào)用循環(huán)中的效果：
result = getMinIndex(A[i], B[i], sortedNail, result);
在此賦值后，result將等于調(diào)用之前的result：這塊木板(A[i], B[i])可以用更早的釘子釘住，但我們并不真正關(guān)心是哪根釘子，因?yàn)槲覀冃枰雷顗牡那闆r，這是到目前為止由result反映的，并且所有達(dá)到該索引的釘子都已經(jīng)在將被錘打的釘子集中。
您可以將其與阿爾法-貝塔修剪進(jìn)行比較。
這篇關(guān)于Codness釘板的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，
