专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近一网友发文称自己的离职证明上有负面消息，该怎么办？不知道大家离职的时候有没有遇到这种情况，如果遇到这种情况，说明这hr很不专业，可以沟通让她修改，如果拒不修改，直接起诉就行了。
根据《劳动合同法》第 50 条、《劳动合同法实施条例》第 24 条，离职证明需载明：劳动合同期限，解除 / 终止劳动合同日期，工作岗位，在本单位的工作年限。禁止记载：离职原因、员工评价、纪律处分等负面信息（除非双方协商一致且不违反法律）。若公司擅自写入 “旷工”“能力不足” 等非法定内容，可能构成违法约定或侵犯劳动者权益（如影响后续求职）。
所以离职证明上是不能对员工有负面评价的，离职争取自己权益的时候不要怕离职证明有负面消息而瞻前顾后，投鼠忌器。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第1482题：制作 m 束花所需的最少天数，难度是中等。
给你一个整数数组 bloomDay，以及两个整数 m 和 k 。现需要制作 m 束花。制作花束时，需要使用花园中相邻的 k 朵花 。
花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好可以用于一束花中。请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。
示例1：
输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3 输出：12 解释：要制作 2 束花，每束需要 3 朵。 花园在 7 天后和 12 天后的情况如下： 7 天后：[x, x, x, x, _, x, x] 可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。 12 天后：[x, x, x, x, x, x, x] 显然，我们可以用不同的方式制作两束花。
示例2：
输入：bloomDay = [1,10,3,10,2], m = 3, k = 2 输出：-1 解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。
bloomDay.length == n
1 <= n <= 10^5
1 <= bloomDay[i] <= 10^9
1 <= m <= 10^6
1 <= k <= n
问题分析
这题说的是制作每束花需要 k 朵花，并且每朵花有一个开花的时间，问制作 m 束花需要的最少天数。
制作 m 束花总共需要 k*m 朵花，如果总的花束不够，就算等到天荒地老也制作不了 m 束花，我们可以直接返回 -1 。
如果花够了，这里怎么来查找最小时间呢？这里我们可以通过二分法查找，二分查找的最小值和最大值分别是数组中元素的最小值和最大值。每次取中间的值，检查能不能制作 m 束花。
比如区间是[10,100]，我们可以先判断55能不能满足条件，如果不能，则区间范围变成[56,100]，如果能满足条件，则区间范围变成[10,55]，注意这里的55不能排除掉，通过二分法查找，最后区间长度为 1 的时候，这个区间的值就是我们要求的结果。
JAVA：
public int minDays(int[] bloomDay, int m, int k) { int n = bloomDay.length; if (n < 1L * m * k)// 防止溢出，转为long类型 return -1; // 找出数组中的最大值和最小值。 int low = Integer.MAX_VALUE, high = 0; for (int num : bloomDay) { low = Math.min(low, num); high = Math.max(high, num); } while (low < high) {// 二分查找。 int mid = (high - low) / 2 + low; if (check(bloomDay, mid, m, k)) { high = mid; } else { low = mid + 1; } } return low; } // 检查days天之后是否可以制作 m 束花。 private boolean check(int[] bloomDay, int days, int m, int k) { int cnt = 0;// 花束的数量 int flowers = 0;// 制作花束使用的花朵 int n = bloomDay.length; for (int i = 0; i < n && cnt < m; i++) { if (bloomDay[i] <= days) {// 第 i 朵盛开了 flowers++; if (flowers == k) { cnt++;// k 朵花制作一个花束。 flowers = 0; } } else {// 第 i 朵还没有盛开。 flowers = 0; } } return cnt >= m; }C++：
public: int minDays(vector
&bloomDay, int m, int k) { int n = bloomDay.size(); if (n < 1L * m * k)// 防止溢出，转为long类型 return-1; // 找出数组中的最大值和最小值。 int low = INT_MAX, high = 0; for (int num: bloomDay) { low = min(low, num); high = max(high, num); } while (low < high) {// 二分查找。 int mid = (high - low) / 2 + low; if (check(bloomDay, mid, m, k)) { high = mid; } else { low = mid + 1; } } return low; } // 检查days天之后是否可以制作 m 束花。 bool check(vector
&bloomDay, int days, int m, int k) { int cnt = 0;// 花束的数量 int flowers = 0;// 制作花束使用的花朵 int n = bloomDay.size(); for (int i = 0; i < n && cnt < m; i++) { if (bloomDay[i] <= days) {// 第 i 朵盛开了 flowers++; if (flowers == k) { cnt++;// k 朵花制作一个花束。 flowers = 0; } } else {// 第 i 朵还没有盛开。 flowers = 0; } } return cnt >= m; }
笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴