Construct the Lexicographically Largest Valid Sequence
给一个数字n, 求[1, n]的一个序列满足除了1以外的数组出现2次, 1 出现1次. 并且要求字典序最大的数组.
这个题试了几种规律, 发现如果n是奇数, 则第二位可放n-2, 依次递减, 然后再放偶数. 但是发现这种也有漏洞. 因为1只能放一次, 所以不好判断1最后的位置, 这会影响字典序的大小, 所以最后用的广搜实现的.
|
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 |
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; } } |