文章目錄
- 1. 比賽結果
- 2. 題目
- 1. LeetCode 5515. 設計停車系統 easy
- 2. LeetCode 5516. 警告一小時內使用相同員工卡大于等于三次的人 medium
- 3. LeetCode 5518. 給定行和列的和求可行矩陣 medium
- 4. LeetCode 5517. 找到處理最多請求的服務器 hard
1. 比賽結果
做出來3題，但速度不夠快，第四題不會，繼續加油！
全國排名： 304 / 2204，13.8%；全球排名： 1143 / 8332，13.7%
2. 題目
1. LeetCode 5515. 設計停車系統 easy
題目鏈接
請你給一個停車場設計一個停車系統，停車場總共有三種不同大小的車位：大，中和小，每種尺寸分別有固定數目的車位，
請你實作 ParkingSystem 類：
ParkingSystem(int big, int medium, int small)初始化 ParkingSystem 類，三個引數分別對應每種停車位的數目，bool addCar(int carType)檢車是否有 carType 對應的停車位，
carType 有三種型別：大，中，小，分別用數字 1， 2 和 3 表示，
一輛車只能停在 carType 對應尺寸的停車位中，
如果沒有空車位，請回傳 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 ，因為有 1 個空的大車位
parkingSystem.addCar(2); // 回傳 true ，因為有 1 個空的中車位
parkingSystem.addCar(3); // 回傳 false ，因為沒有空的小車位
parkingSystem.addCar(1); // 回傳 false ，因為沒有空的大車位，唯一一個大車位已經被占據了
提示：
0 <= big, medium, small <= 1000
carType 取值為 1， 2 或 3
最多會呼叫 addCar 函式 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. 警告一小時內使用相同員工卡大于等于三次的人 medium
題目鏈接
力扣公司的員工都使用員工卡來開辦公室的門，每當一個員工使用一次他的員工卡，安保系統會記錄下員工的名字和使用時間，如果一個員工在一小時時間內使用員工卡的次數大于等于三次，這個系統會自動發布一個 警告 ，
給你字串陣列 keyName 和 keyTime ，期中 [keyName[i], keyTime[i]] 對應一個人的名字和他在 某一天 內使用員工卡的時間，
使用時間的格式是 24小時制 ，形如 "HH:MM" ，比方說 "23:51" 和 "09:49" ，
請你回傳去重后的收到系統警告的員工名字，將它們按 字典序升序 排序后回傳，
請注意 "10:00" - "11:00" 視為一個小時時間范圍內，而 "23:51" - "00:10" 不被視為一小時內，因為系統記錄的是某一天內的使用情況，
示例 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" 在一小時內使用了 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" 在一小時內使用了 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]] 形成的二元對 互不相同 ，
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;
//時間轉成分鐘
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
題目鏈接
給你兩個非負整數陣列 rowSum 和 colSum ，其中 rowSum[i] 是二維矩陣中第 i 行元素的和， colSum[j] 是第 j 列元素的和，換言之你不知道矩陣里的每個元素，但是你知道每一行和每一列的和，
請找到大小為 rowSum.length x colSum.length 的任意 非負整數 矩陣，且該矩陣滿足 rowSum 和 colSum 的要求，
請你回傳任意一個滿足題目要求的二維矩陣，題目保證存在 至少一個 可行矩陣，
示例 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]
行和列的和都滿足題目要求，且所有矩陣元素都是非負的，
另一個可行的矩陣為：[[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. 找到處理最多請求的服務器 hard
題目鏈接
你有 k 個服務器，編號為 0 到 k-1 ，它們可以同時處理多個請求組，
每個服務器有無窮的計算能力但是 不能同時處理超過一個請求 ，請求分配到服務器的規則如下：
- 第
i（序號從 0 開始）個請求到達， - 如果所有服務器都已被占據，那么該請求被舍棄（完全不處理），
- 如果第
(i % k)個服務器空閑，那么對應服務器會處理該請求， - 否則，將請求安排給下一個空閑的服務器（服務器構成一個環，必要的話可能從第 0 個服務器開始繼續找下一個空閑的服務器），比方說，如果第
i個服務器在忙，那么會查看第(i+1)個服務器，第(i+2)個服務器等等，
給你一個 嚴格遞增 的正整數陣列 arrival ，表示第 i 個任務的到達時間，和另一個陣列 load ，其中 load[i] 表示第 i 個請求的作業量（也就是服務器完成它所需要的時間），
你的任務是找到 最繁忙的服務器 ，最繁忙定義為一個服務器處理的請求數是所有服務器里最多的，
請你回傳包含所有 最繁忙服務器 序號的串列，你可以以任意順序回傳這個串列，
示例 1：
輸入：k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3]
輸出：[1]
解釋：
所有服務器一開始都是空閑的，
前 3 個請求分別由前 3 臺服務器依次處理，
請求 3 進來的時候，服務器 0 被占據，
所以它唄安排到下一臺空閑的服務器，也就是服務器 1 ，
請求 4 進來的時候，由于所有服務器都被占據，該請求被舍棄，
服務器 0 和 2 分別都處理了一個請求，服務器 1 處理了兩個請求，
所以服務器 1 是最忙的服務器，
示例 2：
輸入：k = 3, arrival = [1,2,3,4], load = [1,2,1,2]
輸出：[0]
解釋：
前 3 個請求分別被前 3 個服務器處理，
請求 3 進來，由于服務器 0 空閑，它被服務器 0 處理，
服務器 0 處理了兩個請求，服務器 1 和 2 分別處理了一個請求，
所以服務器 0 是最忙的服務器，
示例 3：
輸入：k = 3, arrival = [1,2,3], load = [10,12,11]
輸出：[0,1,2]
解釋：每個服務器分別處理了一個請求，所以它們都是最忙的服務器，
示例 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 保證 嚴格遞增 ，
解題：
- 參考 mike-meng 題解
typedef pair<int, int> pii;
struct cmp{
bool operator()(pii& a, pii& b) const
{
return a.first > b.first;//小的結束時間（結束時間早）優先
}
};
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;//可用機器編號
for(int i = 0; i < k; i++)
s.insert(i);//機器編號
int id=0, maxload = 0;
for(int i = 0; i < arrival.size(); i++)
{
while(!q.empty() && q.top().first <= arrival[i])
{ //機器結束作業時間 <= 任務到達時間
s.insert(q.top().second);
q.pop();
}
auto it = s.lower_bound(i%k);
if(it != s.end())//序號大于等于 i 的空閑機器存在
{
id = *it;
count[id]++;
q.push({arrival[i]+load[i], id});//結束時間，機器編號
s.erase(it);//這個機器不可用了，放入佇列了
}
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/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/157423.html
標籤：其他
上一篇：ensp的ospf小實驗
下一篇：【題解】加分二叉樹