commit 97264eb4eb058514593528433e9681a46c07200f
parent a8191073f125dc1c532e676a6ac182a6e9752b83
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Wed, 6 Nov 2024 18:37:21 +0100
5 Random Problems
Diffstat:
6 files changed, 100 insertions(+), 0 deletions(-)
diff --git a/Problems/0441.cpp b/Problems/0441.cpp
@@ -0,0 +1,4 @@
+class Solution {
+ public:
+ int arrangeCoins(int n) const { return (sqrt(8l * n + 1) - 1) / 2; }
+};
diff --git a/Problems/0457.cpp b/Problems/0457.cpp
@@ -0,0 +1,38 @@
+class Solution {
+ public:
+ bool circularArrayLoop(vector<int> &nums) const {
+ const int n = size(nums);
+ static int seen[5001];
+
+ const auto next = [&](int k) {
+ const int res = (k + nums[k] % n + n) % n;
+ seen[res] = true;
+ return res;
+ };
+
+ memset(seen, 0x00, sizeof(seen));
+ for (auto &num : nums)
+ num %= n;
+
+ for (int i = 0; i < n; i++) {
+ if (seen[i]) continue;
+ int t = i, h = i;
+
+ do {
+ t = next(t);
+ h = next(next(h));
+ } while (t != h);
+
+ const bool dir = nums[t] > 0;
+ do {
+ t = next(t);
+ if ((nums[t] > 0) != dir) goto next;
+ } while (t != h);
+
+ if ((t + nums[t] + n) % n != t) return true;
+ next:;
+ }
+
+ return false;
+ }
+};
diff --git a/Problems/0461.cpp b/Problems/0461.cpp
@@ -0,0 +1,4 @@
+class Solution {
+ public:
+ int hammingDistance(unsigned x, unsigned y) const { return popcount(x ^ y); }
+};
diff --git a/Problems/0464.cpp b/Problems/0464.cpp
@@ -0,0 +1,32 @@
+class Solution {
+ static int8_t dp[1 << 20];
+
+ int rec(int maxi, int tgt, int k) {
+ if (dp[k] != 0) return dp[k] > 0;
+ if (tgt <= 0) return false;
+
+ for (int i = 1, mask = 1; i <= maxi; mask <<= 1, i++) {
+ if (k & mask) continue;
+ if (rec(maxi, tgt - i, k | mask)) continue;
+ dp[k] = 1;
+ return true;
+ }
+
+ dp[k] = -1;
+ return false;
+ }
+
+ public:
+ bool canIWin(int maxi, int tgt) {
+ if (tgt <= maxi) return true;
+
+ const int sum = maxi * (maxi + 1) / 2;
+ if (sum < tgt) return false;
+ if (sum == tgt) return maxi % 2;
+
+ memset(dp, 0x00, sizeof(dp));
+ return rec(maxi, tgt, 0);
+ }
+};
+
+int8_t Solution::dp[1 << 20];
diff --git a/Problems/0467.cpp b/Problems/0467.cpp
@@ -0,0 +1,17 @@
+class Solution {
+ public:
+ int findSubstringInWraproundString(const string &s) const {
+ const int n = size(s);
+ static int seen[26];
+
+ memset(seen, 0x00, sizeof(seen));
+ for (const char c : s)
+ seen[c - 'a'] = 1;
+ for (int i = 1, cnt = 1; i < n; i++) {
+ cnt = (s[i] - s[i - 1] + 26) % 26 == 1 ? cnt + 1 : 1;
+ seen[s[i] - 'a'] = max(seen[s[i] - 'a'], cnt);
+ }
+
+ return accumulate(seen, seen + 26, 0);
+ }
+};
diff --git a/README.md b/README.md
@@ -377,6 +377,7 @@ reference and a base for solving problems.
| 0437 | Medium | [Path Sum III](Problems/0437.cpp) |
| 0438 | Medium | [Find All Anagrams in a String](Problems/0438.cpp) |
| 0440 | Hard | [K-th Smallest in Lexicographical Order](Problems/0440.cpp) |
+| 0441 | Easy | [Arranging Coins](Problems/0441.cpp) |
| 0442 | Medium | [Find All Duplicates in an Array](Problems/0442.cpp) |
| 0443 | Medium | [String Compression](Problems/0443.cpp) |
| 0445 | Medium | [Add Two Numbers II](Problems/0445.cpp) |
@@ -391,11 +392,15 @@ reference and a base for solving problems.
| 0454 | Medium | [4Sum II](Problems/0454.cpp) |
| 0455 | Easy | [Assign Cookies](Problems/0455.cpp) |
| 0456 | Medium | [132 Pattern](Problems/0456.cpp) |
+| 0457 | Medium | [Circular Array Loop](Problems/0457.cpp) |
| 0458 | Hard | [Poor Pigs](Problems/0458.cpp) |
| 0459 | Easy | [Repeated Substring Pattern](Problems/0459.cpp) |
| 0460 | Hard | [LFU Cache](Problems/0460.cpp) |
+| 0461 | Easy | [Hamming Distance](Problems/0461.cpp) |
| 0462 | Medium | [Minimum Moves to Equal Array Elements II](Problems/0462.cpp) |
| 0463 | Easy | [Island Perimeter](Problems/0463.cpp) |
+| 0464 | Medium | [Can I Win](Problems/0464.cpp) |
+| 0467 | Medium | [Unique Substrings in Wraparound String](Problems/0467.cpp) |
| 0472 | Hard | [Concatenated Words](Problems/0472.cpp) |
| 0476 | Easy | [Number Complement](Problems/0476.cpp) |
| 0477 | Medium | [Total Hamming Distance](Problems/0477.cpp) |
