首页 🍒LeetCode,🐶算法

题目

Ftf4bTO9zY.png

思路

可以写一个判断函数jud:
判断天数为day的时候能不能制作m束花。
能则返回true,否则false。

如果从第一天开始判断到最后一天,其中会出现很多false和true,如果从第一天开始遍历当遇到第一个true时的天数即是答案。但是会出现很多false导致超时,所以可以采用二分的思想,left为数组中最小的一天,right为数组中最大的一天。
每次让mid当参数day去判断,返回fasle则右移反之左移。

class Solution {
public:
    bool jud(vector<int> &bloomDay, int m, int k, int day) {
        int num = 0;
        int n = 0;
        for (int i = 0; i < bloomDay.size() && num < m; i++) {
            if (bloomDay[i] <= day) {
                n++;
                if (n == k) {
                    num++;
                    n = 0;
                }
            }
            else {
                n = 0;
            }
        }
        if (num >= m) return true;
        return false;
    }

    int minDays(vector<int> &bloomDay, int m, int k)
    {
        int res = 0;
        if (m * k > bloomDay.size()) return -1;
        vector<int> arr = bloomDay;
        sort(arr.begin(), arr.end());
        int left = arr[0], right = arr[arr.size() - 1];
        while (left < right) {
            int mid = (left + right) / 2;
            if (jud(bloomDay, m, k, mid) == true) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }
};



文章评论

    六天 访客ChromeWindows
    26天 前   回复

    该更新leetcode了