文章目錄

• • 1. 比賽結(jié)果
  • 2. 題目
  • • 1. LeetCode 5515. 設(shè)計(jì)停車系統(tǒng) easy
    • 2. LeetCode 5516. 警告一小時(shí)內(nèi)使用相同員工卡大于等于三次的人 medium
    • 3. LeetCode 5518. 給定行和列的和求可行矩陣 medium
    • 4. LeetCode 5517. 找到處理最多請(qǐng)求的服務(wù)器 hard

1. 比賽結(jié)果

做出來3題，但速度不夠快，第四題不會(huì)。繼續(xù)加油！

全國(guó)排名： 304 / 2204，13.8%；全球排名： 1143 / 8332，13.7%

2. 題目

1. LeetCode 5515. 設(shè)計(jì)停車系統(tǒng) easy

題目鏈接

請(qǐng)你給一個(gè)停車場(chǎng)設(shè)計(jì)一個(gè)停車系統(tǒng)。停車場(chǎng)總共有三種不同大小的車位：大，中和小，每種尺寸分別有固定數(shù)目的車位。

請(qǐng)你實(shí)現(xiàn) ParkingSystem 類：

• ParkingSystem(int big, int medium, int small) 初始化 ParkingSystem 類，三個(gè)參數(shù)分別對(duì)應(yīng)每種停車位的數(shù)目。
• bool addCar(int carType) 檢車是否有 carType 對(duì)應(yīng)的停車位。
  carType 有三種類型：大，中，小，分別用數(shù)字 1， 2 和 3 表示。
  一輛車只能停在 carType 對(duì)應(yīng)尺寸的停車位中。
  如果沒有空車位，請(qǐng)返回 false ，否則將該車停入車位并返回 true 。

示例 1： 輸入： ["ParkingSystem", "addCar", "addCar", "addCar", "addCar"] [[1, 1, 0], [1], [2], [3], [1]] 輸出： [null, true, true, false, false]解釋： ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0); parkingSystem.addCar(1); // 返回 true ，因?yàn)橛?1 個(gè)空的大車位 parkingSystem.addCar(2); // 返回 true ，因?yàn)橛?1 個(gè)空的中車位 parkingSystem.addCar(3); // 返回 false ，因?yàn)闆]有空的小車位 parkingSystem.addCar(1); // 返回 false ，因?yàn)闆]有空的大車位，唯一一個(gè)大車位已經(jīng)被占據(jù)了 提示： 0 <= big, medium, small <= 1000 carType 取值為 1， 2 或 3 最多會(huì)調(diào)用 addCar 函數(shù) 1000 次

---

解題：

class ParkingSystem {int a, b, c; public:ParkingSystem(int big, int medium, int small) {a = big, b = medium, c = small;}bool addCar(int carType) {if(carType == 1 && a > 0){a--;return true;}else if(carType == 2 && b > 0){b--;return true;}else if(carType == 3 && c > 0){c--;return true;}return false;} };

2. LeetCode 5516. 警告一小時(shí)內(nèi)使用相同員工卡大于等于三次的人 medium

題目鏈接

力扣公司的員工都使用員工卡來開辦公室的門。每當(dāng)一個(gè)員工使用一次他的員工卡，安保系統(tǒng)會(huì)記錄下員工的名字和使用時(shí)間。如果一個(gè)員工在一小時(shí)時(shí)間內(nèi)使用員工卡的次數(shù)大于等于三次，這個(gè)系統(tǒng)會(huì)自動(dòng)發(fā)布一個(gè) 警告 。

給你字符串?dāng)?shù)組 keyName 和 keyTime ，期中 [keyName[i], keyTime[i]] 對(duì)應(yīng)一個(gè)人的名字和他在 某一天 內(nèi)使用員工卡的時(shí)間。

使用時(shí)間的格式是 24小時(shí)制 ，形如 "HH:MM" ，比方說 "23:51" 和 "09:49" 。

請(qǐng)你返回去重后的收到系統(tǒng)警告的員工名字，將它們按 字典序升序 排序后返回。

請(qǐng)注意 "10:00" - "11:00" 視為一個(gè)小時(shí)時(shí)間范圍內(nèi)，而 "23:51" - "00:10" 不被視為一小時(shí)內(nèi)，因?yàn)橄到y(tǒng)記錄的是某一天內(nèi)的使用情況。

示例 1： 輸入：keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"] 輸出：["daniel"] 解釋："daniel" 在一小時(shí)內(nèi)使用了 3 次員工卡（"10:00"，"10:40"，"11:00"）。示例 2： 輸入：keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"] 輸出：["bob"] 解釋："bob" 在一小時(shí)內(nèi)使用了 3 次員工卡（"21:00"，"21:20"，"21:30"）。示例 3： 輸入：keyName = ["john","john","john"], keyTime = ["23:58","23:59","00:01"] 輸出：[]示例 4： 輸入：keyName = ["leslie","leslie","leslie","clare","clare","clare","clare"], keyTime = ["13:00","13:20","14:00","18:00","18:51","19:30","19:49"] 輸出：["clare","leslie"]提示： 1 <= keyName.length, keyTime.length <= 105 keyName.length == keyTime.length keyTime 格式為 "HH:MM" 。 保證 [keyName[i], keyTime[i]] 形成的二元對(duì) 互不相同 。 1 <= keyName[i].length <= 10 keyName[i] 只包含小寫英文字母。

---

解題：

class Solution { public:vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {map<string, set<string>> m;// name , set<time> for(int i = 0; i < keyName.size(); i++) {m[keyName[i]].insert(keyTime[i]);}vector<string> ans;string name, time;for(auto it = m.begin(); it != m.end(); ++it){name = it->first;if(it->second.size() < 3)continue;auto it1 = it->second.begin();time = *it1;//時(shí)間轉(zhuǎn)成分鐘int prev = ((time[0]-'0')*10+time[1]-'0')*60+(time[3]-'0')*10+time[4]-'0';it1++, time = *it1;int mid = ((time[0]-'0')*10+time[1]-'0')*60+(time[3]-'0')*10+time[4]-'0';it1++;for( ; it1 != it->second.end(); it1++){time = *it1;int cur = ((time[0]-'0')*10+time[1]-'0')*60+(time[3]-'0')*10+time[4]-'0';if(cur-prev <= 60)// prev, mid, cur{ans.push_back(name);break;}prev = mid;mid = cur;}}return ans;} };

844 ms 116 MB

3. LeetCode 5518. 給定行和列的和求可行矩陣 medium

題目鏈接

給你兩個(gè)非負(fù)整數(shù)數(shù)組 rowSum 和 colSum ，其中 rowSum[i] 是二維矩陣中第 i 行元素的和， colSum[j] 是第 j 列元素的和。換言之你不知道矩陣?yán)锏拿總€(gè)元素，但是你知道每一行和每一列的和。

請(qǐng)找到大小為 rowSum.length x colSum.length 的任意 非負(fù)整數(shù) 矩陣，且該矩陣滿足 rowSum 和 colSum 的要求。

請(qǐng)你返回任意一個(gè)滿足題目要求的二維矩陣，題目保證存在 至少一個(gè) 可行矩陣。

示例 1： 輸入：rowSum = [3,8], colSum = [4,7] 輸出：[[3,0],[1,7]] 解釋： 第 0 行：3 + 0 = 0 == rowSum[0] 第 1 行：1 + 7 = 8 == rowSum[1] 第 0 列：3 + 1 = 4 == colSum[0] 第 1 列：0 + 7 = 7 == colSum[1] 行和列的和都滿足題目要求，且所有矩陣元素都是非負(fù)的。 另一個(gè)可行的矩陣為：[[1,2],[3,5]]示例 2： 輸入：rowSum = [5,7,10], colSum = [8,6,8] 輸出：[[0,5,0],[6,1,0],[2,0,8]]示例 3： 輸入：rowSum = [14,9], colSum = [6,9,8] 輸出：[[0,9,5],[6,0,3]]示例 4： 輸入：rowSum = [1,0], colSum = [1] 輸出：[[1],[0]]示例 5： 輸入：rowSum = [0], colSum = [0] 輸出：[[0]]提示： 1 <= rowSum.length, colSum.length <= 500 0 <= rowSum[i], colSum[i] <= 108 sum(rows) == sum(columns)

---

解題：

class Solution { public:vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {int m = rowSum.size(), n = colSum.size();vector<vector<int>> ans(m, vector<int>(n, 0));for(int i = 0; i < m; ++i) {for(int j = 0; j < n; ++j){if(rowSum[i] == 0)break;ans[i][j] = min(rowSum[i], colSum[j]);rowSum[i] -= ans[i][j];colSum[j] -= ans[i][j];}}return ans;} };

112 ms 32.7 MB

4. LeetCode 5517. 找到處理最多請(qǐng)求的服務(wù)器 hard

題目鏈接

你有 k 個(gè)服務(wù)器，編號(hào)為 0 到 k-1 ，它們可以同時(shí)處理多個(gè)請(qǐng)求組。
每個(gè)服務(wù)器有無窮的計(jì)算能力但是 不能同時(shí)處理超過一個(gè)請(qǐng)求 。請(qǐng)求分配到服務(wù)器的規(guī)則如下：

• 第 i （序號(hào)從 0 開始）個(gè)請(qǐng)求到達(dá)。
• 如果所有服務(wù)器都已被占據(jù)，那么該請(qǐng)求被舍棄（完全不處理）。
• 如果第 (i % k) 個(gè)服務(wù)器空閑，那么對(duì)應(yīng)服務(wù)器會(huì)處理該請(qǐng)求。
• 否則，將請(qǐng)求安排給下一個(gè)空閑的服務(wù)器（服務(wù)器構(gòu)成一個(gè)環(huán)，必要的話可能從第 0 個(gè)服務(wù)器開始繼續(xù)找下一個(gè)空閑的服務(wù)器）。比方說，如果第 i 個(gè)服務(wù)器在忙，那么會(huì)查看第 (i+1) 個(gè)服務(wù)器，第 (i+2) 個(gè)服務(wù)器等等。

給你一個(gè) 嚴(yán)格遞增 的正整數(shù)數(shù)組 arrival ，表示第 i 個(gè)任務(wù)的到達(dá)時(shí)間，和另一個(gè)數(shù)組 load ，其中 load[i] 表示第 i 個(gè)請(qǐng)求的工作量（也就是服務(wù)器完成它所需要的時(shí)間）。

你的任務(wù)是找到 最繁忙的服務(wù)器 。最繁忙定義為一個(gè)服務(wù)器處理的請(qǐng)求數(shù)是所有服務(wù)器里最多的。

請(qǐng)你返回包含所有 最繁忙服務(wù)器 序號(hào)的列表，你可以以任意順序返回這個(gè)列表。

示例 1：

輸入：k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3] 輸出：[1] 解釋： 所有服務(wù)器一開始都是空閑的。 前 3 個(gè)請(qǐng)求分別由前 3 臺(tái)服務(wù)器依次處理。 請(qǐng)求 3 進(jìn)來的時(shí)候，服務(wù)器 0 被占據(jù)，所以它唄安排到下一臺(tái)空閑的服務(wù)器，也就是服務(wù)器 1 。 請(qǐng)求 4 進(jìn)來的時(shí)候，由于所有服務(wù)器都被占據(jù)，該請(qǐng)求被舍棄。 服務(wù)器 0 和 2 分別都處理了一個(gè)請(qǐng)求，服務(wù)器 1 處理了兩個(gè)請(qǐng)求。 所以服務(wù)器 1 是最忙的服務(wù)器。示例 2： 輸入：k = 3, arrival = [1,2,3,4], load = [1,2,1,2] 輸出：[0] 解釋： 前 3 個(gè)請(qǐng)求分別被前 3 個(gè)服務(wù)器處理。 請(qǐng)求 3 進(jìn)來，由于服務(wù)器 0 空閑，它被服務(wù)器 0 處理。 服務(wù)器 0 處理了兩個(gè)請(qǐng)求，服務(wù)器 1 和 2 分別處理了一個(gè)請(qǐng)求。所以服務(wù)器 0 是最忙的服務(wù)器。示例 3： 輸入：k = 3, arrival = [1,2,3], load = [10,12,11] 輸出：[0,1,2] 解釋：每個(gè)服務(wù)器分別處理了一個(gè)請(qǐng)求，所以它們都是最忙的服務(wù)器。示例 4： 輸入：k = 3, arrival = [1,2,3,4,8,9,10], load = [5,2,10,3,1,2,2] 輸出：[1]示例 5： 輸入：k = 1, arrival = [1], load = [1] 輸出：[0]提示： 1 <= k <= 105 1 <= arrival.length, load.length <= 105 arrival.length == load.length 1 <= arrival[i], load[i] <= 109 arrival 保證 嚴(yán)格遞增 。

---

解題：

• 參考 mike-meng 題解

typedef pair<int, int> pii;struct cmp{bool operator()(pii& a, pii& b) const{return a.first > b.first;//小的結(jié)束時(shí)間（結(jié)束時(shí)間早）優(yōu)先} }; class Solution { public:vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {vector<int> count(k, 0);priority_queue<pii,vector<pii>,cmp> q;set<int> s;//可用機(jī)器編號(hào)for(int i = 0; i < k; i++) s.insert(i);//機(jī)器編號(hào)int id=0, maxload = 0;for(int i = 0; i < arrival.size(); i++){while(!q.empty() && q.top().first <= arrival[i]){ //機(jī)器結(jié)束工作時(shí)間 <= 任務(wù)到達(dá)時(shí)間s.insert(q.top().second);q.pop();} auto it = s.lower_bound(i%k);if(it != s.end())//序號(hào)大于等于 i 的空閑機(jī)器存在{id = *it;count[id]++;q.push({arrival[i]+load[i], id});//結(jié)束時(shí)間，機(jī)器編號(hào)s.erase(it);//這個(gè)機(jī)器不可用了，放入隊(duì)列了}else if(it != s.begin()){id = *s.begin();count[id]++;q.push({arrival[i]+load[i], id});s.erase(s.begin());}maxload = max(maxload, count[id]);}vector<int> ans;for(int i = 0; i < k; i++)if(count[i] == maxload)ans.push_back(i);return ans;} };

1240 ms 115.8 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 第 36 场双周赛（304/2204，前13.8%）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。