commit 06f43b0a9aa072a9b8befb085d720499f22d8976
parent 6a5c6dd5bb9cc5c1a7bc58afec6cf583f43d942a
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Thu, 18 Jan 2024 22:30:56 +0000
4 Random Problems
Diffstat:
5 files changed, 79 insertions(+), 0 deletions(-)
diff --git a/Problems/0838.cpp b/Problems/0838.cpp
@@ -0,0 +1,31 @@
+class Solution {
+ public:
+ string pushDominoes(const string &dominoes) const {
+ static int forces[100001];
+
+ const int n = size(dominoes);
+ string res(n, '.');
+
+ for (int i = 0, force = 0; i < n; i++) {
+ if (dominoes[i] == 'R')
+ force = n;
+ else if (dominoes[i] == 'L')
+ force = 0;
+ else
+ force = max(force - 1, 0);
+ forces[i] = force;
+ }
+
+ for (int i = n - 1, force = 0; i >= 0; i--) {
+ if (dominoes[i] == 'L')
+ force = n;
+ else if (dominoes[i] == 'R')
+ force = 0;
+ else
+ force = max(force - 1, 0);
+ if (forces[i] != force) res[i] = forces[i] > force ? 'R' : 'L';
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/1052.cpp b/Problems/1052.cpp
@@ -0,0 +1,15 @@
+class Solution {
+ public:
+ int maxSatisfied(const vector<int> &customers, const vector<int> &grumpy, int minutes) const {
+ const int n = size(customers);
+ int total = 0, crnt = 0, maxi = 0;
+
+ for (int i = 0; i < n; i++) {
+ (grumpy[i] ? crnt : total) += customers[i];
+ if (i >= minutes && grumpy[i - minutes]) crnt -= customers[i - minutes];
+ maxi = max(maxi, crnt);
+ }
+
+ return total + maxi;
+ }
+};
diff --git a/Problems/1680.cpp b/Problems/1680.cpp
@@ -0,0 +1,13 @@
+class Solution {
+ static const int MOD = 1E9 + 7;
+
+ public:
+ int concatenatedBinary(int n) const {
+ long crnt = 0;
+ for (int i = 1, size = 0; i <= n; i++) {
+ if (__builtin_popcount(i) == 1) size++;
+ crnt = ((crnt << size) + i) % MOD;
+ }
+ return crnt;
+ }
+};
diff --git a/Problems/2568.cpp b/Problems/2568.cpp
@@ -0,0 +1,16 @@
+class Solution {
+ public:
+ int minImpossibleOR(const vector<int> &nums) const {
+ vector<bool> seen(32, false);
+
+ for (const int n : nums) {
+ if (__builtin_popcount(n) != 1) continue;
+ seen[__builtin_ffs(n) - 1] = true;
+ }
+
+ for (int i = 0; i < 32; i++) {
+ if (!seen[i]) return 1 << i;
+ }
+ return -1;
+ }
+};
diff --git a/README.md b/README.md
@@ -471,6 +471,7 @@ for solving problems.
| 0830 | Medium | [Kth Smallest Element in a BST](Problems/0230.cpp) |
| 0835 | Medium | [Image Overlap](Problems/0835.cpp) |
| 0837 | Medium | [New 21 Game](Problems/0837.cpp) |
+| 0838 | Medium | [Push Dominoes](Problems/0838.cpp) |
| 0839 | Hard | [Similar String Groups](Problems/0839.cpp) |
| 0841 | Medium | [Keys and Rooms](Problems/0841.cpp) |
| 0844 | Easy | [Backspace String Compare](Problems/0844.cpp) |
@@ -576,6 +577,7 @@ for solving problems.
| 1048 | Medium | [Longest String Chain](Problems/1048.cpp) |
| 1050 | Easy | [Actors and Directors Who Cooperated At Least Three Times](Problems/1050.cpp) |
| 1051 | Easy | [Height Checker](Problems/1051.cpp) |
+| 1052 | Medium | [Grumpy Bookstore Owner](Problems/1052.cpp) |
| 1061 | Medium | [Lexicographically Smallest Equivalent String](Problems/1061.cpp) |
| 1068 | Easy | [Product Sales Analysis I](Problems/1068.cpp) |
| 1070 | Medium | [Product Sales Analysis III](Problems/1070.cpp) |
@@ -812,6 +814,7 @@ for solving problems.
| 1672 | Easy | [Richest Customer Wealth](Problems/1672.cpp) |
| 1675 | Hard | [Minimize Deviation in Array](Problems/1675.cpp) |
| 1679 | Medium | [Max Number of K-Sum Pairs](Problems/1679.cpp) |
+| 1680 | Medium | [Concatenation of Consecutive Binary Numbers](Problems/1680.cpp) |
| 1683 | Easy | [Invalid Tweets](Problems/1683.cpp) |
| 1685 | Medium | [Sum of Absolute Differences in a Sorted Array](Problems/1685.cpp) |
| 1688 | Easy | [Count of Matches in Tournament](Problems/1688.cpp) |
@@ -1022,6 +1025,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) |
+| 2568 | Medium | [Minimum Impossible OR](Problems/2568.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) |
