6. 475.供暖器(中等，學習check函數雙指針思想)
475. 供暖器 - 力扣（LeetCode）
思想
1.冬季已經來臨。 你的任務是設計一個有固定加熱半徑的供暖器向所有房屋供暖。在加熱器的加熱半徑范圍內的每個房屋都可以獲得供暖。現在，給出位于一條水平線上的房屋 houses 和供暖器 heaters 的位置，請你找出并返回可以覆蓋所有房屋的最小加熱半徑。
2.單調性檢驗:加熱半徑越小，越可能不能覆蓋所有房屋，不滿足條件，所以存在一個最小加熱半徑
3.難點在于check函數怎么寫，我原來的思想是遍歷heaters,然后把[heaters[i]-x,heaters[i]+x]變為true，但這樣會超出內存限制
4.學習:
(1)先將houses和heaters進行排序(最重要)
(2)讓i指向當前判斷房屋houses[i],然后j指向可能(先確保右邊界成立) 覆蓋到的heaters[j],x為加熱半徑
- 當且僅當
heaters[j]+x<houses[i]時，第i個房屋必定不能被第j個加熱器覆蓋，然j自增 - 退出循環說明找到合適的j(右邊界必然成立,找到能覆蓋的最小加熱器)，再判斷
heaters[j]-x<=houses[i]<=heaters[j]+x是否滿足
代碼
c++:
class Solution {
public:bool check(vector<int>& houses, vector<int>& heaters, int mid) {int n = houses.size(), m = heaters.size();int j = 0;for (int i = 0; i < n; ++i) {while (j < m && houses[i] > heaters[j] + mid)++j; // 尋找能覆蓋的最小加熱器if (j < m && heaters[j] - mid <= houses[i] &&houses[i] <= heaters[j] + mid)continue; // 滿足條件看下一個房子return false; // 不滿足條件}return true;}int findRadius(vector<int>& houses, vector<int>& heaters) {int res = 0;sort(houses.begin(), houses.end());sort(heaters.begin(), heaters.end());int maxho = INT_MIN, minho = INT_MAX, maxhe = INT_MIN, minhe = INT_MAX;for (const int x : houses) {maxho = max(maxho, x);minho = min(minho, x);}for (const int x : heaters) {maxhe = max(maxhe, x);minhe = min(minhe, x);}int left = 0, right = max(abs(maxho - minhe), abs(maxhe - minho));while (left <= right) {int mid = left + ((right - left) >> 1);if (check(houses, heaters, mid)) {res = mid;right = mid - 1;} elseleft = mid + 1;}return res;}
};
7. 2594.修車的最少時間(中等)
2594. 修車的最少時間 - 力扣（LeetCode）
思想
1.給你一個整數數組 ranks ，表示一些機械工的 能力值 。ranksi 是第 i 位機械工的能力值。能力值為 r 的機械工可以在 r * n2 分鐘內修好 n 輛車。同時給你一個整數 cars ，表示總共需要修理的汽車數目。請你返回**修理所有汽車(條件) ** 最少 需要多少時間(答案)。
2.類似于3296.移山所需的最少秒數
3.單調性檢驗，時間越少，越不可能修理所有汽車，所以存在一個最少時間
代碼
c++:
class Solution {
public:bool check(vector<int>& ranks, int cars, long long mid) {long long sum = 0;for (const int x : ranks) {sum += (long long)sqrt(mid / x);if (sum >= cars)return true;}return false;}long long repairCars(vector<int>& ranks, int cars) {long long res = 0;int minval = INT_MAX;for (const int x : ranks)minval = min(minval, x);long long left = 1, right = 1LL * minval * cars * cars;while (left <= right) {long long mid = left + ((right - left) >> 1);if (check(ranks, cars, mid)) {res = mid;right = mid - 1;} elseleft = mid + 1;}return res;}
};
1.不用轉換為long long的，可以寫成1LL
8. 1482.制作m束花所需的最少天數
1482. 制作 m 束花所需的最少天數 - 力扣（LeetCode）
思想
1.給你一個整數數組 bloomDay，以及兩個整數 m 和 k 。現需要制作 m 束花。制作花束時，需要使用花園中 相鄰的 k 朵花(小條件) 。花園中有 n 朵花，第 i 朵花會在 bloomDay[i] 時盛開，恰好可以用于 一束 花中。請你返回從花園中摘 m 束花(條件) 需要等待的最少的天數(答案)。如果不能摘到 m 束花則返回 -1 。
2.單調性檢驗:天數越少，越不能摘到m束花，所以存在一個最少天數
代碼
c++:
class Solution {
public:bool check(vector<int>& bloomDay, int m, int k, int mid) {int n = bloomDay.size();int sum = 0, cnt = 0;for (int i = 0; i < n; ++i) {if (bloomDay[i] <= mid) {++cnt;if (cnt == k) {++sum;if (sum >= m)return true;cnt = 0;}} else {cnt = 0;}}return false;}int minDays(vector<int>& bloomDay, int m, int k) {int res = -1;int maxval = INT_MIN;for (const int x : bloomDay)maxval = max(maxval, x);int left = 1, right = maxval;while (left <= right) {int mid = left + ((right - left) >> 1);if (check(bloomDay, m, k, mid)) {res = mid;right = mid - 1;} elseleft = mid + 1;}return res;}
};
)
)
