最近實習(xí)生面試因為算法題吃了大虧,之前雖然看了《劍指Offer》铃绒,LeetCode也刷了差不多幾十道題鸽照,但是沒有實實在在掌握,現(xiàn)在趕緊補上來匿垄,希望還不算太晚移宅!這兩天一直在刷Binary Search相關(guān)tag的題,暫時把easy和medium難度的題搞定了椿疗,二分法都是采用
left+1<right
模板做的漏峰,答案先上傳,有時間會更新整理思路的届榄。
[35] Search Insert Position
https://leetcode.com/problems/search-insert-position
要求你找一個數(shù)target浅乔,當(dāng)target在沒找到的情況下,返回如果插入這個數(shù)铝条,這個數(shù)應(yīng)該在哪個下標(biāo)上(If not, return the index where it would be if it were inserted in order)靖苇,相當(dāng)于返回比X大的數(shù)當(dāng)中最小的那個數(shù)的下標(biāo),因為如果新插入這個數(shù)X班缰,這個數(shù)應(yīng)該排在比X大的數(shù)當(dāng)中最小的那個數(shù)的下標(biāo)上贤壁,其余數(shù)字依次后移一個下標(biāo)的位置。
mid是你當(dāng)前這一輪查找的數(shù)的下標(biāo)埠忘,當(dāng)沒找到的情況下脾拆,比mid大的數(shù)當(dāng)中最小的那個數(shù)的下標(biāo)就是mid+1
而right = mid - 1; left = mid + 1; 所以返回left
同理反過來, 如果題目要求你在沒找到的情況下莹妒,返回比X小的數(shù)當(dāng)中最大的那個數(shù)的下標(biāo)名船,則返回right。
總結(jié):在沒找到的情況下旨怠,返回比target大的數(shù)當(dāng)中最小的那個數(shù)的下標(biāo)渠驼,則返回left;在沒找到的情況下鉴腻,返回比target小的數(shù)當(dāng)中最大的那個數(shù)的下標(biāo)迷扇,則返回right。
public int searchInsert(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
int left = 0;
int right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid;
else if (nums[mid] > target)
right = mid;
else
return mid;
}
// target比最左邊元素還小爽哎,那么就插入在left
if (nums[left] >= target) return left;
else if (nums[right] >= target) return right;
else return right + 1;
}
[744] Find Smallest Letter Greater Than Target
https://leetcode.com/problems/find-smallest-letter-greater-than-target
問題:給定一組有序的字母letters谋梭,從中尋找大于字母target的最小字母(環(huán)形有序,z < a)倦青。
思路:判斷中間元素<=target或者>target。
public char nextGreatestLetter(char[] letters, char target) {
int left = 0;
int right = letters.length - 1;
// l==r<n表示找到解了盹舞;l==r==n表示當(dāng)前數(shù)組中沒有比target大的产镐,直接返回第一個元素
while (left + 1 < right) {
int mid = left + (right - left) / 2;
// 中間元素<=target隘庄,表示不是想要的解(第一個大于target的元素)
if (letters[mid] <= target)
left = mid;
else if (letters[mid] > target)
right = mid;
}
if (letters[left] > target) return letters[left];
else if (letters[right] > target) return letters[right];
else return letters[0];
}
參考講解:
[349] Intersection of Two Arrays
https://leetcode.com/problems/intersection-of-two-arrays
問題:給定兩個數(shù)組,寫一個函數(shù)計算它們的交癣亚。
思路:對nums1中的元素遍歷丑掺,然后再nums2中進(jìn)行二分查找,如果兩個元素相等述雾,則放到HashSet中去重街州。
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return new int[]{};
HashSet<Integer> set = new HashSet<>();
Arrays.sort(nums2);
for (Integer num : nums1) {
if (binarySearch(nums2, num)) set.add(num);
}
int k = 0;
int[] res = new int[set.size()];
for (Integer num : set) {
res[k++] = num;
}
return res;
}
private boolean binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return true;
else if (nums[mid] < target)
left = mid;
else
right = mid;
}
if (nums[left] == target || nums[right] == target) return true;
return false;
}
參考講解:
- https://www.youtube.com/watch?v=KJF6JQybjsI
- https://www.youtube.com/watch?v=B5CaAmN8QSQ
- http://www.reibang.com/p/d22d617854f5
[350] Intersection of Two Arrays II
https://leetcode.com/problems/intersection-of-two-arrays-ii
問題:給定兩個數(shù)組,寫一個函數(shù)計算它們的交(要考慮有重復(fù)元素的結(jié)果)玻孟。
思路:不推薦用二分法解唆缴。
public int[] intersection(int[] nums1, int[] nums2) {
// 沒有數(shù)字的情況
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return new int[0];
int results[] = new int[nums1.length];// 結(jié)果數(shù)組
// 先對兩個數(shù)組排序
Arrays.sort(nums1);
Arrays.sort(nums2);
int index = 0;
for (int i = 0, j = 0; i < nums1.length; ) {
if (nums1[i] < nums2[j]) {// 第一個數(shù)組中數(shù)字小
i++;
} else if (nums1[i] == nums2[j]) {// 數(shù)字相同,放入結(jié)果數(shù)組
results[index] = nums1[i];
index++;
i++;
// 判斷第二個數(shù)組有沒有到最后一個數(shù)組黍翎,還沒到才繼續(xù)往后移去比
if (j < nums2.length - 1) j++;
else break;
} else {// 第二個數(shù)組中數(shù)字小面徽,注意要判斷是否到達(dá)最后一個數(shù)字
if (j < nums2.length - 1) j++;
else break;
}
}
return Arrays.copyOfRange(results, 0, index);// 結(jié)果數(shù)組只返回有數(shù)字的那一部分
}
參考講解:
[441] Arranging Coins
https://leetcode.com/problems/arranging-coins
問題:有n枚硬幣,鑄成階梯型(第k行有k枚硬幣)匣掸,返回能被鑄的完整階梯的行數(shù)趟紊,(如果最后一行硬幣不足則不包含)。
思路:k*(k+1)/2
public int arrangeCoins(int n) {
if (n <= 1) return n;
int left = 0;
int right = n;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
// mid的類型為long碰酝,一定注意霎匈!
long midVal = (long) mid * (mid + 1) / 2;
if (midVal == n)
return mid;
else if (midVal > n)
right = mid;
else
left = mid;
}
if (right * (right + 1) / 2 <= n) return right;
return left;
}
[287] Find the Duplicate Number
https://leetcode.com/problems/find-the-duplicate-number
問題:一個非有序數(shù)組有n+1個數(shù),范圍是[1,n]送爸,其中有一個數(shù)重復(fù)了兩次铛嘱。
思路:我們不一定要依次選擇數(shù),然后看是否有這個數(shù)的重復(fù)數(shù)碱璃,我們可以用二分法先選取n/2弄痹,按照抽屜原理,整個數(shù)組中如果小于等于n/2的數(shù)的數(shù)量大于n/2嵌器,說明1到n/2這個區(qū)間是肯定有重復(fù)數(shù)字的肛真。比如6個抽屜,如果有7個襪子要放到抽屜里爽航,那肯定有一個抽屜至少兩個襪子蚓让。這里抽屜就是1到n/2的每一個數(shù),而襪子就是整個數(shù)組中小于等于n/2的那些數(shù)讥珍。這樣我們就能知道下次選擇的數(shù)的范圍历极,如果1到n/2區(qū)間內(nèi)肯定有重復(fù)數(shù)字,則下次在1到n/2范圍內(nèi)找衷佃,否則在n/2到n范圍內(nèi)找趟卸。下次找的時候,還是找一半。
public int findDuplicate(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
// 找到中間那個數(shù)
int mid = left + (right - left) / 2;
int count = 0;
// 由于數(shù)組非有序锄列,要用for循環(huán)遍歷整個數(shù)組图云,計算總數(shù)組中有多少個數(shù)小于等于中間數(shù)
for (int i = 0; i < nums.length; i++) {
// 比較的是mid而不是nums[mid]
if (nums[i] <= mid) count++;
}
// 如果小于等于中間數(shù)的數(shù)的個數(shù)大于中間數(shù)mid,說明前半部分必有重復(fù)
if (count > mid)
right = mid - 1;
// 否則后半部分必有重復(fù)
else
left = mid + 1;
}
return left;
}
參考講解:
- https://www.youtube.com/watch?v=e5AWbVTDqqI
- http://www.cnblogs.com/grandyang/p/4843654.html
- https://segmentfault.com/a/1190000003817671
[33] Search in Rotated Sorted Array
https://leetcode.com/problems/search-in-rotated-sorted-array
問題:
思路:
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
int left = 0;
int right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] < nums[mid]) {
// 移動右指針
if (nums[left] <= target && nums[mid] >= target) right = mid;
else left = mid;
} else if (nums[mid] < nums[right]) {
// 移動左指針
if (nums[right] >= target && nums[mid] <= target) left = mid;
else right = mid;
}
}
// 此時left和right相鄰邻邮,只要判斷是nums[left]還是nums[right]等于target就可以了
if (nums[left] == target) return left;
if (nums[right] == target) return right;
return -1;
}
參考講解:
[81] Search in Rotated Sorted Array II
https://leetcode.com/problems/search-in-rotated-sorted-array-ii
問題:
思路:
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) return false;
int left = 0;
int right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return true;
if (nums[left] < nums[mid]) {
// 移動右指針
if (nums[left] <= target && nums[mid] >= target) right = mid;
else left = mid;
} else if (nums[mid] < nums[left]) {
// 移動左指針
if (nums[right] >= target && nums[mid] <= target) left = mid;
else right = mid;
} else {
left++;
}
}
if (nums[left] == target || nums[right] == target) return true;
return false;
}
參考講解:
[153] Find Minimum in Rotated Sorted Array
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array
問題:
思路:和Search in Rotated Sorted Array很類似竣况,但是更簡單。
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) return -1;
int left = 0;
int right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[right])
right = mid;
else
left = mid;
}
if (nums[left] <= nums[right]) return nums[left];
return nums[right];
}
參考講解:
- https://www.youtube.com/watch?v=lwvtvNIFvwA
- https://www.youtube.com/watch?v=P4r7mF1Jd50
- https://www.youtube.com/watch?v=PK4JQvgo2ZA
[154] Find Minimum in Rotated Sorted Array II
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii
問題:
思路:
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left + 1 < right) {
int mid = (left + right) / 2;
if (nums[mid] < nums[right])
right = mid;
else if (nums[mid] > nums[right])
left = mid;
else
// nums[mid]=nums[right] no idea, but we can eliminate nums[right];
right--;
}
if (nums[left] < nums[right]) return nums[left];
return nums[right];
}
參考講解:
- https://www.youtube.com/watch?v=aCb1zKMimDQ
- http://www.cnblogs.com/springfor/p/4217615.html
- http://buttercola.blogspot.com/2015/08/leetcode-find-minimum-in-rotated-sorted.html
[34] Search for a Range
https://leetcode.com/problems/search-for-a-range
問題:給定一個升序數(shù)組筒严,找到目標(biāo)值對應(yīng)的first index和last index丹泉。
思路:關(guān)鍵是考慮如何處理nums[mid]==target?
先找起點鸭蛙,如果起點在mid的左側(cè)摹恨,那么移動right指針;再找終點规惰,如果終點在mid的右側(cè)睬塌,那么移動left指針。
public int[] searchRange(int[] nums, int target) {
int[] res = new int[]{-1, -1};
if (nums == null || nums.length == 0) return res;
int startIndex = -1, endIndex = -1;
// 找起點startIndex
int left = 0, right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid;
else
right = mid;
}
// 優(yōu)先判斷nums[left]
if (nums[left] == target) startIndex = left;
else if (nums[right] == target) startIndex = right;
if (startIndex == -1) return res;
// 找終點endIndex
left = 0;
right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target)
right = mid;
else
left = mid;
}
// 優(yōu)先判斷nums[right]
if (nums[right] == target) endIndex = right;
else if (nums[left] == target) endIndex = left;
res[0] = startIndex;
res[1] = endIndex;
return res;
}
參考講解:
[162] Find Peak Element
https://leetcode.com/problems/find-peak-element
問題:找到數(shù)組中的極大值點歇万。
思路:極大值點就是比左右兩邊元素都大的點揩晴。
public int findPeakElement2(int[] nums) {
if (nums == null || nums.length == 0) return -1;
if (nums.length == 1) return 0;
int left = 0;
int right = nums.length;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
// 如果一個數(shù)nums[mid]比前面一個和后面一個數(shù)都要大,那么就是我們要找的數(shù)(peak element)
if ((mid == 0 || nums[mid] > nums[mid - 1]) &&
(mid == nums.length - 1 || nums[mid] > nums[mid + 1]))
return mid;
else if (mid > 0 && nums[mid] < nums[mid - 1])
right = mid;
else
left = mid;
}
if (nums[left] > nums[right]) return left;
return right;
}
參考講解:
- https://www.youtube.com/watch?v=NJBBJimXggo
- https://www.youtube.com/watch?v=C9WgtC1wG70
- https://www.youtube.com/watch?v=hvJtPY_4dVE
- http://blog.leanote.com/post/westcode/%5B刷題筆記%5D-LeetCode-LintCode-Find-Peak-Elemen
[278] First Bad Version
https://leetcode.com/problems/first-bad-version
問題:
思路:
public int firstBadVersion(int n) {
int left = 1;
int right = n;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid;
}
}
if (isBadVersion(left)) return left;
return right;
}
[378] Kth Smallest Element in a Sorted Matrix
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix
問題:
思路:我們并不用對每一行都做二分搜索法贪磺,我們注意到每列也是有序的硫兰,我們可以利用這個性質(zhì),從數(shù)組的左下角開始查找寒锚,如果比目標(biāo)值小劫映,我們就向右移一位,而且我們知道當(dāng)前列的當(dāng)前位置的上面所有的數(shù)字都小于目標(biāo)值刹前,那么count += i+1泳赋,反之則向上移一位,這樣我們也能算出cnt的值喇喉。其余部分跟上面的方法相同祖今。
public int kthSmallest(int[][] matrix, int k) {
int left = matrix[0][0];
int right = matrix[matrix.length - 1][matrix[0].length - 1];
while (left + 1 < right) {
int mid = left + (right - left) / 2;
int count = count(matrix, mid);
if (count < k)
left = mid;
else
right = mid;
}
if (count(matrix, right) <= k - 1) return right;
else return left;
}
private int count(int[][] matrix, int target) {
int n = matrix.length;
int result = 0;
for (int i = 0; i < n; i++) {
int j = 0;
while (j < n && matrix[i][j] < target) j++;
result += j;
}
return result;
}
參考講解:
- https://www.youtube.com/watch?v=UP4RF_UjyNk
- https://www.youtube.com/watch?v=T3AAEuZpojU
- https://segmentfault.com/a/1190000008345302
[230] Kth Smallest Element in a BST
https://leetcode.com/problems/kth-smallest-element-in-a-bst
問題:
思路:二分的思想是我每次看看當(dāng)前節(jié)點的左子樹中有多少個元素,記為count拣技。
如果我的k <= count千诬,那么顯然第k小的樹在左子樹中,在左子樹中繼續(xù)進(jìn)行二分搜索膏斤。
如果我的k == count + 1, 那么當(dāng)前節(jié)點恰好是這個第k小的節(jié)點徐绑,直接返回節(jié)點點。
如果我的k > count + 1, 那么第k小的節(jié)點在右子樹莫辨,在右子樹中繼續(xù)進(jìn)行二分搜索傲茄。
public int kthSmallest(TreeNode root, int k) {
int count = countNodes(root.left);
if (k == count + 1) {
return root.val;
} else if (k <= count) {
return kthSmallest(root.left, k);
} else {
// count is the left tree num, 1 is the root
return kthSmallest(root.right, k - 1 - count);
}
}
private int countNodes(TreeNode node) {
if (node == null) return 0;
return 1 + countNodes(node.left) + countNodes(node.right);
}
參考講解:
[367] Valid Perfect Square
https://leetcode.com/problems/valid-perfect-square
問題:給定一個數(shù)n毅访,要求不使用sqrt函數(shù)判斷該數(shù)是否為完全平方數(shù)。
思路:L = 1, R = num / 2 +1開始枚舉即可烫幕。
public boolean isPerfectSquare(int num) {
if (num <= 0) return false;
long left = 0;
long right = num;
while (left + 1 < right) {
long mid = left + (right - left) / 2;
long temp = mid * mid;
if (mid * mid == num)
return true;
else if (mid * mid < num && (mid + 1) * (mid + 1) > num)
return false;
else if (temp < num)
left = mid;
else if (temp > num)
right = mid;
}
if (left * left == num || right * right == num) return true;
return false;
}
參考講解:
[658] Find K Closest Elements
https://leetcode.com/problems/find-k-closest-elements
問題:在一個有序數(shù)組中離給定元素x最近的k個元素(要求返回結(jié)果有序)俺抽。
思路:由于要求返回的數(shù)組是有序的,因此只要找出這k個元素的最左邊那個较曼,然后往右遍歷k個元素作為結(jié)果就可以保證有序的。所以問題變成了left bound的二分搜索過程振愿。
值的范圍:1...M...N
left bound的范圍:0...M...N-k
- 先確定中間值的下標(biāo)是M捷犹,分成兩段,一段是[0, M]冕末,一段是[M, N-k]萍歉。相應(yīng)x也有可能出現(xiàn)在這兩段中的任意一段。
- 如果x取值在[0, M]档桃,又要圍繞x取k個值枪孩,那么left bound一定在M左邊,也就是[0, M]
- 如果x取值在[M, N-k]藻肄,那么left bound有可能出現(xiàn)在[0, M]蔑舞,也有可能出現(xiàn)在[M, N-k]。因此我們以M開頭嘹屯,創(chuàng)造一個k區(qū)間[M, M+k]攻询,如果x剛好出現(xiàn)在區(qū)間的中間位置,也就是
|x-nums[mid]| == |nums[mid+k]-x|
(因為Closest Elements指的是值得距離而不是索引的距離)州弟,那么left bound就是M位置钧栖。如果|x-nums[mid]| > |nums[mid+k]-x|
,那么left bound要往右偏移婆翔;反之往左偏移拯杠。
public List<Integer> findClosestElements(int[] arr, int k, int x) {
List<Integer> results = new ArrayList<>();
int left = 0;
int right = arr.length - k;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < x) {
if (Math.abs(x - arr[mid]) > Math.abs(arr[mid + k] - x)) {
left = mid + 1;
} else {
right = mid;
}
} else {
right = mid;
}
}
int index = left;
while (k != 0) {
results.add(arr[index++]);
k--;
}
return results;
}
參考講解:
- https://www.youtube.com/watch?v=3ifFNvdfjyg
- https://www.youtube.com/watch?v=hWhMl8biGHk
- https://www.jiuzhang.com/qa/458/
- http://www.jiuzhang.com/solution/find-k-closest-elements
- https://blog.csdn.net/TheSnowBoy_2/article/details/77431886
- https://yisuang1186.gitbooks.io/-shuatibiji/k_closest_number_in_sorted_array.html
[74] Search a 2D Matrix
https://leetcode.com/problems/search-a-2d-matrix
問題:
思路:
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return false;
int row = matrix.length;
int col = matrix[0].length;
int left = 0;
int right = row * col - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
int value = matrix[mid / col][mid % col];
if (value < target)
left = mid;
else if (value > target)
right = mid;
else
return true;
}
if (matrix[left / col][left % col] == target || matrix[right / col][right % col] == target) return true;
return false;
}
參考講解:
[240] Search a 2D Matrix II
https://leetcode.com/problems/search-a-2d-matrix-ii
問題:寫一個高效的算法,從一個m×nm×n的整數(shù)矩陣中查找出給定的值啃奴,矩陣具有如下特點:每一行從左到右遞增潭陪、每一列從上到下遞增。
思路:不能用二分法做纺腊。
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return false;
int row = matrix.length;
int col = matrix[0].length;
// i指向最后一行畔咧,j指向第一列
int i = row - 1;
int j = 0;
int count = 0;
// from bottom left to top right
while (i >= 0 && j < col) {
if (matrix[i][j] < target) {
j++;
} else if (matrix[i][j] > target) {
i--;
} else {
return true;
}
}
return false;
}
參考講解:
- https://www.youtube.com/watch?v=mB9iMI1UE8s
- https://www.jiuzhang.com/solution/search-a-2d-matrix-ii/
- https://blog.csdn.net/Jeanphorn/article/details/47028041
[275] H-Index II
https://leetcode.com/problems/h-index-ii
問題:被引用了n次及以上的有n篇文章。
思路:
/**
* H-Index 答案
*/
public int hIndex(int[] citations) {
Arrays.sort(citations);
int res = 0;
// 從后往前遍歷
while (res < citations.length && citations[citations.length - 1 - res] > res) {
res++;
}
return res;
}
/**
* H-Index II 答案
*/
public int hIndex(int[] citations) {
if (citations == null || citations.length == 0) return 0;
int len = citations.length;
int left = 0;
int right = len - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (citations[mid] == len - mid)
return len - mid;
else if (citations[mid] < len - mid)
left = mid;
else
right = mid;
}
if (citations[left] >= len - left) return len - left;
if (citations[right] >= len - right) return len - right;
return 0;
}
參考講解: