LeetCode周赛182

作者 Lucyyang 日期 2020-03-29
LeetCode周赛182

今天的比赛打的还不错哦,虽然第三题在整除问题上WA了一发,但整体过程还是蛮顺利的!希望下次比赛也能顺顺利利做完第三题!

Find Lucky Integer in an Array

题目:LC1294,找到出现次数和值相同的数。

方法:用了一个map统计出现次数,然后从最大值开始遍历,返回第一个相等的值。

代码:

class Solution {
public:
map<int, int> m;
int findLucky(vector<int>& arr) {
for(auto a:arr){
m[a]++;
}
int ans = -1;
for(int i = 500; i>=0; i--){
if(m.find(i)!=m.end()){
if(m[i] == i) {
ans = i;
break;
}
}
}
return ans;
}
};

Count Number of Teams

题目:LC1395,找到数组中递增或递减的三个数。

方法:比赛的时候直接写的O(N3)做法,幸好给的数据范围小过了。O(N2)的做法是对从nums[1:size-2]的数统计larger[left],larger[right],smaller[left]和smaller[right],对于单个数可以组成的个数为larger[left]*smaller[right]+larger[right]*smaller[left]。

代码:

int numTeams(vector<int>& rating) {
int res = 0;
for (auto i = 1; i < rating.size() - 1; ++i) {
int less[2] = {}, greater[2] = {};
for (auto j = 0; j < rating.size(); ++j) {
if (rating[i] < rating[j])
++less[j > i];
if (rating[i] > rating[j])
++greater[j > i];
}
res += less[0] * greater[1] + greater[0] * less[1];
}
return res;
}

Design Underground System

题目:LC1396,一道设计题。题目大意是记录下游客从station1出发到station2的时间,最后会求出所有旅客从station1到station2所用平均时间。

方法:我用了一个map1来求从station1到station2的总共时间,一个map2用来记录从station1到station2的人数;当有新的旅客checkin时,用一个hash table记录下id,checkin信息,当checkout的时候,计算出相关信息加入到map1和map2中,再删去checkin中的信息。比赛中WA了一次,因为最后返回time时用的int/int,结果自动取整了,后面加了个double。

代码:

class UndergroundSystem {
private:
map<pair<string, string>, long long> averTime;
map<pair<string, string>, int> totalInt;
unordered_map<int, pair<string, int>> checkin;
public:
UndergroundSystem() {
}
void checkIn(int id, string stationName, int t) {
checkin[id] = {stationName, t};
}
void checkOut(int id, string stationName, int t) {
auto checkin_status = checkin[id];
int checkintime = checkin_status.second;
string stationStart = checkin_status.first;
checkin.erase(id);
auto stationstr = make_pair(stationStart, stationName);
averTime[stationstr]+=(t - checkintime);
totalInt[stationstr]++;
}
double getAverageTime(string startStation, string endStation) {
auto stationstr = make_pair(startStation, endStation);
double time = (double)averTime[stationstr]/totalInt[stationstr];
return time;
}
};
/**
* Your UndergroundSystem object will be instantiated and called as such:
* UndergroundSystem* obj = new UndergroundSystem();
* obj->checkIn(id,stationName,t);
* obj->checkOut(id,stationName,t);
* double param_3 = obj->getAverageTime(startStation,endStation);
*/

这次比赛题目还是比较简单的,再接再厉!