Construct the Lexicographically Largest Valid Sequence
给一个数字n, 求[1, n]的一个序列满足除了1以外的数组出现2次, 1 出现1次. 并且要求字典序最大的数组.
这个题试了几种规律, 发现如果n是奇数, 则第二位可放n-2, 依次递减, 然后再放偶数. 但是发现这种也有漏洞. 因为1只能放一次, 所以不好判断1最后的位置, 这会影响字典序的大小, 所以最后用的广搜实现的.
class Solution {
public int[] constructDistancedSequence(int n) {
int[] res = new int[n * 2 - 1];
boolean[] used = new boolean[n + 1];
dfs(n, 0, res, used);
return res;
}
private boolean dfs(int n, int pos, int[] res, boolean[] used) {
if(pos == res.length) // finish placement
return true;
if(res[pos] != 0) // if has placed before
return dfs(n, pos + 1, res, used);
for(int j = n ; j >= 1; j--) {
if(used[j])// if it is used, skip
continue;
if(j != 1 && j + pos >= res.length)// if it is out of bound
continue;
if(j != 1 && res[j + pos] != 0)// if it is used
continue;
res[pos] = j;
if(j != 1)
res[pos + j] = j;
used[j] = true;
if(dfs(n, pos + 1, res, used)){
return true;
}
else{
// reset
res[pos] = 0;
if(j != 1)
res[pos + j] = 0;
used[j] = false;
}
}
return false;
}
}