第一題
rp跟實驗室姆咪生了一群小母貓
跟一個有idx跟time的陣列
代表那隻小母貓什麼時後被rp小母貓餵奶
回傳idx最小而且被餵時間間隔最長的小母貓
思路
用map記錄小母貓的被餵時間
```cpp
class Solution {
public:
int buttonWithLongestTime(vector<vector<int>>& events)
{
int now = 0;
unordered_map<int,int> sheep;
int n = events.size();
int res = 0;
int resi = 1000000;
for(int i = 0 ; i < n ; i ++)
{
int pass = events[i][1] - now;
sheep[events[i][0]] = pass;
if(pass > res )
{
resi = events[i][0];
res = pass;
}
else if(pass == res && events[i][0] < resi)
{
resi = events[i][0];
res = pass;
}
now = events[i][1];
}
return resi;
}
};c leetcode
```
第二題
換錢
每天匯率不一樣
要換最多的
而且要跟一開始的幣種一樣
思路
記錄path然後bfs窮舉每一種可能
```cpp
class Solution {
public:
double maxAmount(string initialCurrency, vector<vector<string>>& pairs1, vec
tor<double>& rates1, vector<vector<string>>& pairs2, vector<double>& rates2)
{
//from end money
unordered_map<string,vector<pair<string,double>>> path1;
unordered_map<string,vector<pair<string,double>>> path2;
int n1 = pairs1.size();
int n2 = pairs2.size();
for(int i = 0 ; i < n1 ; i ++)
{
path1[pairs1[i][0]].push_back({pairs1[i][1] , rates1[i]});
path1[pairs1[i][1]].push_back({pairs1[i][0] , 1/rates1[i]});
}
for(int i = 0 ; i < n2 ; i ++)
{
path2[pairs2[i][0]].push_back({pairs2[i][1] , rates2[i]});
path2[pairs2[i][1]].push_back({pairs2[i][0] , 1/rates2[i]});
}
queue<pair<string,double>> q;
unordered_map<string,double> save1;
unordered_map<string,double> save2;
q.push({initialCurrency,1});
while(!q.empty())
{
auto k = q.front();
q.pop();
if(save1[k.first] >= k.second) continue;
save1[k.first] = max(save1[k.first],k.second);
for(auto l : path1[k.first])
{
q.push({l.first , k.second*l.second});
}
}
for(auto k : save1)
{
q.push(k);
// cout << k.first << " " << k.second << endl;
}
while(!q.empty())
{
auto k = q.front();
q.pop();
if(save2[k.first] >= k.second) continue;
save2[k.first] = max(save2[k.first],k.second);
for(auto l : path2[k.first])
{
q.push({l.first , k.second*l.second});
}
}
double res = save2[initialCurrency];
return res;
}
};c leetcode
```