commit 100c1faec99c7b1210f744dae99361da2e64e41e
parent f2301f8ab0267347bf106cffd38a443e48a8484f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Tue, 16 Jan 2024 22:29:11 +0000
2 Random Problems
Diffstat:
5 files changed, 82 insertions(+), 0 deletions(-)
diff --git a/Problems/1016.cpp b/Problems/1016.cpp
@@ -0,0 +1,15 @@
+class Solution {
+ public:
+ bool queryString(const string &s, int n) {
+ vector<bool> seen(n);
+ int count = 0;
+ for (int i = 0; i < size(s) && count < n; i++) {
+ if (s[i] == '0') continue;
+ for (int j = 0, crnt = 0; j < 30 && i + j < size(s) && crnt < n; j++) {
+ crnt = (crnt << 1) + (s[i + j] & 1);
+ if (crnt <= n && !seen[crnt]) seen[crnt] = ++count;
+ }
+ }
+ return count == n;
+ }
+};
diff --git a/Problems/1405.cpp b/Problems/1405.cpp
@@ -0,0 +1,31 @@
+class Solution {
+ typedef tuple<int, char> record;
+
+ public:
+ string longestDiverseString(int a, int b, int c) const {
+ priority_queue<record> pq;
+ if (a > 0) pq.emplace(a, 'a');
+ if (b > 0) pq.emplace(b, 'b');
+ if (c > 0) pq.emplace(c, 'c');
+
+ string res;
+ int last = '!', lastc = 1;
+ while (!pq.empty()) {
+ const auto [cnt, c] = pq.top();
+ pq.pop();
+ if (c == last && lastc == 2) {
+ if (pq.empty()) return res;
+ const auto [ocnt, oc] = pq.top();
+ pq.pop();
+ if (ocnt > 1) pq.emplace(ocnt - 1, oc);
+ res += oc;
+ lastc = 0;
+ }
+ if (c != last) last = c, lastc = 0;
+ if (cnt > 1) pq.emplace(cnt - 1, c);
+ res += c;
+ lastc++;
+ }
+ return res;
+ }
+};
diff --git a/Problems/1504.cpp b/Problems/1504.cpp
@@ -0,0 +1,28 @@
+class Solution {
+ public:
+ int numSubmat(vector<vector<int>> &mat) const {
+ const int n = size(mat), m = size(mat[0]);
+
+ for (int j = 0; j < m; j++) {
+ for (int i = 0, acc = 0; i < n; i++) {
+ if (mat[i][j])
+ mat[i][j] = acc += 1;
+ else
+ acc = 0;
+ }
+ }
+
+ int res = 0;
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < m; j++) {
+ int mini = mat[i][j];
+ for (int k = j; k >= 0; k--) {
+ mini = min(mini, mat[i][k]);
+ if (!mini) break;
+ res += mini;
+ }
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/2579.cpp b/Problems/2579.cpp
@@ -0,0 +1,4 @@
+class Solution {
+ public:
+ long long coloredCells(int n) const { return 1 + 2ll * n * (n - 1); }
+};
diff --git a/README.md b/README.md
@@ -553,6 +553,7 @@ for solving problems.
| 1008 | Medium | [Construct Binary Search Tree from Preorder Traversal](Problems/1008.cpp) |
| 1011 | Medium | [Capacity To Ship Packages Within D Days](Problems/1011.cpp) |
| 1014 | Medium | [Best Sightseeing Pair](Problems/1014.cpp) |
+| 1016 | Medium | [Binary String With Substrings Representing 1 To N](Problems/1016.cpp) |
| 1017 | Medium | [Convert to Base -2](Problems/1017.cpp) |
| 1019 | Medium | [Next Greater Node In Linked List](Problems/1019.cpp) |
| 1020 | Medium | [Number of Enclaves](Problems/1020.cpp) |
@@ -701,6 +702,7 @@ for solving problems.
| 1396 | Medium | [Design Underground System](Problems/1396.cpp) |
| 1400 | Medium | [Construct K Palindrome Strings](Problems/1400.cpp) |
| 1402 | Hard | [Reducing Dishes](Problems/1402.cpp) |
+| 1405 | Medium | [Longest Happy String](Problems/1405.cpp) |
| 1406 | Hard | [Stone Game III](Problems/1406.cpp) |
| 1407 | Easy | [Top Travellers](Problems/1407.cpp) |
| 1409 | Medium | [Queries on a Permutation With Key](Problems/1409.cpp) |
@@ -744,6 +746,7 @@ for solving problems.
| 1498 | Medium | [Number of Subsequences That Satisfy the Given Sum Condition](Problems/1498.cpp) |
| 1502 | Easy | [Can Make Arithmetic Progression From Sequence](Problems/1502.cpp) |
| 1503 | Medium | [Last Moment Before All Ants Fall Out of a Plank](Problems/1503.cpp) |
+| 1504 | Medium | [Count Submatrices With All Ones](Problems/1504.cpp) |
| 1508 | Medium | [Range Sum of Sorted Subarray Sums](Problems/1508.cpp) |
| 1512 | Easy | [Number of Good Pairs](Problems/1512.cpp) |
| 1514 | Medium | [Path with Maximum Probability](Problems/1514.cpp) |
@@ -1016,6 +1019,7 @@ for solving problems.
| 2542 | Medium | [Maximum Subsequence Score](Problems/2542.cpp) |
| 2545 | Medium | [Sort the Students by Their Kth Score](Problems/2545.cpp) |
| 2551 | Hard | [Put Marbles in Bags](Problems/2551.cpp) |
+| 2579 | Medium | [Count Total Number of Colored Cells](Problems/2579.cpp) |
| 2610 | Medium | [Convert an Array Into a 2D Array With Conditions](Problems/2610.cpp) |
| 2616 | Medium | [Minimize the Maximum Difference of Pairs](Problems/2616.cpp) |
| 2620 | Easy | [Counter](Problems/2620.js) |
