commit 0c4be2dd7e1849bf5f09add4e4952f5619fe1521
parent b63855cf7ac47e69cc0454549065d2c5cbb4f430
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sat, 2 Nov 2024 15:09:50 +0100
1 Daily Problem, 2 Random
Diffstat:
4 files changed, 83 insertions(+), 0 deletions(-)
diff --git a/Problems/0354.cpp b/Problems/0354.cpp
@@ -0,0 +1,21 @@
+class Solution {
+ public:
+ int maxEnvelopes(vector<vector<int>> &envelopes) const {
+ const int n = size(envelopes);
+
+ sort(begin(envelopes), end(envelopes),
+ [](const auto &a, const auto &b) { return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1]; });
+
+ vector<int> res;
+ for (int i = 0; i < n; i++) {
+ const auto crnt = envelopes[i][1];
+ const auto it = lower_bound(begin(res), end(res), crnt);
+ if (it == end(res))
+ res.push_back(crnt);
+ else
+ *it = crnt;
+ }
+
+ return size(res);
+ }
+};
diff --git a/Problems/0355.cpp b/Problems/0355.cpp
@@ -0,0 +1,44 @@
+class Twitter {
+ vector<pair<int, int>> posts[501];
+ bool following[501][501] = {0};
+ int time = 0;
+
+ public:
+ Twitter() {
+ for (int i = 0; i <= 500; i++) {
+ following[i][i] = true;
+ }
+ }
+
+ void postTweet(int userId, int tweetId) { posts[userId].emplace_back(time++, tweetId); }
+
+ vector<int> getNewsFeed(int userId) {
+ using type_t = tuple<int, int, int>;
+ static const auto cmp = [](const type_t &a, const type_t &b) { return get<0>(a) < get<0>(b); };
+ priority_queue<type_t, vector<type_t>, decltype(cmp)> pq(cmp);
+
+ for (int i = 0; i <= 500; i++) {
+ if (!following[userId][i]) continue;
+
+ const int n = size(posts[i]);
+ if (n == 0) continue;
+
+ pq.emplace(posts[i][n - 1].first, i, n - 1);
+ if (size(pq) > 10) pq.pop();
+ }
+
+ vector<int> res;
+ while (!pq.empty() && size(res) < 10) {
+ const auto [time, user, idx] = pq.top();
+ pq.pop();
+ res.push_back(posts[user][idx].second);
+ if (idx - 1 >= 0) pq.emplace(posts[user][idx - 1].first, user, idx - 1);
+ }
+
+ return res;
+ }
+
+ void follow(int followerId, int followeeId) { following[followerId][followeeId] = true; }
+
+ void unfollow(int followerId, int followeeId) { following[followerId][followeeId] = false; }
+};
diff --git a/Problems/2490.cpp b/Problems/2490.cpp
@@ -0,0 +1,15 @@
+class Solution {
+ public:
+ bool isCircularSentence(const string &sentence) const {
+ char prev = sentence.back();
+ stringstream ss(sentence);
+ string word;
+
+ while (ss >> word) {
+ if (word.front() != prev) return false;
+ prev = word.back();
+ }
+
+ return true;
+ }
+};
diff --git a/README.md b/README.md
@@ -319,6 +319,8 @@ reference and a base for solving problems.
| 0349 | Easy | [Intersection of Two Arrays](Problems/0349.cpp) |
| 0350 | Easy | [Intersection of Two Arrays II](Problems/0350.cpp) |
| 0352 | Hard | [Data Stream as Disjoint Intervals](Problems/0352.cpp) |
+| 0354 | Hard | [Russian Doll Envelopes](Problems/0354.cpp) |
+| 0355 | Medium | [Design Twitter](Problems/0355.cpp) |
| 0357 | Medium | [Count Numbers with Unique Digits](Problems/0357.cpp) |
| 0367 | Easy | [Valid Perfect Square](Problems/0367.cpp) |
| 0368 | Medium | [Largest Divisible Subset](Problems/0368.cpp) |
@@ -1288,6 +1290,7 @@ reference and a base for solving problems.
| 2485 | Easy | [Find the Pivot Integer](Problems/2485.cpp) |
| 2486 | Medium | [Append Characters to String to Make Subsequence](Problems/2486.cpp) |
| 2487 | Medium | [Remove Nodes From Linked List](Problems/2487.cpp) |
+| 2490 | Easy | [Circular Sentence](Problems/2490.cpp) |
| 2491 | Medium | [Divide Players Into Teams of Equal Skill](Problems/2491.cpp) |
| 2492 | Medium | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp) |
| 2497 | Medium | [Maximum Star Sum of a Graph](Problems/2497.cpp) |
