当前位置：网站首页>[刷题] 二分答案求解

[刷题] 二分答案求解

2022-07-26 18:14:00 【20要继续努力哦!】

二分答案

秋招对我好点!!!

前言

在刷LintCode进阶必刷编程80题,遇到了二分答案的题目,之前有遇到过二分法解决问题的题目,但是二分答案确实见得不多(可能我比较菜狗),而且这些题大部分都比较难,第一眼写不出方法来,特此记录一下解题方法和过程!

二分答案

二分答案是binary search里面比较难的题型，也就是，直接求一个最值很难，但是我们可以很简单的在解空间做判定性问题，比如能不能，行不行，大了还是小了，return true or false，从而缩小解空间，记住，这种方法有个前提条件就是有单调递增或者递减的性质，才能用。这也是binary search使用的条件；

总结一下,二分答案的题目求解需要包含:

  1. 答案有单调递增或者递减的性质

例如,183.木材加工这题,需要求满足条件的木头的最大长度,很显然,如果len是满足条件的,那么len-1必定也满足条件,因此这题类似与求解有序数组元素的右边界

  1. 解空间
    二分答案与求解元素边界问题不一样的是,需要自己去获取解空间,然后依据条件去判断如果去缩小空间

  2. 有一个值得注意的是 空间的限定范围:

while(left<right){
      // 为了防止死循环
            int mid = (right-left)/2 + left;

            // 判断是否满足条件
            if(isOK(l, k,mid)){
    
                left = mid;
            }else{
    
                right = mid;  // 如果不满足 向左移动
            }
        }

不同于求边界问题,相同的元素有很多个,这里满足条件的元素只有一个,因此在缩小范围的时候,我们需要保证mid的取值( left = mid 或者 right = mid),然后为了避免死循环,限定条件则为(while(left<right))

以下给出求解有序数组元素右边界的核心代码

// 求解右边界
while(left<=right){
      
            int mid = (right-left)/2 + left;
            if(nums[mid]<=target){
    
                left = mid + 1;
            }else{
    
                right = mid - 1; 
            }
        }

题目解析

963 · 评委出题

题目链接

描述

题目难度分为“简单题”、“中等题”、“难题”三个等级。评委们已经出好了EE 道简单题， MM 道中等题， HH 道难题。然后评委们又出了 EMEM道“简中”题和 MHMH 道“中难”题。所谓的“简中题”是指该类型的题既可以归类为“简单题”也可以归类为“中等题”。所谓的“中难题”是指该类型的题既可以归类为“中等题”也可以归类为“难题”。评委们规定：一场比赛必须包含 3 道题，其中 1 题是“简单题”， 1 题是“中等题”， 1 题是“难题”。每道题目至多只能出现在一场比赛中。现在，评委们最多可以组织多少场比赛？

解析

从题目可以算出,组织比赛的场数只有一个范围的,(0-min(min(E+EM,EM+M+MH),MH+H)),而在这其中,小于等于某个数的场数都能符合条件,因此二分搜索可以起到帮助!

代码

class Solution {
    
public:
     bool helper(long long E, long long EM, long long M, long long MH, long long H,long long int target){
    
     
         if(target<min(min(E,M),H)){
    
             return true;
         }
		// 简单题 
         if(target>E){
    
             EM = EM - (target-E);
         }
         if(EM<0){
    
             return false;
         }
		// 中等题 
         if(target>H)
         {
    
             MH = MH-(target-H);
         }
         if(MH<0){
    
             return false;
         }
		// 困难题 
         if(M+MH+EM< target){
    
             return false;
         }
         return true;
     }
    long long theNumberOfContests(long long E, long long EM, long long M, long long MH, long long H) {
    
        // write your code here.
        long long int end = min(min(E+EM,EM+M+MH),MH+H);
        long long int start  = 0;
        while(start+1<end){
    
            long long int mid = start+(end-start)/2;
            if(helper(E,EM,M,MH,H,mid))
            {
    
                start = mid;
            }
            else{
    
                end = mid;
            }
        }
        if(helper(E,EM,M,MH,H,end)){
    
            return end;
        }
        else{
    
            return start;
        }
    }
};

437 · 书籍复印

题目链接

描述
给定n本书，第i本书有pages[i]页。有k个人来抄这些书。

这些书排成一行，每个人都可以索取连续一段的书。例如，一个抄书人可以连续地将书从第i册复制到第j册，但是他不能复制第1册、第2册和第4册（没有第3册）。

他们在同一时间开始抄书，每抄一页书都要花1分钟。为了让最慢的抄书人能在最早的时间完成书的分配，最好的策略是什么？

请返回最慢抄书人花费的最短时间。

解析

花费时间的最大值和最小值有个区间,(min,max) = (最长的个人时间,总时间)

二分法不断缩小范围 + 判断是否满足条件!

代码

class Solution
{
    
  public:
    int copyBooks(vector<int> &pages, int k)
    {
    
        if (pages.size() == 0)
        {
    
            return 0;
        }

        int total = 0;
        int max = pages[0];
        for (int i = 0; i < pages.size(); i++)
        {
    
            total += pages[i];
            if (max < pages[i])
            {
    
                max = pages[i];
            }
        }

        // 左右 最小和最大
        int start = max;
        int end = total;

        while (start + 1 < end)  // 
        {
    
            int mid = (end - start) / 2 + start;
            if (countCopiers(pages, mid) > k) // 需要的人数大于k 那就把花费时间给增大
            {
    
                start = mid;
            }
            else
            {
    
                end = mid;
            }
        }

        // 最终结果
        if (countCopiers(pages, start) <= k)
        {
    
            return start;
        }

        return end;
    }

    int countCopiers(vector<int> &pages, int limit)
    {
    
        if (pages.size() == 0)
        {
    
            return 0;
        }

        int copiers = 1;
        int sum = pages[0]; // limit is always >= pages[0]
        for (int i = 1; i < pages.size(); i++)
        {
    
            if (sum + pages[i] > limit)
            {
    
                copiers++;
                sum = 0;
            }
            sum += pages[i];
        }

        return copiers;
    }
};

319 · 方阵排队

题目链接

描述

给定一个长度为N的数组height代表N个人的身高
请你选出一部分人组成方阵(即矩阵的行数与列数相同),并且每一行的人的身高差不超过2。
请问最多能选取多少人参加方阵

解析

其实这题也能用二分法

代码

class Solution {
    
public:
    /** * @param height: n people's height * @return: return the maxium number of people in square matrix */
     // 获取最大行
     int getRow(vector<int> &height,int len){
    
         int i=0;
         int count =0;

         while(i+len<=height.size()){
    

             // 移动窗口
             if(height[i+len-1]-height[i]>2){
    
                 i++;
                 continue;
             }

             if(height[i+len-1]-height[i]<=2){
    
                i+=len;
                count++;
             }

             if(len==count) return count;
         }
        return count;
     }


    int maxPeopleNumber(vector<int> &height) {
    
        // write your code here
        // 做出来去吃饭
        // 方阵
        // 首先升序排列
        sort(height.begin(),height.end());
        int len = sqrt(height.size());

        // 求解列 能达到的最大行
        while(len>0){
    
            int row = getRow(height,len);
            if(row==len) return row*len;
            if(row<len) len--;
        }

        return 0;
    }
};

183 · 木材加工

题目链接

描述

有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。给定L和k，你需要计算能够得到的小段木头的最大长度。

解析

木头有长短范围限制 + 满足条件

有一说一,这类题目类似遍历找答案,只不过结果有序,就可以用二分去求解!

代码

class Solution {
    
public:

     bool isOK(vector<int> &l, int k,int mid){
    
         // 判断能不能
         int sum = 0;
         for(const int len : l){
    
            sum += len/mid;
         }
         return sum>=k;   // 如果大于等于k 就肯定会可以
     }


    int woodCut(vector<int> &l, int k) {
    
        // write your code here
        // 使用二分法 判断情况是否满足条件
        if(l.size()==0) return 0;
        int maxLen= 0;
        for(const int len : l){
    
            maxLen = max(maxLen,len);
        }

        int left = 0,right = maxLen;  // right不能+1

        while(left+1<right){
      // 为了防止
            int mid = (right-left)/2 + left;

            // 判断是否满足条件
            if(isOK(l, k,mid)){
    
                left = mid;
            }else{
    
                right = mid;  // 如果不满足 向左移动
            }
        }

        // 判断条件
        if(isOK(l, k,right)){
    
            return right;
        }
        return left;
    }
};
原网站

版权声明
本文为[20要继续努力哦!]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_43147335/article/details/125891619

边栏推荐

猜你喜欢

随机推荐