全国排名: 304 / 2204,13.8%;全球排名: 1143 / 8332,13.7%
请你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位:大,中和小,每种尺寸分别有固定数目的车位。
请你实现 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;
}
};
力扣公司的员工都使用员工卡来开办公室的门。每当一个员工使用一次他的员工卡,安保系统会记录下员工的名字和使用时间。如果一个员工在一小时时间内使用员工卡的次数大于等于三次,这个系统会自动发布一个 警告 。
给你字符串数组 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
给你两个非负整数数组 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
你有 k 个服务器,编号为 0 到 k-1 ,它们可以同时处理多个请求组。 每个服务器有无穷的计算能力但是 不能同时处理超过一个请求 。请求分配到服务器的规则如下:
i
(序号从 0 开始)个请求到达。(i % k)
个服务器空闲,那么对应服务器会处理该请求。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 保证 严格递增 。
解题:
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