Question

1718. 构建字典序最大的可行序列

English Version

题目描述

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