系列文章目錄

算法及數據結構系列 - BFS算法

---

二分查找

框架思路

int binarySearch(int[] nums, int target) {int left = 0, right = ...;while(...) {int mid = left + (right - left) / 2;if (nums[mid] == target) {...} else if (nums[mid] < target) {left = ...} else if (nums[mid] > target) {right = ...}}return ...;
}

計算 mid 時需要防止溢出，代碼中 left + (right - left) / 2 就和 (left + right) / 2 的結果相同，但是有效防止了 left 和 right 太大直接相加導致溢出。

經典題型

二分查找

給定一個 n 個元素有序的（升序）整型數組 nums 和一個目標值 target ，寫一個函數搜索 nums 中的 target，如果目標值存在返回下標，否則返回 -1。

class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length - 1;while(left <= right){int mid = left + (right - left)/2;if(nums[mid] == target){return mid;}else if (nums[mid] > target){right = mid - 1;}else{left = mid + 1;}}return -1;}
}

尋找左側邊界

注意: 當 val 不存在時，得到的索引恰好是比 val 大的最小元素索引。

int left_bound(int[] nums, int target) {if (nums.length == 0) return -1;int left = 0;int right = nums.length; // 注意while (left < right) { // 注意int mid = (left + right) / 2;if (nums[mid] == target) {right = mid;} else if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid; // 注意}}return left;
}

尋找右側邊界

int right_bound(int[] nums, int target) {if (nums.length == 0) return -1;int left = 0, right = nums.length;while (left < right) {int mid = (left + right) / 2;if (nums[mid] == target) {left = mid + 1; // 注意} else if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid;}}return left - 1; // 注意
}

刷題

875. 愛吃香蕉的珂珂

珂珂喜歡吃香蕉。這里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警衛已經離開了，將在 H 小時后回來。

珂珂可以決定她吃香蕉的速度 K （單位：根/小時）。每個小時，她將會選擇一堆香蕉，從中吃掉 K 根。如果這堆香蕉少于 K 根，她將吃掉這堆的所有香蕉，然后這一小時內不會再吃更多的香蕉。

珂珂喜歡慢慢吃，但仍然想在警衛回來前吃掉所有的香蕉。

返回她可以在 H 小時內吃掉所有香蕉的最小速度 K（K 為整數）。

提示： 吃每一堆分別要幾小時;尋找左側邊界

class Solution {public int minEatingSpeed(int[] piles, int H) {Arrays.sort(piles);int left = 1, right = piles[piles.length - 1] + 1;while(left < right){int mid = left + (right - left)/2;if(canFinish(mid, piles, H)){right = mid;}else{left = mid + 1;}}return left;}public boolean canFinish(int k, int[] piles, int H){long tmpHour = 0;for(int i = 0; i< piles.length;i++){tmpHour += (long)(piles[i] / k);if(piles[i] % k > 0){tmpHour ++;}}if(tmpHour <= H){return true;}else{return false;}}
}

1011. 在 D 天內送達包裹的能力

傳送帶上的包裹必須在 D 天內從一個港口運送到另一個港口。

傳送帶上的第 i 個包裹的重量為 weights[i]。每一天，我們都會按給出重量的順序往傳送帶上裝載包裹。我們裝載的重量不會超過船的最大運載重量。

返回能在 D 天內將傳送帶上的所有包裹送達的船的最低運載能力。

示例：

輸入：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) 是不允許的。 s

class Solution {public int shipWithinDays(int[] weights, int D) {if(weights.length == 0){return 0;}int len = weights.length;int left = weights[0], right = (weights[0] + weights[len -1]) * len / 2 + 1;while(left < right){int mid = left + (right - left)/2;if(canFinish(weights, D, mid)){right = mid;}else{left = mid + 1;}}return left;}public boolean canFinish(int[] w, int D, int cap){int i = 0;for (int day = 0; day < D; day++) {int maxCap = cap;while ((maxCap -= w[i]) >= 0) {i++;if (i == w.length)return true;}}return false;}
}

392. 判斷子序列

給定字符串 s 和 t ，判斷 s 是否為 t 的子序列。

你可以認為 s 和 t 中僅包含英文小寫字母。字符串 t 可能會很長（長度 ~= 500,000），而 s 是個短字符串（長度 <=100）。

字符串的一個子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對位置形成的新字符串。（例如，"ace"是"abcde"的一個子序列，而"aec"不是）。

class Solution {public boolean isSubsequence(String s, String t) {int fromIndex = 0;for(int i = 0; i < s.length(); i++){char tmp = s.charAt(i);int j = fromIndex;for(; j < t.length(); j++){if(t.charAt(j) == tmp){fromIndex = j + 1;break;}}if(j == t.length()){return false;}}return true;}
}

后續挑戰 :

如果有大量輸入的 S，稱作S1, S2, … , Sk 其中 k >= 10億，你需要依次檢查它們是否為 T 的子序列。在這種情況下，你會怎樣改變代碼？

class Solution {public boolean isSubsequence(String s, String t) {int m = s.length(), n = t.length();ArrayList<Integer>[] index = new ArrayList[256];// 先記下 t 中每個字符出現的位置for (int i = 0; i < n; i++) {char c = t.charAt(i);if (index[c] == null) index[c] = new ArrayList<>();index[c].add(i);}int j = 0; // t 上的指針// 借助 index 查找 s[i]for (int i = 0; i < m; i++) {char c = s.charAt(i);// 整個 t 壓根兒沒有字符 cif (index[c] == null) return false;int pos = find(index[c], j);// 二分搜索區間中沒有找到字符 cif (pos == index[c].size()) return false;// 向前移動指針 jj = index[c].get(pos) + 1;}return true;}public int find(ArrayList<Integer> arr, int target){int left = 0, right = arr.size();while(left < right){int mid = left + (right - left)/2;if(arr.get(mid) == target){right = mid;}else if (arr.get(mid) > target){right = mid;}else {left = mid + 1;}}return left;}
}