二分查找应用

发表于 | 分类于 ， ， |

二分查找应用：珂珂吃香蕉、在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;
    }
};
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
func minEatingSpeed(piles []int, h int) int {
    n := len(piles)
    maxVal := 0
    //找到piles中的最大值
    for i := 0; i < n; i++ {
        if piles[i] > maxVal {
            maxVal = piles[i]
        }
    }
    left := 1
    right := maxVal
    for left <= right {
        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 的速度吃香蕉，返回吃完这堆香蕉需要的时间
func fun(piles []int, x int) int {
    sum := 0
    n := len(piles)
    for 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;
    }
};
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
func shipWithinDays(weights []int, days int) int {
    n := len(weights)
    sum := 0
    maxVal := 0
    for i := 0; i < n; i++ {
        if weights[i] > maxVal {
            maxVal = weights[i]
        }
        sum += weights[i]
    }
    
    left := maxVal
    right := sum
    for left <= right {
        mid := left + (right-left)/2
        if fun(weights, mid) > days {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return left
}

func fun(weights []int, x int) int {
    days := 1
    sum := 0
    for i := 0; i < len(weights); 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;
    }
};
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
func splitArray(nums []int, m int) int {
    n := len(nums)
    maxVal := 0
    sum := 0
    for i := 0; i < n; i++ {
        if nums[i] > maxVal {
            maxVal = nums[i]
        }
        sum += nums[i]
    }
    left := maxVal
    right := sum
    for left <= right {
        mid := left + (right-left)/2
        if fun(nums, mid) > m {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return left
}

func fun(nums []int, x int) int {
    m := 1
    sum := 0
    for i := 0; i < len(nums); 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;
    }
};
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
func maximumCandies(candies []int, k int64) int {
    n := len(candies)
    maxVal := 0
    for i := 0; i < n; i++ {
        if candies[i] > maxVal {
            maxVal = candies[i]
        }
    }
    left := 1
    right := maxVal
    for left <= right {
        mid := left + (right-left)/2
        if fun(candies, k, mid) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return right
}

func fun(candies []int, k int64, x int) bool {
    n := len(candies)
    var res int64 = 0
    for i := 0; i < n; i++ {
        res += int64(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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func findMin(nums []int) int {
    //数组中最后一个元素，最小值右边的一定比它小，最小值左边的一定比它大
    n := len(nums)
    left := 0
    right := n - 1
    for left < right {
        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;
    }
};
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
func search(nums []int, target int) int {
    n := len(nums)
    k := 1
    for k < n && nums[k] >= nums[k-1] {
        k++
    }
    res := -1

    left_val := binarySearch(nums, target, 0, k-1)
    right_val := binarySearch(nums, target, k, n-1)

    if left_val != -1 {
        res = left_val
    }
    if right_val != -1 {
        res = right_val
    }

    return res
}

//二分查找
func binarySearch(nums []int, target int, low int, high int) int {
    left := low
    right := high
    for left <= right {
        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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func peakIndexInMountainArray(arr []int) int {
    n := len(arr)
    left := 0
    right := n - 1
    
    for left < right {
        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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func findPeakElement(nums []int) int {
    n := len(nums)
    left := 0
    right := n - 1
    for left < right {
        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;
    }
};
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
func findDuplicate(nums []int) int {
    n := len(nums)

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

        //统计nums中小于等于 mid 的元素个数
        count := 0
        for _, num := range 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;
    }
};
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
func maxArea(height []int) int {
    n := len(height)
    res := 0

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

    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
-------------本文结束 感谢阅读-------------
0%