greedy+backtracking O(n!) time O(n) space
这道题的关键点是要发现贪心去放有可能一次性放不进去，所以必须要回溯反复试数
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
| class Solution {
public:
vector<int> constructDistancedSequence(int n) {
this->n = n;
res.resize(n + n - 1);
dfs(0);
return res;
}
bool dfs(int i) {
if (i == size(res)) return true;
if (res[i] != 0) return dfs(i + 1);
for (int x = n; x > 0; --x) {
if (used & (1 << x)) continue;
int offset = x == 1 ? 0 : x;
if (i + offset < size(res) && res[i + offset] == 0) {
res[i] = res[i + offset] = x;
used ^= 1 << x;
if (dfs(i + 1)) return true;
used ^= 1 << x;
res[i] = res[i + offset] = 0;
}
}
return false;
}
int n, used = 0;
vector<int> res;
};
|
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
| class Solution {
public:
vector<int> constructDistancedSequence(int n) {
this->n = n;
res.resize(n + n - 1);
used.resize(n + 1);
dfs(0);
return res;
}
bool dfs(int i) {
if (i == size(res)) return true;
if (res[i] != 0) return dfs(i + 1);
for (int x = n; x > 0; --x) {
if (used[x]) continue;
int offset = x == 1 ? 0 : x;
if (i + offset < size(res) && res[i + offset] == 0) {
res[i] = res[i + offset] = x;
used[x] = true;
if (dfs(i + 1)) return true;
used[x] = false;
res[i] = res[i + offset] = 0;
}
}
return false;
}
int n;
vector<int> res;
vector<bool> used;
};
|
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
| class Solution {
public:
vector<int> constructDistancedSequence(int n) {
this->n = n;
res.resize(n + n - 1);
used.resize(n + 1);
dfs(0);
return res;
}
bool dfs(int i) {
if (i == size(res)) return true;
if (res[i] != 0) return dfs(i + 1);
for (int x = n; x > 0; --x) {
if (used[x]) continue;
if (x == 1) {
res[i] = x;
used[x] = true;
if (dfs(i + 1)) return true;
used[x] = false;
res[i] = 0;
} else if (i + x < size(res) && res[i + x] == 0) {
res[i] = res[i + x] = x;
used[x] = true;
if (dfs(i + 1)) return true;
used[x] = false;
res[i] = res[i + x] = 0;
}
}
return false;
}
int n;
vector<int> res;
vector<bool> used;
};
|