【算法题】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

java代码：

class Solution {
    int[] ans;
    // 标记是否找到一个解了
    boolean flag = false;
    public int[] constructDistancedSequence(int n) {
        // 除了1出现1次，2到n出现两次，那么返回数组的长度为2n-1
        ans = 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，更新ans
            System.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-1
            if (visited[i]) {
                continue;
            }
            // 到这里表示i没用过，分情况讨论i是不是1
            if (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-1
                if (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;
                }
            }
        }
    }
}

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73