1.设计停车系统
做法：
按照题意模拟。
代码：
class ParkingSystem {
public:
ParkingSystem(int big, int medium, int small) {
this->big = big;
this->medium = medium;
this->small = small;
}
bool addCar(int carType) {
if(carType == 1){
if(this->big > 0){
this->big--;
return true;
}
}
else if(carType == 2){
if(this->medium > 0){
this->medium--;
return true;
}
}
else if(carType == 3){
if(this->small > 0){
this->small--;
return true;
}
}
return false;
}
private:
int big, medium, small;
};
2. 警告一小时内使用相同员工卡大于等于三次的人
做法：
统计每个人的“打卡时间”，没有跨天的情况。对时间排个序，就能快速的判断是否是否有3个“打卡时间”小于1个小时。
class Solution {
public:
map<string, vector<string>>mp;
vector<string>ans;
vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
int num = keyName.size();
mp.clear();
ans.clear();
for(int i = 0; i < num; i++){
string name = keyName[i];
string time = keyTime[i];
mp[name].push_back(time);
}
for(map<string, vector<string>>::iterator it = mp.begin();it!=mp.end();it++){
vector<string>tmp = it->second;
string name = it->first;
sort(tmp.begin(), tmp.end());
for(int i = 2; i < tmp.size(); i++){
int t1 = fun(tmp[i]), t2 = fun(tmp[i-2]);
if(t1-t2<=60){
ans.push_back(name);
break;
}
}
}
sort(ans.begin(), ans.end());
return ans;
}
int fun(string time){
int hour = (time[0]-'0')*10+(time[1]-'0');
int mins = (time[3] - '0')*10+(time[4]-'0');
return hour*60+mins;
}
};
3.给定行和列的和求可行矩阵
做法：
对一个矩形的左上角的点a(0,0)=min(row[0], col[0])，如果取到了的是行，那那一行其他格子可以是0。如果取到的是列，那那一列其他格子可以是0。基于这样的操作，每次可以将一个矩形的第一行，或者第一列去掉，变成一个子问题。
代码
class Solution {
public:
vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
int n = rowSum.size(), m = colSum.size();
vector<vector<int>> ans(n, vector<int>(m,-1));
for(int i = 0;i<n;i++){
for(int j=0;j<m;j++){
if(ans[i][j]==-1){
if(rowSum[i]<colSum[j]){
ans[i][j]=rowSum[i];
for(int k=j+1;k<m;k++){
if(ans[i][k]==-1){
ans[i][k]=0;
}
}
colSum[j]-=rowSum[i];
rowSum[i] = 0;
}
else{
ans[i][j]=colSum[j];
for(int k=i+1;k<n;k++){
ans[k][j]=0;
}
rowSum[i] -= colSum[j];
colSum[j]=0;
}
}
}
}
return ans;
}
};
4.找到处理最多请求的服务器
做法
其实就是按照题意来做，为了效率，需要用一个数据结构支持以下操作： 1.对于x，找到大于等于x的数。 2.对于x，找到所有小于等于x的数。 这里选择C++中的set来做这个数据结构。 可用服务器的选择过程相当于操作1。运行服务器变成可用服务器的过程相当于操作2。
代码
class Solution {
public:
set<pair<int,int>> endtime;
set<int> now;
int count[100005];
vector<int>ans;
vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
endtime.clear();
now.clear();
ans.clear();
for(int i=0;i<k;i++){
now.insert(i);
count[i]=0;
}
int n=arrival.size();
for(int i=0;i<n;i++){
int time_now=arrival[i];
while(1){
if(endtime.empty()) break;
set<pair<int,int>>::iterator it = endtime.begin();
pair<int,int> tmp = *it;
if(time_now>=tmp.first){
endtime.erase(it);
now.insert(tmp.second);
}
else{
break;
}
}
if(now.empty()) continue;
set<int>::iterator it = now.lower_bound(i%k);
if(it == now.end()){
it = now.begin();
}
int tmp = *it;
now.erase(it);
count[tmp]++;
endtime.insert(make_pair(time_now+load[i],tmp));
}
int maxx=0;
for(int i=0;i<k;i++){
maxx=max(maxx,count[i]);
}
for(int i=0;i<k;i++){
if(count[i]==maxx){
ans.push_back(i);
}
}
return ans;
}
};
