leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0355.cpp (1382B)

0 class Twitter { 1 vector<pair<int, int>> posts[501]; 2 bool following[501][501] = {0}; 3 int time = 0; 4 5 public: 6 Twitter() { 7 for (int i = 0; i <= 500; i++) { 8 following[i][i] = true; 9 } 10 } 11 12 void postTweet(int userId, int tweetId) { posts[userId].emplace_back(time++, tweetId); } 13 14 vector<int> getNewsFeed(int userId) { 15 using type_t = tuple<int, int, int>; 16 static const auto cmp = [](const type_t &a, const type_t &b) { return get<0>(a) < get<0>(b); }; 17 priority_queue<type_t, vector<type_t>, decltype(cmp)> pq(cmp); 18 19 for (int i = 0; i <= 500; i++) { 20 if (!following[userId][i]) continue; 21 22 const int n = size(posts[i]); 23 if (n == 0) continue; 24 25 pq.emplace(posts[i][n - 1].first, i, n - 1); 26 if (size(pq) > 10) pq.pop(); 27 } 28 29 vector<int> res; 30 while (!pq.empty() && size(res) < 10) { 31 const auto [time, user, idx] = pq.top(); 32 pq.pop(); 33 res.push_back(posts[user][idx].second); 34 if (idx - 1 >= 0) pq.emplace(posts[user][idx - 1].first, user, idx - 1); 35 } 36 37 return res; 38 } 39 40 void follow(int followerId, int followeeId) { following[followerId][followeeId] = true; } 41 42 void unfollow(int followerId, int followeeId) { following[followerId][followeeId] = false; } 43 };