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
andn
occurs twice in the sequence. - For every integer
i
between2
andn
, the distance between the two occurrences ofi
is exactlyi
.
The distance between two numbers on the sequence, a[i]
and a[j]
, is the absolute difference of their indices, |j - i|
.
Return the lexicographically largest sequence. It is guaranteed that under the given constraints, there is always a solution.
A sequence a
is lexicographically larger than a sequence b
(of the same length) if in the first position where a
and b
differ, sequence a
has a number greater than the corresponding number in b
. For example, [0,1,9,0]
is lexicographically larger than [0,1,5,6]
because the first position they differ is at the third number, and 9
is greater than 5
.
Example 1:
Input: n = 3 Output: [3,1,2,3,2] Explanation: [2,3,2,1,3] is also a valid sequence, but [3,1,2,3,2] is the lexicographically largest valid sequence.
Example 2:
Input: n = 5 Output: [5,3,1,4,3,5,2,4,2]
Constraints:
1 <= n <= 20
Rust Solution
struct Solution;
impl Solution {
fn construct_distanced_sequence(n: i32) -> Vec<i32> {
let mut nums: Vec<i32> = vec![];
for i in (2..=n).rev() {
nums.push(i);
}
nums.push(1);
let n = n as usize;
let m = 2 * n - 1;
let mut cur = vec![0; m];
let mut visited: u32 = (1 << n) - 1;
Self::dfs(0, &mut cur, &mut visited, &nums, m, n);
cur
}
fn dfs(
start: usize,
cur: &mut Vec<i32>,
visited: &mut u32,
nums: &[i32],
m: usize,
n: usize,
) -> bool {
if start == m {
true
} else {
if cur[start] == 0 {
for i in 0..n {
if 1 << i & *visited != 0 {
let distance = nums[i] as usize;
if distance == 1 {
*visited &= !(1 << i);
cur[start] = nums[i];
let found = Self::dfs(start + 1, cur, visited, nums, m, n);
if found {
return true;
}
cur[start] = 0;
*visited |= 1 << i;
} else {
if start + distance < m && cur[start + distance] == 0 {
cur[start] = nums[i];
cur[start + distance] = nums[i];
*visited &= !(1 << i);
let found = Self::dfs(start + 1, cur, visited, nums, m, n);
if found {
return true;
}
cur[start + distance] = 0;
cur[start] = 0;
*visited |= 1 << i;
}
}
}
}
false
} else {
Self::dfs(start + 1, cur, visited, nums, m, n)
}
}
}
}
#[test]
fn test() {
let n = 3;
let res = vec![3, 1, 2, 3, 2];
assert_eq!(Solution::construct_distanced_sequence(n), res);
let n = 5;
let res = vec![5, 3, 1, 4, 3, 5, 2, 4, 2];
assert_eq!(Solution::construct_distanced_sequence(n), res);
}
Having problems with this solution? Click here to submit an issue on github.