插： 前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。
坚持不懈，越努力越幸运，大家一起学习鸭~~~

题目：

给你一个整数 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

java代码：

class Solution {int[] ans;// 标记是否找到一个解了boolean flag = false;public int[] constructDistancedSequence(int n) {// 除了1出现1次，2到n出现两次，那么返回数组的长度为2n-1ans = new int[2 * n - 1];// 和ans等长，用于记录当前遍历的一个序列int[] arr = new int[2 * n - 1];// 初始为-1，表示这个位置没有被用过Arrays.fill(arr, -1);// 记录1到n各自是否已经填好了boolean[] visited = new boolean[n + 1];// 第二个参数0表示先填第一位，优先使用大数填dfs(n, 0, arr, visited);// 注意最后不能返回arr，arr元素最后都会被重置为-1，所以要多创建一个ans变量return ans;}// 当前在填arr[index]private void dfs(int n, int index, int[] arr, boolean[] visited) {// 找到一个解了，就不再递归，因为按我们的思路，第一个解一定是字典序最大的// 注意，这里flag是必须的，不然会遍历完所有状态，ans就是字典序最小的了if (flag) {return;}// arr所有位置都填好了if (index == 2 * n - 1) {flag = true;// 将arr复制到ans，更新ansSystem.arraycopy(arr, 0, ans, 0, 2 * n - 1);return;}// 当前位置index已经填好了，那么就看下一位置if (arr[index] != -1) {dfs(n, index + 1, arr, visited);return;}// 当前位置index还没填，从n开始递减地看能不能填for (int i = n; i >= 1; i--) {// i已经用过了，继续看i-1if (visited[i]) {continue;}// 到这里表示i没用过，分情况讨论i是不是1if (i == 1) {// 如果i是1，只需要将arr[index]赋值为i(即1)arr[index] = 1;visited[i] = true;dfs(n, index + 1, arr, visited);arr[index] = -1;visited[i] = false;} else {// 如果i不是1，需要将arr[index+i]也赋值为i// 当然，如果这里arr[index + i] == -1不成立的话，说明i还是不能放在这里，需要继续循环看i-1if (index + i < 2 * n - 1 && arr[index + i] == -1) {// 到了这里说明i可以放在index和index+i处arr[index] = i;arr[index + i] = i;// 标记i已经填好了visited[i] = true;// 递归dfs(n, index + 1, arr, visited);// 状态重置arr[index] = -1;arr[index + i] = -1;visited[i] = false;}}}}
}