aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--construct_lexicographically_seq.c63
-rw-r--r--construct_lexicographically_seq.py59
2 files changed, 122 insertions, 0 deletions
diff --git a/construct_lexicographically_seq.c b/construct_lexicographically_seq.c
new file mode 100644
index 0000000..b33bafc
--- /dev/null
+++ b/construct_lexicographically_seq.c
@@ -0,0 +1,63 @@
+// 1718. Construct the Lexicographically Largest Valid Sequence
+#include "leetcode.h"
+
+/*
+ * given an integer 'n', find a sequence that satisfies all of the following:
+ * the integer '1' occurs once in the sequence, each integer between '2' and 'n'
+ * occurs twice in the sequence, and for every integer 'i' between '2' and 'n',
+ * the distance between the two occurence of 'i' is exactly 'i'. the distance
+ * between two numbers on the sequence, 'a[i]' and 'a[j]' is the absolute
+ * difference of their indices '|j - i|'.
+ */
+
+bool dfs(int *arr, int n, int idx, bool *vis, int max) {
+ if (idx >= n)
+ return true;
+ int next;
+ while (arr[idx])
+ idx++;
+ for (int i = max; i >= 1; i--) {
+ next = max;
+ if (i != 1 && idx + i >= n)
+ return false;
+ if (vis[i] || (i != 1 && arr[idx + i]))
+ continue;
+ vis[i] = true;
+ arr[idx] = i;
+ if (i != 1)
+ arr[idx + i] = i;
+ if (i == max)
+ while (vis[--next])
+ ;
+ if (!next)
+ return true;
+ if (dfs(arr, n, idx + 1, vis, next))
+ return true;
+ vis[i] = false;
+ arr[idx] = 0;
+ if (i != 1)
+ arr[idx + i] = 0;
+ }
+ return false;
+}
+
+int *constructDistancedSequence(int n, int *returnSize) {
+ int m = 2 * n - 1;
+ bool vis[24] = {0};
+ int *ans = (int *)calloc(m, sizeof(int));
+ dfs(ans, m, 0, vis, n);
+ (*returnSize) = m;
+ return ans;
+}
+
+int main() {
+ int rs1, *cds1 = constructDistancedSequence(3, &rs1);
+ int rs2, *cds2 = constructDistancedSequence(5, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", cds1[i]); // expect: 3 1 2 3 2
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", cds2[i]); // expect: 5 3 1 4 3 5 2 4 2
+ printf("\n");
+ free(cds1), free(cds2);
+}
diff --git a/construct_lexicographically_seq.py b/construct_lexicographically_seq.py
new file mode 100644
index 0000000..75df736
--- /dev/null
+++ b/construct_lexicographically_seq.py
@@ -0,0 +1,59 @@
+# 1718. Construct the Lexicographically Largest Valid Sequence
+
+"""
+given an integer 'n', find a sequence that satisfies all of the following:
+the integer '1' occurs once in the sequence, each integer between '2' and 'n'
+occurs twice in the sequence, and for every integer 'i' between '2' and 'n',
+the distance between the two occurence of 'i' is exactly 'i'. the distance
+between two numbers on the sequence, 'a[i]' and 'a[j]' is the absolute
+difference of their indices '|j - i|'.
+"""
+
+
+class Solution(object):
+ def constructDistancedSequence(self, n):
+ """
+ :type n: int
+ :rtype: List[int]
+ """
+ i, arr, vis = 0, [0] * (2 * n - 1), [False] * (n + 1)
+
+ def dfs(arr, i, vis):
+ if i >= 2 * n - 1:
+ return True
+ for j in range(n, 0, -1):
+ if (
+ j > 1
+ and (
+ (not (arr[i] == 0 and (i + j < 2 * n - 1) and arr[i + j] == 0))
+ or vis[j]
+ )
+ ) or (j == 1 and (arr[i] != 0 or vis[j])):
+ continue
+ if j > 1:
+ arr[i] = j
+ arr[i + j] = j
+ else:
+ arr[i] = j
+ vis[j] = True
+ next = i + 1
+ while next < 2 * n - 1 and arr[next]:
+ next += 1
+ if dfs(arr, next, vis):
+ return True
+ if j > 1:
+ arr[i] = 0
+ arr[i + j] = 0
+ else:
+ arr[i] = 0
+ vis[j] = False
+ return False
+
+ dfs(arr, i, vis)
+ return arr
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.constructDistancedSequence(3))
+ print(obj.constructDistancedSequence(5))