專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

最近一網(wǎng)友發(fā)文稱自己的離職證明上有負(fù)面消息，該怎么辦？不知道大家離職的時(shí)候有沒有遇到這種情況，如果遇到這種情況，說明這hr很不專業(yè)，可以溝通讓她修改，如果拒不修改，直接起訴就行了。

根據(jù)《勞動(dòng)合同法》第 50 條、《勞動(dòng)合同法實(shí)施條例》第 24 條，離職證明需載明：勞動(dòng)合同期限，解除 / 終止勞動(dòng)合同日期，工作崗位，在本單位的工作年限。禁止記載：離職原因、員工評(píng)價(jià)、紀(jì)律處分等負(fù)面信息（除非雙方協(xié)商一致且不違反法律）。若公司擅自寫入 “曠工”“能力不足” 等非法定內(nèi)容，可能構(gòu)成違法約定或侵犯勞動(dòng)者權(quán)益（如影響后續(xù)求職）。

所以離職證明上是不能對(duì)員工有負(fù)面評(píng)價(jià)的，離職爭(zhēng)取自己權(quán)益的時(shí)候不要怕離職證明有負(fù)面消息而瞻前顧后，投鼠忌器。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第1482題：制作 m 束花所需的最少天數(shù)，難度是中等。

給你一個(gè)整數(shù)數(shù)組 bloomDay，以及兩個(gè)整數(shù) m 和 k 。現(xiàn)需要制作 m 束花。制作花束時(shí)，需要使用花園中相鄰的 k 朵花 。

花園中有 n 朵花，第 i 朵花會(huì)在 bloomDay[i] 時(shí)盛開，恰好可以用于一束花中。請(qǐng)你返回從花園中摘 m 束花需要等待的最少的天數(shù)。如果不能摘到 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 朵盛開的花，因?yàn)樗鼈儾幌噜彙?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 朵花，并且每朵花有一個(gè)開花的時(shí)間，問制作 m 束花需要的最少天數(shù)。

制作 m 束花總共需要 k*m 朵花，如果總的花束不夠，就算等到天荒地老也制作不了 m 束花，我們可以直接返回 -1 。

如果花夠了，這里怎么來查找最小時(shí)間呢？這里我們可以通過二分法查找，二分查找的最小值和最大值分別是數(shù)組中元素的最小值和最大值。每次取中間的值，檢查能不能制作 m 束花。

比如區(qū)間是[10,100]，我們可以先判斷55能不能滿足條件，如果不能，則區(qū)間范圍變成[56,100]，如果能滿足條件，則區(qū)間范圍變成[10,55]，注意這里的55不能排除掉，通過二分法查找，最后區(qū)間長(zhǎng)度為 1 的時(shí)候，這個(gè)區(qū)間的值就是我們要求的結(jié)果。

JAVA：

public int minDays(int[] bloomDay, int m, int k) {     int n = bloomDay.length;     if (n < 1L * m * k)// 防止溢出，轉(zhuǎn)為long類型         return -1;     // 找出數(shù)組中的最大值和最小值。     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;// 花束的數(shù)量     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 朵花制作一個(gè)花束。                 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)// 防止溢出，轉(zhuǎn)為long類型             return-1;         // 找出數(shù)組中的最大值和最小值。         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;// 花束的數(shù)量         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 朵花制作一個(gè)花束。                     flowers = 0;                 }             } else {// 第 i 朵還沒有盛開。                 flowers = 0;             }         }         return cnt >= m;     }

筆者簡(jiǎn)介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。