最近实习生面试因为算法题吃了大亏，之前虽然看了《剑指Offer》，LeetCode也刷了差不多几十道题，但是没有实实在在掌握，现在赶紧补上来，希望还不算太晚！这两天一直在刷Binary Search相关tag的题，暂时把easy和medium难度的题搞定了，二分法都是采用
left+1<right模板做的，答案先上传，有时间会更新整理思路的。
[35] Search Insert Position
https://leetcode.com/problems/search-insert-position
要求你找一个数target，当target在没找到的情况下，返回如果插入这个数，这个数应该在哪个下标上（If not, return the index where it would be if it were inserted in order），相当于返回比X大的数当中最小的那个数的下标，因为如果新插入这个数X，这个数应该排在比X大的数当中最小的那个数的下标上，其余数字依次后移一个下标的位置。
mid是你当前这一轮查找的数的下标，当没找到的情况下，比mid大的数当中最小的那个数的下标就是mid+1
而right = mid - 1; left = mid + 1; 所以返回left
同理反过来， 如果题目要求你在没找到的情况下，返回比X小的数当中最大的那个数的下标，则返回right。
总结：在没找到的情况下，返回比target大的数当中最小的那个数的下标，则返回left；在没找到的情况下，返回比target小的数当中最大的那个数的下标，则返回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的最小字母（环形有序，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表示当前数组中没有比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
问题：给定两个数组，写一个函数计算它们的交。
思路：对nums1中的元素遍历，然后再nums2中进行二分查找，如果两个元素相等，则放到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
- https://www.jianshu.com/p/d22d617854f5
[350] Intersection of Two Arrays II
https://leetcode.com/problems/intersection-of-two-arrays-ii
问题：给定两个数组，写一个函数计算它们的交（要考虑有重复元素的结果）。
思路：不推荐用二分法解。
public int[] intersection(int[] nums1, int[] nums2) {
// 没有数字的情况
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return new int[0];
int results[] = new int[nums1.length];// 结果数组
// 先对两个数组排序
Arrays.sort(nums1);
Arrays.sort(nums2);
int index = 0;
for (int i = 0, j = 0; i < nums1.length; ) {
if (nums1[i] < nums2[j]) {// 第一个数组中数字小
i++;
} else if (nums1[i] == nums2[j]) {// 数字相同，放入结果数组
results[index] = nums1[i];
index++;
i++;
// 判断第二个数组有没有到最后一个数组，还没到才继续往后移去比
if (j < nums2.length - 1) j++;
else break;
} else {// 第二个数组中数字小，注意要判断是否到达最后一个数字
if (j < nums2.length - 1) j++;
else break;
}
}
return Arrays.copyOfRange(results, 0, index);// 结果数组只返回有数字的那一部分
}
参考讲解：
[441] Arranging Coins
https://leetcode.com/problems/arranging-coins
问题：有n枚硬币，铸成阶梯型（第k行有k枚硬币），返回能被铸的完整阶梯的行数，（如果最后一行硬币不足则不包含）。
思路：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
问题：一个非有序数组有n+1个数，范围是[1,n]，其中有一个数重复了两次。
思路：我们不一定要依次选择数，然后看是否有这个数的重复数，我们可以用二分法先选取n/2，按照抽屉原理，整个数组中如果小于等于n/2的数的数量大于n/2，说明1到n/2这个区间是肯定有重复数字的。比如6个抽屉，如果有7个袜子要放到抽屉里，那肯定有一个抽屉至少两个袜子。这里抽屉就是1到n/2的每一个数，而袜子就是整个数组中小于等于n/2的那些数。这样我们就能知道下次选择的数的范围，如果1到n/2区间内肯定有重复数字，则下次在1到n/2范围内找，否则在n/2到n范围内找。下次找的时候，还是找一半。
public int findDuplicate(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
// 找到中间那个数
int mid = left + (right - left) / 2;
int count = 0;
// 由于数组非有序，要用for循环遍历整个数组，计算总数组中有多少个数小于等于中间数
for (int i = 0; i < nums.length; i++) {
// 比较的是mid而不是nums[mid]
if (nums[i] <= mid) count++;
}
// 如果小于等于中间数的数的个数大于中间数mid，说明前半部分必有重复
if (count > mid)
right = mid - 1;
// 否则后半部分必有重复
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
问题：给定一个升序数组，找到目标值对应的first index和last index。
思路：关键是考虑如何处理nums[mid]==target？
先找起点，如果起点在mid的左侧，那么移动right指针；再找终点，如果终点在mid的右侧，那么移动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;
}
// 优先判断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;
}
// 优先判断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
问题：找到数组中的极大值点。
思路：极大值点就是比左右两边元素都大的点。
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;
// 如果一个数nums[mid]比前面一个和后面一个数都要大，那么就是我们要找的数(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
问题：
思路：我们并不用对每一行都做二分搜索法，我们注意到每列也是有序的，我们可以利用这个性质，从数组的左下角开始查找，如果比目标值小，我们就向右移一位，而且我们知道当前列的当前位置的上面所有的数字都小于目标值，那么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
问题：
思路：二分的思想是我每次看看当前节点的左子树中有多少个元素，记为count。
如果我的k <= count，那么显然第k小的树在左子树中，在左子树中继续进行二分搜索。
如果我的k == count + 1, 那么当前节点恰好是这个第k小的节点，直接返回节点点。
如果我的k > count + 1, 那么第k小的节点在右子树，在右子树中继续进行二分搜索。
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
问题：给定一个数n，要求不使用sqrt函数判断该数是否为完全平方数。
思路：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
问题：在一个有序数组中离给定元素x最近的k个元素（要求返回结果有序）。
思路：由于要求返回的数组是有序的，因此只要找出这k个元素的最左边那个，然后往右遍历k个元素作为结果就可以保证有序的。所以问题变成了left bound的二分搜索过程。
值的范围：1...M...N
left bound的范围：0...M...N-k
- 先确定中间值的下标是M，分成两段，一段是[0, M]，一段是[M, N-k]。相应x也有可能出现在这两段中的任意一段。
- 如果x取值在[0, M]，又要围绕x取k个值，那么left bound一定在M左边，也就是[0, M]
- 如果x取值在[M, N-k]，那么left bound有可能出现在[0, M]，也有可能出现在[M, N-k]。因此我们以M开头，创造一个k区间[M, M+k]，如果x刚好出现在区间的中间位置，也就是
|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的整数矩阵中查找出给定的值，矩阵具有如下特点：每一行从左到右递增、每一列从上到下递增。
思路：不能用二分法做。
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;
}
参考讲解：
