1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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))
|