commit 4d7621ffe152a5af0283fa78ddeaf64dd26f1f04
parent 93c4fbb9b604739d4084d9d7d6587946515abaf0
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Fri, 12 Jan 2024 22:10:02 +0000
4 Random Problems
Diffstat:
5 files changed, 93 insertions(+), 0 deletions(-)
diff --git a/Problems/0967.cpp b/Problems/0967.cpp
@@ -0,0 +1,24 @@
+class Solution {
+ public:
+ vector<int> numsSameConsecDiff(const int n, const int k) const {
+ static const int lookup[] = {0, 1, 10, 100, 1000, 10000,
+ 100000, 1000000, 10000000, 100000000, 1000000000};
+ vector<int> res;
+ queue<int> q;
+ for (int i = 1; i <= 9; i++)
+ q.push(i);
+ while (!q.empty()) {
+ const int crnt = q.front();
+ q.pop();
+ if (crnt >= lookup[n])
+ res.push_back(crnt);
+ else {
+ const int low = crnt % 10 - k, high = crnt % 10 + k;
+ if (high <= 9) q.push(crnt * 10 + high);
+ if (k == 0) continue;
+ if (low >= 0) q.push(crnt * 10 + low);
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/1749.cpp b/Problems/1749.cpp
@@ -0,0 +1,25 @@
+class Solution {
+ public:
+ int maxAbsoluteSum(const vector<int> &nums) const {
+ int mini = 0, maxi = 0, res = 0;
+ for (const int n : nums) {
+ maxi = max(0, maxi + n);
+ mini = min(0, mini + n);
+ res = max({res, maxi, -mini});
+ }
+ return res;
+ }
+};
+
+class Solution {
+ public:
+ int maxAbsoluteSum(const vector<int> &nums) const {
+ int mini = 0, maxi = 0, sum = 0;
+ for (const int n : nums) {
+ sum += n;
+ mini = min(mini, sum);
+ maxi = max(maxi, sum);
+ }
+ return maxi - mini;
+ }
+};
diff --git a/Problems/2058.cpp b/Problems/2058.cpp
@@ -0,0 +1,25 @@
+class Solution {
+ public:
+ vector<int> nodesBetweenCriticalPoints(ListNode *head) {
+ ListNode *prev = head, *crnt = head->next, *next;
+ vector<int> res(2, INT_MAX);
+ int first = 0, last = 0;
+ for (int pos = 1; next = crnt->next; pos++) {
+ if (crnt->val > prev->val && crnt->val > next->val ||
+ crnt->val < prev->val && crnt->val < next->val) {
+ if (!first)
+ first = last = pos;
+ else {
+ res[0] = min(res[0], pos - last);
+ res[1] = pos - first;
+ last = pos;
+ }
+ }
+ prev = crnt;
+ crnt = next;
+ }
+ if (res[0] == INT_MAX) res[0] = -1;
+ if (res[1] == INT_MAX) res[1] = -1;
+ return res;
+ }
+};
diff --git a/Problems/2997.cpp b/Problems/2997.cpp
@@ -0,0 +1,15 @@
+static auto _ = []() {
+ ios_base::sync_with_stdio(false);
+ cout.tie(NULL);
+ cin.tie(NULL);
+ return NULL;
+}();
+
+class Solution {
+ public:
+ int minOperations(const vector<int> &nums, int k) const {
+ for (const int n : nums)
+ k ^= n;
+ return __builtin_popcount(k);
+ }
+};
diff --git a/README.md b/README.md
@@ -530,6 +530,7 @@ for solving problems.
| 0958 | Medium | [Check Completeness of a Binary Tree](Problems/0958.cpp) |
| 0959 | Medium | [Regions Cut By Slashes](Problems/0959.cpp) |
| 0965 | Easy | [Univalued Binary Tree](Problems/0965.cpp) |
+| 0967 | Medium | [Numbers With Same Consecutive Differences](Problems/0967.cpp) |
| 0969 | Medium | [Pancake Sorting](Problems/0969.cpp) |
| 0973 | Medium | [K Closest Points to Origin](Problems/0973.cpp) |
| 0974 | Medium | [Subarray Sums Divisible by K](Problems/0974.cpp) |
@@ -827,6 +828,7 @@ for solving problems.
| 1738 | Medium | [Find Kth Largest XOR Coordinate Value](Problems/1738.cpp) |
| 1741 | Easy | [Find Total Time Spent by Each Employee](Problems/1741.cpp) |
| 1743 | Medium | [Restore the Array From Adjacent Pairs](Problems/1743.cpp) |
+| 1749 | Medium | [Maximum Absolute Sum of Any Subarray](Problems/1749.cpp) |
| 1751 | Hard | [Maximum Number of Events That Can Be Attended II](Problems/1751.cpp) |
| 1753 | Medium | [Maximum Score From Removing Stones](Problems/1753.cpp) |
| 1757 | Easy | [Recyclable and Low Fat Products](Problems/1757.cpp) |
@@ -902,6 +904,7 @@ for solving problems.
| 2043 | Medium | [Simple Bank System](Problems/2043.cpp) |
| 2044 | Medium | [Count Number of Maximum Bitwise-OR Subsets](Problems/2044.cpp) |
| 2050 | Hard | [Parallel Courses III](Problems/2050.cpp) |
+| 2058 | Medium | [Find the Minimum and Maximum Number of Nodes Between Critical Points](Problems/2058.cpp) |
| 2073 | Easy | [Time Needed to Buy Tickets](Problems/2073.cpp) |
| 2079 | Medium | [Watering Plants](Problems/2079.cpp) |
| 2085 | Easy | [Count Common Words With One Occurrence](Problems/2085.cpp) |
@@ -1053,3 +1056,4 @@ for solving problems.
| 2900 | Medium | [Longest Unequal Adjacent Groups Subsequence I](Problems/2900.cpp) |
| 2914 | Medium | [Minimum Number of Changes to Make Binary String Beautiful](Problems/2914.cpp) |
| 2947 | Medium | [Count Beautiful Substrings I](Problems/2947.cpp) |
+| 2997 | Medium | [Minimum Number of Operations to Make Array XOR Equal to K](Problems/2997.cpp) |
