Leetcode Weekly Contest 428

[oin1104 (是oin的說)]

第一題
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
```


--

我是小黃瓜
https://i.imgur.com/1YMQtyf.jpeg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.27.220 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1734237277.A.84D.html
噓 sustainer123: 怎麼才兩題
推 Furina: 我好崇拜你
→ oin1104: 第三題很難欸 rolling hash
噓 mrsonic: 怪人
→ sixB: 你好棒 我今天有醒可是很不想打