diff options
-rw-r--r-- | construct_lexicographically_seq.c | 63 | ||||
-rw-r--r-- | construct_lexicographically_seq.py | 59 |
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)) |