comments | difficulty | edit_url | rating | source | tags | ||
---|---|---|---|---|---|---|---|
true |
中等 |
2080 |
第 43 场双周赛 Q3 |
|
给你一个整数 n
,请你找到满足下面条件的一个序列:
- 整数
1
在序列中只出现一次。 2
到n
之间每个整数都恰好出现两次。- 对于每个
2
到n
之间的整数i
,两个i
之间出现的距离恰好为i
。
序列里面两个数 a[i]
和 a[j]
之间的 距离 ,我们定义为它们下标绝对值之差 |j - i|
。
请你返回满足上述条件中 字典序最大 的序列。题目保证在给定限制条件下,一定存在解。
一个序列 a
被认为比序列 b
(两者长度相同)字典序更大的条件是: a
和 b
中第一个不一样的数字处,a
序列的数字比 b
序列的数字大。比方说,[0,1,9,0]
比 [0,1,5,6]
字典序更大,因为第一个不同的位置是第三个数字,且 9
比 5
大。
示例 1:
输入:n = 3 输出:[3,1,2,3,2] 解释:[2,3,2,1,3] 也是一个可行的序列,但是 [3,1,2,3,2] 是字典序最大的序列。
示例 2:
输入:n = 5 输出:[5,3,1,4,3,5,2,4,2]
提示:
1 <= n <= 20
class Solution:
def constructDistancedSequence(self, n: int) -> List[int]:
def dfs(u):
if u == n * 2:
return True
if path[u]:
return dfs(u + 1)
for i in range(n, 1, -1):
if cnt[i] and u + i < n * 2 and path[u + i] == 0:
cnt[i] = 0
path[u] = path[u + i] = i
if dfs(u + 1):
return True
path[u] = path[u + i] = 0
cnt[i] = 2
if cnt[1]:
cnt[1], path[u] = 0, 1
if dfs(u + 1):
return True
path[u], cnt[1] = 0, 1
return False
path = [0] * (n * 2)
cnt = [2] * (n * 2)
cnt[1] = 1
dfs(1)
return path[1:]
class Solution {
private int[] path;
private int[] cnt;
private int n;
public int[] constructDistancedSequence(int n) {
this.n = n;
path = new int[n * 2];
cnt = new int[n * 2];
Arrays.fill(cnt, 2);
cnt[1] = 1;
dfs(1);
int[] ans = new int[n * 2 - 1];
for (int i = 0; i < ans.length; ++i) {
ans[i] = path[i + 1];
}
return ans;
}
private boolean dfs(int u) {
if (u == n * 2) {
return true;
}
if (path[u] > 0) {
return dfs(u + 1);
}
for (int i = n; i > 1; --i) {
if (cnt[i] > 0 && u + i < n * 2 && path[u + i] == 0) {
cnt[i] = 0;
path[u] = i;
path[u + i] = i;
if (dfs(u + 1)) {
return true;
}
cnt[i] = 2;
path[u] = 0;
path[u + i] = 0;
}
}
if (cnt[1] > 0) {
path[u] = 1;
cnt[1] = 0;
if (dfs(u + 1)) {
return true;
}
cnt[1] = 1;
path[u] = 0;
}
return false;
}
}
class Solution {
public:
int n;
vector<int> cnt, path;
vector<int> constructDistancedSequence(int _n) {
n = _n;
cnt.resize(n * 2, 2);
path.resize(n * 2);
cnt[1] = 1;
dfs(1);
vector<int> ans;
for (int i = 1; i < n * 2; ++i) ans.push_back(path[i]);
return ans;
}
bool dfs(int u) {
if (u == n * 2) return 1;
if (path[u]) return dfs(u + 1);
for (int i = n; i > 1; --i) {
if (cnt[i] && u + i < n * 2 && !path[u + i]) {
path[u] = path[u + i] = i;
cnt[i] = 0;
if (dfs(u + 1)) return 1;
cnt[i] = 2;
path[u] = path[u + i] = 0;
}
}
if (cnt[1]) {
path[u] = 1;
cnt[1] = 0;
if (dfs(u + 1)) return 1;
cnt[1] = 1;
path[u] = 0;
}
return 0;
}
};
func constructDistancedSequence(n int) []int {
path := make([]int, n*2)
cnt := make([]int, n*2)
for i := range cnt {
cnt[i] = 2
}
cnt[1] = 1
var dfs func(u int) bool
dfs = func(u int) bool {
if u == n*2 {
return true
}
if path[u] > 0 {
return dfs(u + 1)
}
for i := n; i > 1; i-- {
if cnt[i] > 0 && u+i < n*2 && path[u+i] == 0 {
cnt[i] = 0
path[u], path[u+i] = i, i
if dfs(u + 1) {
return true
}
cnt[i] = 2
path[u], path[u+i] = 0, 0
}
}
if cnt[1] > 0 {
cnt[1] = 0
path[u] = 1
if dfs(u + 1) {
return true
}
cnt[1] = 1
path[u] = 0
}
return false
}
dfs(1)
return path[1:]
}