leetcode

commit 60bbca57a435dfc044ce061db6ce810789830f6e
parent 2208abd0e42780a715f544192b54af01f2d529ff
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 22 Feb 2024 09:43:21 +0000

1 Random Problem

Diffstat:
A
Problems/1718.cpp
 | 
36
++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 37 insertions(+), 0 deletions(-)
diff --git a/Problems/1718.cpp b/Problems/1718.cpp
@@ -0,0 +1,36 @@
+class Solution {
+    bool seen[21] = {0};
+    vector<int> res = vector(39, 0);
+
+    bool rec(const int n, int crnt) {
+        while (crnt < size(res) && res[crnt])
+            crnt++;
+        if (crnt == size(res)) return true;
+
+        for (int i = n; i > 1; i--) {
+            if (seen[i] || crnt + i >= size(res) || res[crnt + i]) continue;
+            res[crnt + i] = res[crnt] = i;
+            seen[i] = true;
+            if (rec(n, crnt + 1)) return true;
+            seen[i] = false;
+            res[crnt + i] = 0;
+        }
+
+        if (!seen[1]) {
+            res[crnt] = 1;
+            seen[1] = true;
+            if (rec(n, crnt + 1)) return true;
+            seen[1] = false;
+        }
+        res[crnt] = 0;
+
+        return false;
+    }
+
+  public:
+    vector<int> constructDistancedSequence(const int n) {
+        res.resize(2 * n - 1);
+        rec(n, 0);
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -871,6 +871,7 @@ for solving problems.
 |  1704  |    Easy    | [Determine if String Halves Are Alike](Problems/1704.cpp)                                          |
 |  1706  |   Medium   | [Where Will the Ball Fall](Problems/1706.cpp)                                                      |
 |  1716  |    Easy    | [Calculate Money in Leetcode Bank](Problems/1716.cpp)                                              |
+|  1718  |   Medium   | [Construct the Lexicographically Largest Valid Sequence](Problems/1718.cpp)                        |
 |  1721  |   Medium   | [Swapping Nodes in a Linked List](Problems/1721.cpp)                                               |
 |  1722  |   Medium   | [Minimize Hamming Distance After Swap Operations](Problems/1722.cpp)                               |
 |  1726  |   Medium   | [Tuple with Same Product](Problems/1726.cpp)                                                       |