IVN
0%

再看二分

Posted on Edited on In
Symbols count in article: 26k Reading time ≈ 23 mins.

二分好题选编

852. Peak Index in a Mountain Array

找最小的arr[i]大于arr[i+1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode852 {
    public int peakIndexInMountainArray(int[] arr) {
        //[1, n-2]
        int n=arr.length;
        int left=1;
        int right=n-2;
        int res=0;
        while(left<=right){
            //[left,right]
            int mid=left+(right-left)/2;
            if(arr[mid]>arr[mid-1]){
                res=mid;
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return res;
    }
}

162. Find Peak Element

You must write an algorithm that runs in O(log n) time.

俗话说「人往高处走，水往低处流」。如果我们从一个位置开始，不断地向高处走，那么最终一定可以到达一个峰值位置。

但没有回头路，每当选择向一边走，另一边的路就再也不可能走到了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int findPeakElement(int[] nums) {
    int n=nums.length;
    int left=0;
    int right=n-1;
    int res=0;
    while(left<=right){
        int mid=left+(right-left)/2;
        int l=mid-1>=0 ? nums[mid-1] : Integer.MIN_VALUE;
        int r=mid+1<n ? nums[mid+1] : Integer.MIN_VALUE;
        if(nums[mid]>l && nums[mid]>r){
            return mid;
        }
        if(l>nums[mid] && nums[mid]>r){
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class LeetCode162 {
    public int findPeakElement(int[] nums) {
        //nums[i-1]<nums[i]>nums[i+1]
        //nums[i-1]>nums[i]<nums[i+1], i=i+1	波谷时向左向右都可
        //nums[i-1]>nums[i]>nums[i+1], i=i-1
        //nums[i-1]<nums[i]<nums[i+1], i=i+1
        int n=nums.length;
        int left=0;
        int right=n-1;
        int res=0;
        while(left<=right){
            int mid=left+(right-left)/2;
            int c=compare(nums,mid-1,mid,mid+1);
            if(c==0){
                res=mid;
                break;
            }else if(c>0){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return res;
    }

    int compare(int[] nums, int pre, int cur, int post){
        int preVal= pre==-1 ? Integer.MIN_VALUE : nums[pre];
        int postVal= post==nums.length ? Integer.MIN_VALUE : nums[post];
        int curVal=nums[cur];
        if(curVal>preVal && curVal>postVal){
            return 0;
        }
        if(curVal<preVal && curVal>postVal){
            return -1;
        }
        return 1;
    }
}

167. Two Sum II - Input Array Is Sorted

注意：

  1. already sorted in non-decreasing order
  2. there is exactly one solution
  3. must use only constant extra space

time and space complexity:

  • Two pointers: O(n) time and O(1) space
  • Dictionary: O(n) time and O(n) space
  • Binary search: O(nlogn) time and O(1) space

法一： two pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] twoSum(int[] numbers, int target) {
    int n=numbers.length;
    int left=0;
    int right=n-1;
    while(left<right){
        int sum=numbers[left]+numbers[right];
        if(sum==target){
            return new int[]{left+1,right+1};
        }else if(sum>target){
            right--;
        }else{
            left++;
        }
    }
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int[] twoSum(int[] numbers, int target) {
            int n=numbers.length;
    for (int i = 0; i < n; i++) {
        int temp=target-numbers[i];
        int left=i+1;
        int right=n-1;
        int mid=0;
        while(left<=right){
            mid=left+(right-left)/2;
            if(numbers[mid]==temp){
                return new int[]{i+1,mid+1};
            }else if(numbers[mid]<temp){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
    }
    return null;
}

209. Minimum Size Subarray Sum

法一： sliding window

O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int minSubArrayLen(int target, int[] nums) {
    int n=nums.length;
    int min=Integer.MAX_VALUE;
    int l=0;
    int r=0;
    int sum=0;
    while(r<n){
        //[l,r)
        sum+=nums[r++];
        while(sum>=target){
            min=Math.min(min,r-l);
            sum-=nums[l++];
        }
    }
    return min==Integer.MAX_VALUE ? 0 : min;
}

法二： binary search

O(n log(n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int minSubArrayLen(int target, int[] nums) {
    int lo = 1;
    int hi = nums.length;
    int result = 0;
    while(lo <= hi) {
        int mid = lo + (hi - lo)/2;
        if(isPossible(nums, target, mid)){
            hi = mid - 1;
            result = mid;
        }
        else lo = mid + 1;
    }
    return result;
}
boolean isPossible(int[] nums, int target, int size) {
    int sum = 0;
    int i = 0, j = 0;
    for(i = 0; i < size; i++) {
        sum += nums[i];
        if(sum >= target) return true;
    }
    while(i < nums.length) {
        sum = sum + nums[i++] - nums[j++];
        if(sum >= target)
            return true;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public int minSubArrayLen(int target, int[] nums) {
    int n=nums.length;
    int l=0;
    int r=n-1;
    int res=0;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(possible(nums,target,mid+1)){
            res=mid+1;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    return res;
}

boolean possible(int[] nums, int target, int size){
    int sum=0;
    int i=0;
    for (; i < size; i++) {
        sum+=nums[i];
        if(sum>=target){
            return true;
        }
    }
    //[0,end]
    int j=0;
    //[j,i]
    while(i<nums.length){
        sum+=nums[i++];
        sum-=nums[j++];
        if(sum>=target){
            return true;
        }
    }
    return false;
}

240. Search a 2D Matrix II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public boolean searchMatrix(int[][] matrix, int target) {
    int row=matrix.length;
    int col=matrix[0].length;
    for (int i = 0; i < row; i++) {
        if(find(matrix[i],target,col)){
            return true;
        }
    }
    return false;
}

boolean find(int[] arr, int target, int n){
    int left=0;
    int right=n-1;
    while(left<=right){
        int mid=left+(right-left)/2;
        if(arr[mid]==target){
            return true;
        }else if(arr[mid]<target){
            left=mid+1;
        }else{
            right=mid-1;
        }
    }
    return false;
}

278. First Bad Version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int firstBadVersion(int n) {
    int l=0;
    int r=n;
    int res=n;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(isBadVersion(mid)){
            res=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    return res;
}

287. Find the Duplicate Number

You must solve the problem without modifying the array nums and uses only constant extra space.

Approach 3: Negative Marking

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int findDuplicate(int[] nums) {
    int n=nums.length;
    int res=-1;
    for (int num : nums) {
        int cur=Math.abs(num);
        if(nums[cur]<0){
            res=cur;
            break;
        }
        nums[cur]*=-1;
    }
    for (int i = 0; i < n; i++) {
        if(nums[i]<0){
            nums[i]*=-1;
        }
    }
    return res;
}

Approach 7: Floyd’s Tortoise and Hare (Cycle Detection)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int findDuplicate(int[] nums) {
    int head=nums[0];
    int fast=head;
    int slow=head;
    do{
        fast=nums[nums[fast]];
        slow=nums[slow];
    }while(fast!=slow);
    int p=head;
    while(slow!=p){
        slow=nums[slow];
        p=nums[p];
    }
    return p;
}

41. First Missing Positive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int firstMissingPositive(int[] nums) {
    int n=nums.length;
    int i=0;
    while(i<n){
        //[1,2,3,...,n]
        int correct=nums[i]-1;
        if(nums[i]>0 && nums[i]<=n && nums[i]!=nums[correct]){
            int temp=nums[i];
            nums[i]=nums[correct];
            nums[correct]=temp;
        }else{
            i++;
        }
    }
    for (int j = 1; j <= n; j++) {
        if(nums[j-1]!=j){
            return j;
        }
    }
    return n+1;
}

392. Is Subsequence

Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public boolean isSubsequence(String s, String t) {
    List<Integer>[] lists=new List[26];
    for (int i = 0; i < t.length(); i++) {
        char c=t.charAt(i);
        if(lists[c-'a']==null){
            lists[c-'a']=new ArrayList<>();
        }
        lists[c-'a'].add(i);
    }
    int j=0;
    for (int i=0; i < s.length(); i++) {
        char cur=s.charAt(i);
        if(lists[cur-'a']==null){
            return false;
        }
        int pos=leftBound(j,lists[cur-'a']);
        if(pos==-1){
            return false;
        }
        j=lists[cur-'a'].get(pos)+1;
    }
    return true;
}

int leftBound(int target, List<Integer> list){
    int left=0;
    int right=list.size();
    while(left<right){
        //[left,right)
        int mid=left+(right-left)/2;
        if(target>list.get(mid)){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left==list.size() ? -1 : left;
}

792. Number of Matching Subsequences

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public int numMatchingSubseq(String s, String[] words) {
    int res=0;
    List<Integer>[] lists=new List[26];
    for (int i = 0; i < s.length(); i++) {
        char c=s.charAt(i);
        if(lists[c-'a']==null){
            lists[c-'a']=new ArrayList<>();
        }
        lists[c-'a'].add(i);
    }
    for (String word : words) {
        int j=0;
        int i = 0;
        for (; i < word.length(); i++) {
            int cur=word.charAt(i)-'a';
            if(lists[cur]==null){
                break;
            }
            int pos=leftBound(j,lists[cur]);
            if(pos==-1){
                break;
            }
            j=lists[cur].get(pos)+1;
        }
        if(i==word.length()){
            res++;
        }
    }
    return res;
}

int leftBound(int target, List<Integer> list){
    int left=0;
    int right=list.size();
    while(left<right){
        //[left,right)
        int mid=left+(right-left)/2;
        if(target>list.get(mid)){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left==list.size() ? -1 : left;
}

275. H-Index II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int hIndex(int[] citations) {
    //1,1,3
    int n=citations.length;
    int left=0;
    int right=n-1;
    while(left<=right){
        int mid=left+(right-left)/2;
        if(citations[mid]==n-mid){
            //[mid,n-1]
            return n-mid;
        }else if(citations[mid]>n-mid){
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    //[left,n-1]
    return n-left;
}

702. Search in a Sorted Array of Unknown Size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LeetCode702 {
     interface ArrayReader {
       int get(int index);
     }

    public int search(ArrayReader reader, int target) {
        int left=0;
        int right=10000;
        while(left<=right){
            //[left,right]
            int mid=left+(right-left)/2;
            int val=reader.get(mid);
            if(val==target){
                return mid;
            }else if(val>target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return -1;
    }
}

33. Search in Rotated Sorted Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int search(int[] nums, int target) {
    int n=nums.length;
    int left=0;
    int right=n-1;
    while(left<=right){
        int mid=(left+right)>>1;
        if(nums[mid]==target){
            return mid;
        }
        if(nums[left]<=nums[mid]){
            //[left,mid] sorted
            if(nums[mid]>target && nums[left]<=target){
                //target in sorted range
                right=mid-1;
            }else{
                left=mid+1;
            }
        }else{
            //[mid,right] sorted
            if(nums[mid]<target && nums[right]>=target){
                //target in sorted range
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
    }
    return -1;
}

81. Search in Rotated Sorted Array II

determine which part mid is, left or right

  1. if (left<mid || left==mid && left!=right), in left
  2. if (left>mid), in right
  3. if (left==mid==right), no idea, but we can safely exclude left and right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public boolean search(int[] nums, int target) {
    int n=nums.length;
    int left=0;
    int right=n-1;
    while(left<=right){
        int mid=(left+right)>>1;
        if(nums[mid]==target){
            return true;
        }
        if(nums[left]<nums[mid] || nums[left]==nums[mid] && nums[left]!=nums[right]){
            //[left,mid] sorted
            if(nums[left]<=target && nums[mid]>target){
                //target in sorted range
                right=mid-1;
            }else{
                left=mid+1;
            }
        }else if(nums[left]>nums[mid]){
            //[mid,right] sorted
            if(nums[mid]<target && nums[right]>=target){
                //target in sorted range
                left=mid+1;
            }else{
                right=mid-1;
            }
        }else{
            //left == mid ==right, don't know which part is sorted
            //but can safely narrow current interval to [left+1,right-1]
            left++;
            right--;
        }
    }
    return false;
}

二分答案法模板

找满足条件的最小整数值

1
2
3
4
5
6
7
8
9
10
11
while(left<right){
    //[left,right)
    int mid=(left+right)/2;
    //
    while(!condition){
        left=mid+1;
    }else{
        right=mid;
    }
}
return left; //or right, since left=right

找满足条件的最小小数值

1
2
3
4
5
6
7
8
9
10
while(right-left>1e-6){
    //[left,right)
    double mid=(left+right)/2;
    if(!valid){
        left=mid;
    }else{
        right=mid;
    }
}
return left;

找满足条件的最大整数值

1
2
3
4
5
6
7
8
9
10
11
while(left<right){
    //(left,right]
    int mid=(left+right+1)/2;
    //
    while(!condition){
        right=mid-1;
    }else{
        left=mid;
    }
}
return right;	//or left, since left=right

找满足条件的

2560. House Robber IV

https://leetcode.com/problems/house-robber-iv/discuss/3143697/JavaC%2B%2BPython-Binary-Search-O(1)-Space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int minCapability(int[] nums, int k) {
    int left= Arrays.stream(nums).min().getAsInt();
    int right= Arrays.stream(nums).max().getAsInt();
    int n=nums.length;
    while(left<right){
        //[left,right)
        int mid=left+(right-left)/2;
        int take=0;
        for (int i = 0; i < n; i++) {
            if(nums[i]<=mid){
                take++;
                i++;
            }
        }
        if(take<k){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left;
}

875. Koko Eating Bananas

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int minEatingSpeed(int[] piles, int h) {
    int n=piles.length;
    int left=1;
    int right=1000000000;
    while(left<right){
        //[left,right)
        int mid=left+(right-left)/2;
        int take=0;
        for (int i = 0; i < n; i++) {
            take+=piles[i]/mid;
            if(piles[i]%mid!=0){
                take++;
            }
            if(take>h){
                break;
            }
        }
        if(take>h){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left;
}

774. Minimize Max Distance to Gas Station

double也能玩二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public double minmaxGasDist(int[] stations, int k) {
    double left=0;
    double right=1e8;
    while(right-left>1e-6){
        //[left,right)
        double mid=(left+right)/2;
        if(!valid(stations,k,mid)){
            left=mid;
        }else{
            right=mid;
        }
    }
    return left;
}

boolean valid(int[] stations, int k, double p){
    int need=0;
    for (int i = 0; i < stations.length-1; i++) {
        need+=(stations[i+1]-stations[i])/p;
        if(need>k){
            break;
        }
    }
    return need<=k;
}

1011. Capacity To Ship Packages Within D Days

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int shipWithinDays(int[] weights, int days) {
    int n=weights.length;
    int left= Arrays.stream(weights).max().getAsInt();
    int right=(int)1e8;
    while(left<right){
        //[left,right)
        int mid=left+(right-left)/2;
        int take=0;
        int cur=0;
        for (int i = 0; i < n; i++) {
            cur+=weights[i];
            if(i<n-1 && cur+weights[i+1]>mid){
                cur=0;
                take++;
            }
        }
        take++;
        if(take>days){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left;
}

1231. Divide Chocolate

非常规！

  • 求最大可能值，而非最小可能值，因此需返回 right
  • 返回右边边界，注意 mid
  • 无需判断存在正好等于 mid的块 ？？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int maximizeSweetness(int[] sweetness, int k) {
    //maximize my piece
    //minimize others' pieces
    int n=sweetness.length;
    if(n==0){
        return 0;
    }
    int left=1;
    int right=(int)1e9;
    while(left<right){
        //(left,right]
        int mid=(right+left+1)/2;

        int cur=0;
        int count=0;
        for (int i = 0; i < n; i++) {
            cur+=sweetness[i];
            if(cur>=mid){
 
                count++;
                cur=0;
            }
        }
        if( count>k){
            left=mid;
        }else{
            right=mid-1;
        }
    }
    return right;	//or return left
}

1283. Find the Smallest Divisor Given a Threshold

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int smallestDivisor(int[] nums, int threshold) {
    int left=1;
    int right=(int)1e6;
    while(left<right){
        //[left,right)
        int mid=(left+right)/2;
        int sum=0;
        for (int num : nums) {
            sum+=num%mid==0 ? num/mid : num/mid+1;
            if(sum>threshold){
                break;
            }
        }
        if(sum>threshold){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left;
}

1482. Minimum Number of Days to Make m Bouquets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int minDays(int[] bloomDay, int m, int k) {
    int n=bloomDay.length;
    if(n<m || n<m*k){
        return -1;
    }
    int left=1;
    int right=(int)1e9;
    while(left<right){
        //[left,right)
        int mid=(left+right)/2;
        int count=0;
        int cur=0;
        for (int i = 0; i < n; i++) {
            if(bloomDay[i]<=mid){
                cur++;
                if(cur==k){
                    count++;
                    cur=0;
                }
            }else{
                cur=0;
            }
        }
        if(count<m){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left;
}

1539. Kth Missing Positive Number

easy题的edge case也不easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int findKthPositive(int[] arr, int k) {
    int n=arr.length;
    if(k<=arr[0]-1){
        return k;
    }
    k-=arr[0]-1;
    int cur=0;
    for (int i = 0; i < n-1; i++) {
        cur=arr[i+1]-arr[i]-1;
        if(k>cur){
            k-=cur;
        }else{
            return arr[i]+k;
        }
    }
    return arr[n-1]+k;
}

Could you solve this problem in less than O(n) complexity?

开背！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int findKthPositive(int[] arr, int k) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int pivot = left + (right - left) / 2;
        // If number of positive integers
        // which are missing before arr[pivot]
        // is less than k -->
        // continue to search on the right.
        if (arr[pivot] - pivot - 1 < k) {
            left = pivot + 1;
        // Otherwise, go left.
        } else {
            right = pivot - 1;
        }
    }

    // At the end of the loop, left = right + 1,
    // and the kth missing is in-between arr[right] and arr[left].
    // The number of integers missing before arr[right] is
    // arr[right] - right - 1 -->
    // the number to return is
    // arr[right] + k - (arr[right] - right - 1) = k + left
    return left + k;
}

1802. Maximum Value at a Given Index in a Bounded Array

https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/discuss/1119801/JavaC%2B%2BPython-Binary-Search

注意：

  • 为简便计算，初始所有值均减一
  • 最后返回值时需加上一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int maxValue(int n, int index, int maxSum) {
    maxSum -= n;
    int left = 0, right = maxSum, mid;
    while (left < right) {
        mid = (left + right + 1) / 2;
        if (test(n, index, mid) <= maxSum)
            left = mid;
        else
            right = mid - 1;
    }
    return left + 1;
}

private long test(int n, int index, int a) {
    //左边到0或到头
    int b = Math.max(a - index, 0);
    long res = (long)(a + b) * (a - b + 1) / 2;
    //右边到0或到头
    b = Math.max(a - ((n - 1) - index), 0);
    res += (long)(a + b) * (a - b + 1) / 2;
    return res - a;		//中间加了两次，需减掉
}

累加求和，超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int maxValue(int n, int index, int maxSum) {
    int left=1;
    int right=(int)1e9;
    while(left<right){
        //(left,right]
        int mid=(left+right+1)/2;
        int sum=0;
        int pre=mid;
        a:{            for (int i = index; i >= 0; i--) {
            sum+=pre==1 ? 1 : --pre;
            if(sum>maxSum){
                break a;
            }
        }
            pre=mid;
            for (int i = index+1; i < n; i++) {
                sum+=pre==1 ? 1 : --pre;
                if(sum>maxSum){
                    break a;
                }
            }
        }

        if(sum<=maxSum){
            left=mid;
        }else{
            right=mid-1;
        }
    }
    return right;
}

2226. Maximum Candies Allocated to K Children

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int maximumCandies(int[] candies, long k) {
    long sum=0;
    for (int candy : candies) {
        sum+=candy;
    }
    if(sum<k){
        return 0;
    }
    int left=1;
    int right= Arrays.stream(candies).max().getAsInt();
    while(left<right){
        //(left,right]
        int mid=(left+right+1)/2;
        long count=0;
        for (int candy : candies) {
            count+=candy/mid;
            if(count>=k){
                break;
            }
        }
        if(count<k){
            right=mid-1;
        }else{
            left=mid;
        }
    }
    return right;
}

719. Find K-th Smallest Pair Distance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int smallestDistancePair(int[] nums, int k) {
    int n=nums.length;
    Arrays.sort(nums);
    //kth smallest dif =>
    //smallest dif satisfying count>=k
    //count: number of pairs with distance <= mi
    int low=0;
    int high=nums[n-1]-nums[0];
    while(low<high){
        int mid=(low+high)/2;
        int count=0;
        int left=0;
        for (int right = 0; right < n; right++) {
            while(nums[right]-nums[left]>mid){
                left++;
            }
            //([left,right-1] right)
            count+=right-left;
        }
        if(count<k){
            low=mid+1;
        }else{
            high=mid;
        }
    }
    return low;
}

644. Maximum Average Subarray II

二分+sliding window，太妙了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public double findMaxAverage(int[] nums, int k) {
    double left=-10000;
    double right=10000;
    while(right-left>1e-5){
        double mid=(left+right)/2;
        if(check(nums,k,mid)){
            left=mid;
        }else{
            right=mid;
        }
    }
    return left;
}

boolean check(int[] nums, int k, double mid){
    double sum=0;
    for (int i = 0; i < k; i++) {
        sum+=nums[i]-mid;
    }
    if(sum>=0){
        return true;
    }
    int n=nums.length;
    double prev=0;
    for (int i = k; i < n; i++) {
        //[i-k+1,i]
        sum+=nums[i]-mid;
        prev+=nums[i-k]-mid;
        if(prev<0){
            sum-=prev;
            prev=0;
        }
        if(sum>=0){
            return true;
        }
    }
    return false;
}

1552. Magnetic Force Between Two Balls

找满足条件的最大值，模板题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int maxDistance(int[] position, int m) {
    //maximize minimum gap
    Arrays.sort(position);
    int n=position.length;
    int left=1;
    int right=position[n-1];
    while(left<right){
        //(left,right]
        int mid=(left+right+1)/2;
        int count=1;
        int pre=position[0];
        for (int i = 1; i < n; i++) {
            if(position[i]-pre>=mid){
                pre=position[i];
                count++;
                if(count>=m){
                    break;
                }
            }
        }
        if(count<m){//invalid
            right=mid-1;
        }else{//valid, try larger gap
            left=mid;
        }
    }
    return left;
}

1428. Leftmost Column with at Least a One

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class LeetCode1428 {
     interface BinaryMatrix {
      public int get(int row, int col);
      public List<Integer> dimensions();
    }
    int row;
     int col;
     int res;
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        List<Integer> list=binaryMatrix.dimensions();
        row=list.get(0);
        col=list.get(1);
        res=col;
        for (int i = 0; i < row; i++) {
            search(binaryMatrix,i);
        }
        return res==col ? -1 : res;
    }

    void search(BinaryMatrix binaryMatrix, int i){
         int left=0;
         int right=col-1;
         while(left<right){
             //[left,right)
             int mid=(left+right)/2;
             int val=binaryMatrix.get(i,mid);
             if(val==0){
                 left=mid+1;
             }else{
                 right=mid;
             }
         }
         if(binaryMatrix.get(i,left)==1){
             res=Math.min(res,left);
         }
    }
}

528. Random Pick with Weight

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    Random rand;
    int total;
    int n;
    int[] prefix;
    public Solution(int[] w) {
        rand=new Random();
        n=w.length;
        prefix=new int[n];
        prefix[0]=w[0];
        for (int i = 1; i < n; i++) {
            prefix[i]=prefix[i-1]+w[i];
        }
        total= Arrays.stream(w).sum();
    }

    public int pickIndex() {
        int target=rand.nextInt(total)+1;   //[1,total]
        return binarySearch(target);
    }

    int binarySearch(int target){
        //[1,a] [a+1,b] [b+1,c]
        //smallest a where a >=target
        int left=0;
        int right=n;
        while(left<right){
            //[left,right)
            int mid=(left+right)/2;
            if(prefix[mid]<target){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return left;
    }
}

540. Single Element in a Sorted Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int singleNonDuplicate(int[] nums) {
    //a a b c c
    //a b b c c
    //a a b b c
    //find the smallest even index  where nums[i]!=nums[i+1]
    int n=nums.length-1;
    int left=0;
    int right=n;
    while(left<right){
        //[left,right)
        int mid=(left+right)/2;
        if((mid&1)==1){
            mid--;
        }
        if(nums[mid]==nums[mid+1]){
            left=mid+2;
        }else{
            right=mid;
        }
    }
    return nums[left];
}

410. Split Array Largest Sum

classic min-max: Return the minimized largest sum of the split.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int splitArray(int[] nums, int k) {
    int n=nums.length;
    int l=0;
    int r=(int)1e9;
    //the smallest sum that satisfies
    while(l<r){
        //[l,r)
        int mid=(l+r)>>1;
        int count=0;
        int sum=0;
        int i=0;
        for (; i < n; i++) {
            if(nums[i]>mid){
                break;
            }
            sum+=nums[i];
            if(sum>mid){
                count++;
                sum=nums[i];
            }
        }
        count++;
        if(i<n || count>k){//not valid
            l=mid+1;
        }else{
            r=mid;
        }
    }
    return l;
}

2616. Minimize the Maximum Difference of Pairs

经典binary+greedy解min-max

https://leetcode.com/problems/minimize-the-maximum-difference-of-pairs/discuss/3395952/in-case-you-are-wondering-why-greedy-works-for-this-problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int minimizeMax(int[] nums, int p) {
    int n=nums.length;
    Arrays.sort(nums);
    int left=0;
    int right=nums[n-1]-nums[0];
    while(left<right){
        int mid=(left+right)>>1;
        int count=0;
        for(int i=1; i<n && count<p; i++){
            if(nums[i]-nums[i-1]<=mid){
                count++;
                i++;
            }
        }
        if(count<p){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left;
}

1891. Cutting Ribbons

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int maxLength(int[] ribbons, int k) {
    Arrays.sort(ribbons);
    int n=ribbons.length;
    int l=0;
    int r=100000;
    while(l<r){
        //(l,r]
        int mid=(l+r+1)/2;
        int count=0;
        for (int i = n-1; i >=0; i--) {
            int num=ribbons[i];
            count+=num/mid;
            if(count>=k || num<mid){
                break;
            }
        }
        if(count<k){
            r=mid-1;
        }else{
            l=mid;
        }
    }
    return l;
}

1498. Number of Subsequences That Satisfy the Given Sum Condition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public int numSubseq(int[] nums, int target) {
    Arrays.sort(nums);
    int res=0;
    int mod=(int)1e9+7;
    int n=nums.length;
    int[] pow=new int[n+1];
    pow[0]=1;
    for (int i = 1; i <= n; i++) {
        pow[i]=(pow[i-1]<<1)%mod;
    }
    for (int left = 0; left < n; left++) {
        //nums[left]+nums[right]<=target
        int right=findFirstSmall(nums,target-nums[left])-1;
        //[left,right]
        if(right-left>=0){
            res+=pow[right-left];
            res%=mod;
        }
    }
    return res;
}

private int findFirstSmall(int[] nums, int target){
    //find smallest idx where nums[idx]>target
    int left=0;
    int right=nums.length;
    while(left<right){
        //[left,right)
        int mid=(left+right)/2;
        if(nums[mid]<=target){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left;
}

2448. Minimum Cost to Make Array Equal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public long minCost(int[] nums, int[] cost) {
    int left= Arrays.stream(nums).min().getAsInt();
    int right=Arrays.stream(nums).max().getAsInt();
    long res=0;
    while(left<right){
       int mid=(left+right)/2;
       long cost1=helper(nums,cost,mid);
       long cost2=helper(nums,cost,mid+1);
       if(cost1>cost2){
           res=cost2;
           left=mid+1;
       }else{
           res=cost1;
           right=mid;
       }
    }
    return res;
}

private long helper(int[] nums, int[] cost, int target){
    long res=0;
    for (int i = 0; i < nums.length; i++) {
        res+=1L*Math.abs(target-nums[i])*cost[i];
    }
    return res;
}

1870. Minimum Speed to Arrive on Time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int minSpeedOnTime(int[] dist, double hour) {
    //binary search min
    int n=dist.length;
    int left=1;
    int right=(int)1e7+1;
    while(left<right){
        int mid=(left+right)/2;
        //[left,right)
        double t=0;
        int i=0;
        for (; i < n-1; i++) {
            t+=dist[i]%mid==0 ? dist[i]/mid : dist[i]/mid+1;
            if(t>hour){
                break;
            }
        }
        t+=(double)dist[i]/mid;
        if(t>hour){
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left==(int)1e7+1 ? -1 : left;
}

153. Find Minimum in Rotated Sorted Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int findMin(int[] nums) {
    int n=nums.length;
    if(nums[0]<nums[n-1]){
        return nums[0];
    }
    //[left,mid,right]
    //1 2 4 5 6 7 0 
    //7 0 1 2 4 5 6
    //find the smallest i where nums[i]<nums[0]
    int left=0;
    int right=n-1;
    while(left<right){
        int mid=(left+right)>>1;
        if(nums[mid]>=nums[0]){
            //invalid, search right
            left=mid+1;
        }else{
            //valid, search left
            right=mid;
        }
    }
    return nums[left];
}