commit 24eb038d748aff5c5e1b686a52d2e0841070841e
parent 97264eb4eb058514593528433e9681a46c07200f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Thu, 7 Nov 2024 13:55:28 +0100
2 Random Problems
Diffstat:
3 files changed, 80 insertions(+), 0 deletions(-)
diff --git a/Problems/0423.cpp b/Problems/0423.cpp
@@ -0,0 +1,22 @@
+class Solution {
+ public:
+ string originalDigits(const string &s) {
+ string word[10] = {"zero", "two", "six", "eight", "three", "seven", "five", "four", "one", "nine"};
+ uint8_t mapping[10] = {0, 2, 6, 8, 3, 7, 5, 4, 1, 9};
+ uint32_t count[26] = {0}, digits[10] = {0};
+ char *letters = "zwxghsvuoi";
+ string res;
+
+ for (const char c : s)
+ count[c - 'a']++;
+ for (int i = 0; i <= 9; i++) {
+ const int cnt = digits[mapping[i]] = count[letters[i] - 'a'];
+ for (const char c : word[i])
+ count[c - 'a'] -= cnt;
+ }
+ for (int i = 0; i <= 9; i++)
+ res += string(digits[i], '0' + i);
+
+ return res;
+ }
+};
diff --git a/Problems/0473.cpp b/Problems/0473.cpp
@@ -0,0 +1,56 @@
+// Backtracking: 4 ^ N
+class Solution {
+ static bool find(const vector<int> &sticks, const int side, int idx, int crnt[4]) {
+ if (idx == size(sticks)) return crnt[0] == side && crnt[1] == side && crnt[2] == side;
+
+ for (int i = 0; i < 4; i++) {
+ if (crnt[i] + sticks[idx] > side) continue;
+
+ crnt[i] += sticks[idx];
+ if (find(sticks, side, idx + 1, crnt)) return true;
+ crnt[i] -= sticks[idx];
+ }
+
+ return false;
+ }
+
+ public:
+ bool makesquare(vector<int> &sticks) const {
+ const int sum = accumulate(begin(sticks), end(sticks), 0);
+ if (sum % 4 != 0) return false;
+
+ sort(begin(sticks), end(sticks), greater<>());
+ int crnt[4] = {sticks[0], 0};
+ return find(sticks, sum / 4, 1, crnt);
+ }
+};
+
+// DP: N * 2 ^ N
+class Solution {
+ uint8_t dp[4][1 << 16] = {0};
+
+ bool find(const vector<int> &sticks, int left, int side, int crnt, uint16_t mask) {
+ if (dp[left][mask]) return false;
+ dp[left][mask] = 1;
+
+ if (crnt == side) left--, crnt = 0;
+ if (!left) return true;
+
+ for (int i = 0, msk = 1; i < size(sticks); i++, msk <<= 1) {
+ if (mask & msk) continue;
+ if (crnt + sticks[i] > side) continue;
+ if (find(sticks, left, side, crnt + sticks[i], mask | msk)) return true;
+ }
+
+ return false;
+ }
+
+ public:
+ bool makesquare(vector<int> &sticks) {
+ const int sum = accumulate(begin(sticks), end(sticks), 0);
+ if (sum % 4 != 0) return false;
+
+ const int side = sum / 4;
+ return find(sticks, 3, side, 0, 0);
+ }
+};
diff --git a/README.md b/README.md
@@ -365,6 +365,7 @@ reference and a base for solving problems.
| 0417 | Medium | [Pacific Atlantic Water Flow](Problems/0417.cpp) |
| 0419 | Medium | [Battleships in a Board](Problems/0419.cpp) |
| 0421 | Medium | [Maximum XOR of Two Numbers in an Array](Problems/0421.cpp) |
+| 0423 | Medium | [Reconstruct Original Digits from English](Problems/0423.cpp) |
| 0424 | Medium | [Longest Repeating Character Replacement](Problems/0424.cpp) |
| 0427 | Medium | [Construct Quad Tree](Problems/0427.cpp) |
| 0429 | Medium | [N-ary Tree Level Order Traversal](Problems/0429.cpp) |
@@ -402,6 +403,7 @@ reference and a base for solving problems.
| 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) |
+| 0473 | Medium | [Matchsticks to Square](Problems/0473.cpp) |
| 0476 | Easy | [Number Complement](Problems/0476.cpp) |
| 0477 | Medium | [Total Hamming Distance](Problems/0477.cpp) |
| 0481 | Medium | [Magical String](Problems/0481.cpp) |
