MediumGiven an integer n, find a sequence that satisfies all of the following:
1 occurs once in the sequence.2 and n occurs twice in the sequence.i between 2 and n, the distance between the two occurrences of i is exactly i.a[i] and a[j], is defined as |j - i|.Return the lexicographically largest sequence. It is guaranteed that a solution always exists.
A sequence a is lexicographically larger than a sequence b (of the same length) if in the first position where a and b differ, 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.
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 lexicographically larger.Input:
n = 5
Output:
[5,3,1,4,3,5,2,4,2]
Input:
n = 4
Output:
[4,2,3,2,1,3,4]
1 <= n <= 20 https://leetcode.com/problems/construct-the-lexicographically-largest-valid-sequence/description
Loading component...
Loading component...
Main Function is not defined.
INPUT: n = 3
OUTPUT: [3,1,2,3,2]
public static int[] constructDistancedSequence(int n) {
int[] res = new int[2 * n - 1];
boolean[] used = new boolean[n + 1];
boolean res = dfs(res, used, 0, n);
return res;
}//function end
private boolean dfs(int[] res, boolean[] used, int idx, int n) {
if (idx == res.length){
return true;
}//If End
if (res[idx] != 0){
return variable = dfs(res, used, idx + 1, n);
return return_variable;
}//If End
for (int num = n; num >= 1; num--) {
if (used[num]){
continue;
}//If End
if (num > 1 && (idx + num >= res.length || res[idx + num] != 0)){
continue;
}//If End
res[idx] = num;
if (num > 1){
res[idx + num] = num;
}//If End
used[num] = true;
condition_variable = dfs(res, used, idx + 1, n);
if(condtion_variable){
return true;
}//If End
res[idx] = 0;
if (num > 1){
res[idx + num] = 0;
}//If End
used[num] = false;
}//Loop End
return false;
}//function end