二分查找应用

发表于 | 分类于 ， ， |

二分查找应用：珂珂吃香蕉、在D天内送达包裹的能力、分割数组的最大值、每个小孩最多能分到多少糖果、寻找旋转排序数组中的最小值、搜索旋转排序数组

875.珂珂吃香蕉

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

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
class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int n=piles.size();
        int maxVal=0;
        //找到piles中的最大值
        for(int i=0;i<n;i++){
            if(piles[i]>maxVal){
                maxVal=piles[i];
            }
        }
        int left=1;
        int right=maxVal;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(fun(piles, mid)>h){
                left=mid+1;
            }else if(fun(piles, mid)<h){
                right=mid-1;
            }else{
                //收缩右边界
                right=mid-1;
            }
        }
        return left;
    }
    //以 x/h 的速度吃香蕉，返回吃完这堆香蕉需要的时间
    int fun(vector<int>& piles, int x){
        int sum=0;
        int n=piles.size();
        for(int i=0;i<n;i++){
            sum+=piles[i]/x;
            if(piles[i]%x>0){
                sum++;
            }
        }
        return sum;
    }
};

1011.在D天内送达包裹的能力

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。

示例1：

1
2
输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5
输出：15
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 {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int n=weights.size();
        int sum=0;
        int maxVal=0;
        for(int i=0;i<n;i++){
            if(weights[i]>maxVal){
                maxVal=weights[i];
            }
            sum+=weights[i];
        }
        
        int left=maxVal;
        int right=sum;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(fun(weights, mid)>days){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return left;
    }
    int fun(vector<int>& weights, int x){
        int days=1;
        int sum=0;
        for(int i=0;i<weights.size();i++){
            sum += weights[i];
            if(sum>x){
                days++;
                sum=weights[i];
            }
        }
        return days;
    }
};

410.分割数组的最大值

给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

思路：这道题和前一道1011的运输问题是一模一样的。改写一下题目：你只有一艘货船，现在有若干货物，每个货物的重量是nums[i]，现在你需要在m天内将这些货物运走，请问你的货船的最小载重是多少？

货船每天运走的货物就是nums的一个子数组，在m天内运完就是将nums划分成m个子数组，让货船的载重尽可能小，就是让所有子数组中最大的那个子数组元素之和尽可能小。

代码跟上面那个题一模一样的

二分搜索，最小值为nums中的最大值，最大值为nums中所有值的和

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
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int n=nums.size();
        int maxVal=0;
        int sum=0;
        for(int i=0;i<n;i++){
            if(nums[i]>maxVal){
                maxVal=nums[i];
            }
            sum +=nums[i];
        }
        int left=maxVal;
        int right=sum;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(fun(nums, mid)>m){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return left;
    }
    int fun(vector<int>& nums, int x){
        int m=1;
        int sum=0;
        for(int i=0;i<nums.size();i++){
            sum += nums[i];
            if(sum>x){
                m++;
                sum=nums[i];
            }
        }
        return m;
    }
};

2226.每个小孩最多能分到多少糖果

给你一个 下标从 0 开始 的整数数组 candies 。数组中的每个元素表示大小为 candies[i] 的一堆糖果。你可以将每堆糖果分成任意数量的 子堆 ，但 无法 再将两堆合并到一起。

另给你一个整数 k 。你需要将这些糖果分配给 k 个小孩，使每个小孩分到 相同 数量的糖果。每个小孩可以拿走 至多一堆 糖果，有些糖果可能会不被分配。

返回每个小孩可以拿走的 最大糖果数目 。

1
2
3
示例1：
输入：candies = [5,8,6], k = 3
输出：5
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
class Solution {
public:
    int maximumCandies(vector<int>& candies, long long k) {
        int n=candies.size();
        int maxVal=0;
        for(int i=0;i<n;i++){
            if(candies[i]>maxVal){
                maxVal=candies[i];
            }
        }
        int left=1;
        int right=maxVal;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(fun(candies, k, mid)){
                left=mid+1;
            }else{
                right=mid-1;
            }
        } 
        return right;
    }
    bool fun(vector<int>& candies, long long k, int x){
        int n=candies.size();
        long long res=0;
        for(int i=0;i<n;i++){
            res += candies[i]/x; //注意x不能等于0；
        }
        return res>=k;
    }
};

153.寻找旋转排序数组中的最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findMin(vector<int>& nums) {
        //数组中最后一个元素，最小值右边的一定比它小，最小值左边的一定比它大
        int n=nums.size();
        int left=0;
        int right=n-1;
        while(left < right){
            int mid=left+(right-left)/2;
            if(nums[mid]<nums[right]){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return nums[left];
    }
};

33.搜索旋转排序数组

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n=nums.size();
        int k=1;
        while(k<n && nums[k] >= nums[k-1]) k++;
        int res=-1;

        int left_val = BinarySearch(nums, target, 0, k-1);
        int right_val = BinarySearch(nums, target, k, n-1);

        if(left_val!=-1) res=left_val;
        if(right_val!=-1) res=right_val;

        return res;
    }
    //二分查找
    int BinarySearch(vector<int>& nums, int target, int low, int high){

        int left=low;
        int right=high;
        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;
    }
};

852.山脉数组的顶峰索引

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

162.寻找峰值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n=nums.size();
        int left=0;
        int right=n-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]<nums[mid+1]){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return left;
    }
};

287.寻找重复数

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
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n=nums.size(); 

        //在[1...n]查找nums中重复的元素
        int left=1;
        int right=n;
        while(left<right){
            int mid=left+(right-left)/2;

            //统计nums中小于等于 mid 的元素个数
            int count=0;
            for(int num : nums){
                if(num<=mid){
                    count++;
                }
            }

            if(count>mid){
                //下一轮搜索的区间[left...mid]
                right=mid;
            }else{
                //下一轮搜索的区间[mid+1, right]
                left=mid+1;
            }
        }
        return left;
    }
};

11.盛水最多的容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxArea(vector<int>& height) {
        
        int n=height.size();
        int res = 0;

        int left = 0;
        int right = n-1;
        while(left<right){
            res = max(res, min(height[left],height[right])*(right-left));
            if(height[left]<height[right]) left++;
            else right--;
        }

        return res;
    }
};
-------------本文结束 感谢阅读-------------
0%