先来几个入门级别的练练手。
若求的是小于临界值的，return high。因为high最终=mid-1.
若求的是大于临界值的，return low。因为low最终=mid+1.
367. Valid Perfect Square
比较简单，O(log n) 复杂度。
public boolean isPerfectSquare(int num) {
long low=1, high=num;
while(low<=high){
long mid=(low+high)/2;
if(mid*mid==num)
return true;
else if(mid*mid>num)
high=mid-1;
else low=mid+1;
}
return false;
}
另外还有两种解法。
利用数学性质，可被开方的数字一定是1+3+5+7+......一个一个去试就行了。 O(sqrt(n)) 复杂度。
public boolean isPerfectSquare(int num) {
int i = 1;
while (num > 0) {
num -= i;
i += 2;
}
return num == 0;
}
用Newton Method。 https://en.wikipedia.org/wiki/Integer_square_root#Using_only_integer_division
不过感觉意义不大。
public boolean isPerfectSquare(int num) {
long x = num;
while (x * x > num) {
x = (x + num / x) >> 1;
}
return x * x == num;
}
35. Search Insert Position
Binary Search都用非递归写算了，递归beats 31%，非递归beats 78%，差距挺大的。
另外就是注意如果找不到的话，要返回low，因为最后low的位置就是mid+1，即本该出现的位置。或者返回high+1也是一样。
public int searchInsert(int[] nums, int target) {
int low=0, high=nums.length-1;
while(low<=high){
int mid=(low+high)/2;
if(nums[mid]==target)
return mid;
else if(nums[mid]>target)
high=mid-1;
else low=mid+1;
}
return low;
}
475. Heaters
这题看起来容易，但处理corner case挺烦的，G家出的。
因为用Binary Search，所以得先sort heaters。
对于每一个house，算出左边最接近的heater的距离和右边最接近的heater距离，取最小，即为覆盖该house最小的radius。
对于所有house，每个house的最小radius取最大，即为覆盖所有house最小的radius。
O(mlog n)复杂度。
顺带一提，java自带 Arrays.binarySearch()方法。
public class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int max=0;
for(int i=0;i<houses.length;i++){
int low=0, high=heaters.length-1;
int res=bs(low, high, houses[i], heaters);
max=Math.max(max, res);
}
return max;
}
public int bs(int low, int high, int target, int[] heaters){
while(low<=high){
int mid=(low+high)/2;
if(heaters[mid]>target)
high=mid-1;
else if(heaters[mid]<target)
low=mid+1;
else return 0;
}
int left= low<heaters.length? Math.abs(heaters[low]-target):Integer.MAX_VALUE;
int right= high>-1? Math.abs(target-heaters[high]):Integer.MAX_VALUE;
return Math.min(left, right);
}
}
69. Sqrt(x)
注意对于x，如果他不能开方的话，返回小于他的可开方的结果。因此最后返回的是high。
public class Solution {
public int mySqrt(int x) {
long low=0, high=x;
while(low<=high){
long mid=(low+high)/2;
if(mid*mid==x)
return (int)mid;
else if(mid*mid<x)
low=mid+1;
else high=mid-1;
}
return (int)high;
}
}
374. Guess Number Higher or Lower
Trivial.
public class Solution extends GuessGame {
public int guessNumber(int n) {
long low=0, high=n;
while(low<=high){
long mid=(low+high)/2;
int res=guess((int)mid);
if(res==-1)
high=mid-1;
else if(res==1)
low=mid+1;
else return (int)mid;
}
return 0;
}
}
278. First Bad Version
Important!!!! 一定要用long啊啊啊啊!!!! Leetcode 每次都会用overflow的值来搞你啊啊啊!!!!每次改好费劲啊啊啊啊!!!!一开始就要用long啊啊啊啊啊!!!!!!!!
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
long low=1, high=n;
while(low<=high){
long mid=(low+high)/2;
if(isBadVersion((int)mid))
high=mid-1;
else low=mid+1;
}
return (int)low;
}
}
441. Arranging Coins
这题相当于求最长连续队列 1+2+3+4+.....+x<=n。
用binary search的话就利用求和公式 (x*(x+1))/2 <=n来做。
public class Solution {
public int arrangeCoins(int n) {
int low=0, high=n;
while(low<=high){
int mid=(low+high)/2;
if((0.5*mid*mid+0.5*mid)<=n)
low=mid+1;
else high=mid-1;
}
return high;
}
}
153. Find Minimum in Rotated Sorted Array
注意循环条件low不能等于high，不然找到pivot会死循环至TLE。因为我们是拿high跟mid作为比较，最后high会一直向pivot靠近，直到等于pivot。
public class Solution {
public int findMin(int[] nums) {
int low=0, high=nums.length-1;
if(high==0)
return nums[high];
while(low<high){
int mid=(low+high)/2;
if(nums[mid]>nums[high]){
low=mid+1;
}
else if(nums[mid]<nums[high]){
high=mid;
}
}
return nums[high];
}
}
154. Find Minimum in Rotated Sorted Array II
允许duplicate，因此追加个操作，当nums[mid]=nums[high]的时候，因为不知道pivot在左边还是右边，索性就往左挪，high--。
public class Solution {
public int findMin(int[] nums) {
int low=0, high=nums.length-1;
while(low<high){
int mid=(low+high)/2;
if(nums[mid]<nums[high])
high=mid;
else if(nums[mid]>nums[high])
low=mid+1;
else high--;
}
return nums[high];
}
}
33. Search in Rotated Sorted Array
有了上一题铺垫，先找到rotate的pivot，找到之后就没什么好讲的了，老套路。
找到pivot后，用(mid+offset)%n来找出该元素在原队列的位置。
public class Solution {
public int search(int[] nums, int target) {
int low=0, high=nums.length-1;
while(low<high){
int mid=(low+high)/2;
if(nums[mid]>nums[high])
low=mid+1;
else high=mid;
}
int offset=low;
low=0;
high=nums.length-1;
while(low<=high){
int mid=(low+high)/2;
int realmid=(mid+offset)%nums.length;
if(nums[realmid]==target)
return realmid;
else if(nums[realmid]<target)
low=mid+1;
else high=mid-1;
}
return -1;
}
}
34. Search for a Range
题目要求解区间，因此需要2个binary search，一个出上限，一个出下限，O(2log n) 的复杂度。或者也可以用递归写到一起，看个人喜好。
public class Solution {
public int[] searchRange(int[] nums, int target) {
int low=0, high=nums.length-1;
int[] res=new int[2];
res[0]=bs(low, high, nums, target, 0, Integer.MAX_VALUE);
res[1]=bs(low, high, nums, target, 1, Integer.MIN_VALUE);
return res;
}
public int bs(int low, int high, int[] nums, int target, int mode, int left){
if(mode==0){
while(low<=high){
int mid=(low+high)/2;
if(nums[mid]==target&&mid<left){
left=mid;
high=mid-1;
}
else if(nums[mid]<target)
low=mid+1;
else high=mid-1;
}
if(left==Integer.MAX_VALUE)
left=-1;
}
if(mode==1){
while(low<=high){
int mid=(low+high)/2;
if(nums[mid]==target&&mid>left){
left=mid;
low=mid+1;
}
else if(nums[mid]<target)
low=mid+1;
else high=mid-1;
}
if(left==Integer.MIN_VALUE)
left=-1;
}
return left;
}
}
74. Search a 2D Matrix
先来常规解法，对每排第一个数用一次binary search确定数在哪一排，然后对该排用一次binary search找出该数。因为每排第一个数是该排最小，所以第一次binary search后取high即为所在排。
另外注意如果high<0，则不存在该数。
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m=matrix.length;
if(m==0)
return false;
int n=matrix[0].length;
if(n==0)
return false;
int low=0, high=m-1;
while(low<=high){
int mid=(low+high)/2;
if(matrix[mid][0]==target)
return true;
else if(matrix[mid][0]>target)
high=mid-1;
else low=mid+1;
}
int row=high;
if(row<0)
return false;
low=0; high=n-1;
while(low<=high){
int mid=(low+high)/2;
if(matrix[row][mid]==target)
return true;
else if(matrix[row][mid]<target)
low=mid+1;
else high=mid-1;
}
return false;
}
}
第二个解法，将整个2D Matrix看做一个sorted 数列，则第i位数对应 nums[i/n][i%n]。然后正常用binary search就行。
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length==0)
return false;
if(matrix[0].length==0)
return false;
int low=0, high=matrix.length*matrix[0].length-1;
while(low<=high){
int mid=(low+high)/2;
if(matrix[mid/matrix[0].length][mid%matrix[0].length]==target)
return true;
else if(matrix[mid/matrix[0].length][mid%matrix[0].length]>target)
high=mid-1;
else low=mid+1;
}
return false;
}
}
240. Search a 2D Matrix II
300. Longest Increasing Subsequence
只写binary search做法。
用一个数组big装前n个连续增长数列的最大值，也就是连续增长数列的末尾那个数。
比如对于数列[1,2,5,4,3,6,7]，先装第一个数， big[0]=1。第二个数2，大于big[0]，则big[1]=2，接着big[2]=5，到第四个数4，小于big[2]，则将big[2]更新，因为到big[2]增长中断，将big[2]赋值为4。下一个数3，小于big[2]，不增长，则又将big[2]更新，以便于重新算增长的长度。碰到下一个数6，大于big[2]，于是big[3]=6。
因此每读取一个数，都要在big数组里进行binary search，如果大于所有big[1...n]，则size+1并更新big[n+1]。最后返回size。O(nlogn)复杂度。
public class Solution {
public int lengthOfLIS(int[] nums) {
int[] big=new int[nums.length];
int count=0;
for(int s:nums){
int low=0, high=count;
while(low<high){
int mid=(low+high)/2;
if(big[mid]<s)
low=mid+1;
else high=mid;
}
big[high]=s;
if(low==count)
count++;
}
return count;
}
}
354. Russian Doll Envelopes
俄罗斯套娃嘛，大的套小的。有了上一题的基础，这题就十分好做了，信手拈来。
首先把数组排序，可以根据width排序，排序好之后就是 longest increasing subsequence问题了。
有个细节要注意，这个width可以是重复值，因此对于[3, 3]和[3, 4]来说，[3, 4]是不能套[3, 3]的，但是算法会判定能套，因为4>3。所以在排序的时候，对于width相同的，要把height大的排在前面，这样就不会出错了。
public class Solution {
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, new Comparator<int[]>(){
public int compare(int[] num1, int[] num2){
if(num1[0]==num2[0])
return num2[1]-num1[1];
else return num1[0]-num2[0];
}
}
);
int[] tail=new int[envelopes.length+1];
int count=0;
for(int[] num:envelopes){
int low=0, high=count;
while(low<high){
int mid=(low+high)/2;
if(num[1]>tail[mid])
low=mid+1;
else high=mid;
}
tail[high]=num[1];
if(low==count)
count++;
}
return count;
}
}
162. Find Peak Element
和rotated sorted array类似，但是在处理方法只能mid和前一个或后一个比，因为不能保证mid前都是sorted或者mid后都是sorted。这里是判断小于mid+1，所以最后high位置为所求。如果判断大于mid+1，则low位置为所求。
public class Solution {
public int findPeakElement(int[] nums) {
int low=0, high=nums.length-1;
while(low<high){
int mid=(low+high)/2;
if(nums[mid]<nums[mid+1])
low=mid+1;
else high=mid;
}
return high;
}
}
436. Find Right Interval
这题做起来巨tm烦，逻辑太绕了。
首先我们必须sort intervals才能用binary search，因此用个hashmap记录原本的index。由于start不重复，就用start来标记。由于要保留intervals原本的顺序(不然涉及很多map.get操作巨烦)，又要新建一个数组来sort，这里我们sort start。接下来就是照常的binary search。
public class Solution {
public int[] findRightInterval(Interval[] intervals) {
Map<Integer, Integer> map=new HashMap<>();
int[] starts=new int[intervals.length];
int[] res=new int[intervals.length];
for(int i=0;i<intervals.length;i++){
map.put(intervals[i].start, i);
starts[i]=intervals[i].start;
}
Arrays.sort(starts);
for(int i=0;i<intervals.length;i++){
int low=0, high=starts.length-1;
while(low<high){
int mid=(low+high)/2;
if(starts[mid]>=intervals[i].end)
high=mid;
else low=mid+1;
}
if(starts[high]<intervals[i].end)
res[i]=-1;
else res[i]=map.get(starts[high]);
}
return res;
}
}
483. Smallest Good Base
4. Median of Two Sorted Arrays
这题貌似很经典啊，序号为4的hard题，频率是绿条，各大公司都考过，那必须做到倒背如流。
唯一要解决的重要点就是，怎么找到合适的位置。Median的位置便是将AB等量分开的位置，即A[left]+B[left]的长度等于A[right]+B[right]。同时，Median左侧的最大元素要小于右侧的最小元素。
所以做法就是，先求得整个数组的中点 bigMid，然后对A数组二分，每次找个mid，相应的B数组里就是bigMid-mid位置。这样就能保证A[left]+B[left]恒为一半。如果A小于B，mid就要增加，反之mid减小，最终贴近的位置就是Median位置。
找到Median位置后，接着就找出左侧的最大元素和右侧的最小元素，即得Median。
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n=nums1.length;
int m=nums2.length;
if(n>m)
return findMedianSortedArrays(nums2, nums1);
int bigMid=(n+m-1)/2;
int low=0, high=Math.min(bigMid, n);
while(low<high){
int mid1=(low+high)/2;
int mid2=bigMid-mid1;
if(nums1[mid1]<nums2[mid2])
low=mid1+1;
else high=mid1;
}
int left=Math.max( low>0? nums1[low-1]:Integer.MIN_VALUE, bigMid-low>=0? nums2[bigMid-low]:Integer.MIN_VALUE);
int right=Math.min( low<n? nums1[low]:Integer.MAX_VALUE, bigMid-low+1<m? nums2[bigMid-low+1]:Integer.MAX_VALUE);
if((n+m)%2==1)
return (double)left;
return (left+right)/2.0;
}
}
410. Split Array Largest Sum
这道题还是挺好想的，我们可以先设个lower bound和upper bound，然后对bound进行二分，每次出来的mid我们都进行验证，如果满足要求，降低upper bound，不满足，提高lower bound。验证的话，拿个count计数，每次和大于mid时，另开个区间，count++。如果最后count不大于m，就满足要求。
public class Solution {
public int splitArray(int[] nums, int m) {
long low=0, high=0;
for(int num:nums){
low=Math.max(low, num);
high+=num;
}
while(low<=high){
long mid=(low+high)/2;
if(helper(mid, nums, m))
high=mid-1;
else low=mid+1;
}
return (int)low;
}
public boolean helper(long mid, int[] nums, int m){
long sum=0;
int count=1;
for(int num:nums){
sum+=num;
if(sum>mid){
count++;
sum=num;
}
if(count>m)
return false;
}
return true;
}
}
302. Smallest Rectangle Enclosing Black Pixels
给的是其中一个黑点的坐标( x, y )，因此根据这个坐标找出4个边界就可以算出面积。假设矩阵维度m x n。
- 左边能到达的最远列
- 右边能到达的最远列
- 上边能到达的最远排
- 下边能到达的最远排
对于这四个边界，分别用二分来搞就行。
- low=0, high=y.
- low=y, high=n-1.
- low=0, high=x.
- low=x, high=m-1.
判断是否valid就是算出当前列/行是不是至少含有一个1.
public class Solution {
int m,n;
public int minArea(char[][] image, int x, int y) {
m=image.length;
n=image[0].length;
int left_col=bs(0, y, image, 0, 0);
int right_col=bs(y, n-1, image, 0, 1);
int up_row=bs(0, x, image, 1, 0);
int down_row=bs(x, m-1, image, 1, 1);
return (down_row-up_row)*(right_col-left_col);
}
public int bs(int low, int high, char[][] image, int mode, int mode2){
while(low<=high){
int mid=(low+high)/2;
if(isValid(mid, image, mode)){
if(mode2==0)
high=mid-1;
else low=mid+1;
}
else {
if(mode2==0)
low=mid+1;
else high=mid-1;
}
}
return low;
}
public boolean isValid(int mid, char[][] image, int mode){
if(mode==0){
for(int i=0;i<m;i++)
if(image[i][mid]=='1')
return true;
}
else {
for(int i=0;i<n;i++)
if(image[mid][i]=='1')
return true;
}
return false;
}
}