今天在力扣看到一道題，順手寫了下，用到了二分法和貪心演算法，這里記錄一下思路，
二分法查找，也稱折半查找，是一種在有序陣列中查找特定元素的搜索演算法，查找程序可以分為以下步驟：
（1）首先，從有序陣列的中間的元素開始搜索，如果該元素正好是目標元素（即要查找的元素），則搜索程序結束，否則進行下一步，
（2）如果目標元素大于或者小于中間元素，則在陣列大于或小于中間元素的那一半區域查找，然后重復第一步的操作，
（3）如果某一步陣列為空，則表示找不到目標元素，
案例：
題目：從一個排好序的陣列中找到固定值的下標，
代碼：
function binary_search(arr, key) {
var low = 0,
high = arr.length - 1;
while (low <= high) {
var mid = parseInt((high + low) / 2);
if (key == arr[mid]) {
return mid;
} else if (key > arr[mid]) {
low = mid + 1;
} else if (key < arr[mid]) {
high = mid - 1;
} else {
return -1;
}
}
}
從上方的代碼中，大致了解了二分法是個什么東西，核心是減少回圈次數，用最少的方法，回傳準確的結果，節約記憶體，提高效率，
下面是進階題目：
傳送帶上的包裹必須在 D 天內從一個港口運送到另一個港口，
傳送帶上的第 i 個包裹的重量為 weights[i]，每一天，我們都會按給出重量的順序往傳送帶上裝載包裹，我們裝載的重量不會超過船的最大運載重量，
回傳能在 D 天內將傳送帶上的所有包裹送達的船的最低運載能力，
示例 1：
輸入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5 輸出：15 解釋： 船舶最低載重 15 就能夠在 5 天內送達所有包裹，如下所示： 第 1 天：1, 2, 3, 4, 5 第 2 天：6, 7 第 3 天：8 第 4 天：9 第 5 天：10 請注意，貨物必須按照給定的順序裝運，因此使用載重能力為 14 的船舶并將包裝分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允許的，
示例 2：
輸入：weights = [3,2,2,4,1,4], D = 3 輸出：6 解釋： 船舶最低載重 6 就能夠在 3 天內送達所有包裹，如下所示： 第 1 天：3, 2 第 2 天：2, 4 第 3 天：1, 4
示例 3：
輸入：weights = [1,2,3,1,1], D = 4 輸出：3 解釋： 第 1 天：1 第 2 天：2 第 3 天：3 第 4 天：1, 1
下面是我的答案：
var shipWithinDays = function(weights, D) {
let l = Math.max(...weights),r = weights.reduce((n,m) => n + m);
while(l < r){
let r1 = (r - l) % 2 == 1 ? (r - l - 1) / 2: (r - l) / 2;
let mid = l + r1;
if(getWeight(weights,mid) <= D){
r = mid;
}else{
l = mid + 1;
}
}
function getWeight(arr,k){
let sum = 1;
let s = 0;
for(let i = 0; i < arr.length; i++){
if(s + arr[i] <= k){
s += arr[i];
}else{
s = arr[i];
sum++;
}
}
return sum;
}
return l;
};
思路是以陣列里的最大值為初始值，總和值為結尾值，用二分法來查詢，減少次數，有興趣可以看下代碼研究下，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/280521.html
標籤：JavaScript
下一篇：前端快取API請求資料