class Solution {
public:
vector<int> constructDistancedSequence(int n) {
}
};
1718. 构建字典序最大的可行序列
给你一个整数 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原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-05-29 17:50:32
func constructDistancedSequence(n int) []int {
size := 2*n - 1
// 答案数组
res := make([]int, size)
// 用来检查数字是否被使用的辅助数组，0位置弃用
vis := make([]bool, n+1)
var dfs func(res []int, vis []bool, idx int) bool
dfs = func(res []int, vis []bool, idx int) bool {
// 特判，走到了尽头，判断一下是不是用掉了全部数字
if idx == len(res) {
for i := 1; i <= n; i++ {
if !vis[i] {
return false
}
}
return true
}
// 特判，这一个位置已经占用了，去下一个位置
if res[idx] != 0 {
return dfs(res, vis, idx+1)
}
// 从最大的n开始到2为止判断是不是能得到答案
for i := n; i > 1; i-- {
if vis[i] {
continue
}
// 发现了一个有可能的位置
if idx+i < len(res) && res[idx+i] == 0 {
res[idx] = i
res[idx+i] = i
vis[i] = true
// 找到了答案，一路往上返回
if dfs(res, vis, idx+1) {
return true
}
// 放置的数字没能得到答案，撤销放置，继续循环
vis[i] = false
res[idx] = 0
res[idx+i] = 0
}
}
// 特殊的1，只能放一个
if !vis[1] {
res[idx] = 1
vis[1] = true
if dfs(res, vis, idx+1) {
return true
}
vis[1] = false
res[idx] = 0
}
// 前面的选择有问题，回去撤销一下
return false
}
dfs(res, vis, 0)
return res
}
golang 解法, 执行用时: 4 ms, 内存消耗: 1.9 MB, 提交时间: 2023-05-29 17:49:43
func constructDistancedSequence(n int) []int {
res := make([]int, 2*n-1)
dfs(n, 0, res, map[int]int{})
return res
}
func dfs(n int, index int, res []int, set map[int]int) bool {
if index >= len(res) {
return true
}
if res[index] != 0{
return dfs(n, index+1, res,set)
}
for i := n; i >= 1; i-- {
_, ok := set[i]
if ok|| (i!=1&&index+i>=len(res))|| (i!=1&&res[index+i] != 0) {
continue
}
res[index] = i
if i!=1 {
res[index+i] = i
}
set[i]=1
if dfs(n, index+1, res, set) {
return true
}
delete(set, i)
res[index] = 0
if i!=1 {
res[index+i] = 0
}
}
return false
}
java 解法, 执行用时: 0 ms, 内存消耗: 38.9 MB, 提交时间: 2023-05-29 17:49:03
class Solution {
int len;
boolean flag = false;
boolean[] vis;
public int[] constructDistancedSequence(int n) {
//总长度为2n = 1
this.len = 2 * n - 1;
this.vis = new boolean[n + 1];
int[] ans = new int[len];
Arrays.fill(ans, -1);
//传入结果数组，当前索引，当前计数，最大值，四个参数进行回溯
dfs(ans, 0, 0, n);
return ans;
}
void dfs(int[] ans, int cur, int count, int n){
if(cur == len){
if(count == len)
flag = true;
return;
}
if(ans[cur] != -1){
dfs(ans, cur + 1, count, n);
return;
}
for(int i = n; i >= 1; i--){
if(!vis[i]){
//当前可以匹配的序列b超出数组长度范围
if(i != 1 && cur + i >= len) return;
if(i == 1 || ans[cur + i] == -1){
vis[i] = true;
if(i != 1) ans[cur + i] = i;
//i = 1，总数 + 1，其他 +2，
int x = (i == 1 ? 1 : 2);
ans[cur] = i;
dfs(ans, cur + 1, count + x, n);
if(flag) return;
ans[cur] = -1;
if(i != 1) ans[cur + i] = -1;
vis[i] = false;
}
}
}
}
}
python3 解法, 执行用时: 52 ms, 内存消耗: 15.9 MB, 提交时间: 2023-05-29 17:47:56
class Solution:
def constructDistancedSequence(self, n: int) -> List[int]:
res = [-1] * (2 * n - 1)
def bt(cur: int) -> bool:
if cur == 2 * n - 1:
return True
# 这个位置之前已经放过了
if res[cur] != -1:
return bt(cur + 1)
# 字典序最大的序列:优先看大的
for num in range(n, 0, -1):
if num not in res:
gap = num if num > 1 else 0
# 可以填
if cur + gap < 2 * n - 1 and res[cur] == res[cur + gap] == -1:
res[cur] = res[cur + gap] = num
if bt(cur + 1):
return True
res[cur] = res[cur + gap] = -1
return False
bt(0)
return res