Python程序构建字典序最大的有效序列

假设我们有一个数字n，我们必须找到一个满足以下所有规则的序列：

  • 1在序列中出现一次。

  • 2到n之间的每个数字在序列中出现两次。

  • 对于2到n范围内的每个i，i的两次出现之间的距离正好是i。

序列上两个数字a[i]和a[j]之间的距离是|j - i|。我们必须找到字典序最大的序列。

因此，如果输入是n = 4，则输出将是[4, 2, 3, 2, 4, 3, 1]

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数`backtrack()`。这将接受`elems`，`res`，`start := 0`作为参数。
  • 如果`elems`的大小小于等于0，则
    • 返回True
  • 如果`start`大于等于`res`的大小，则
    • 返回False
  • 如果`res[start]`与-1不同，则
    • 返回`backtrack(elems, res, start + 1)`
  • 对于0到`elems`大小减1的范围内的i，执行以下操作：
    • `num := elems[i]`
    • 如果`num`等于1，则`dist := 0`，否则`dist := num`
    • 如果`(start + dist)`小于`res`的大小并且`res[start + dist]`等于-1，则
      • `res[start] := num`
      • `res[start + dist] := num`
      • 从`elems`中删除第i个元素
      • 如果`backtrack(elems, res, start)`返回False，则
        • `res[start] := -1`
        • `res[start + dist] := -1`
        • 在位置i将`num`插入到`elems`中
        • 进入下一个迭代
      • 否则，
        • 返回True
  • 从主方法中执行以下操作：
  • `elems :=` 一个包含从n到1的n个元素的列表
  • `res :=` 一个大小为n*2-1的列表，并用-1填充
  • `backtrack(elems, res)`
  • 返回`res`

示例

让我们看看下面的实现，以便更好地理解：

def backtrack(elems, res, start = 0):
   if len(elems) <= 0:
      return True

   if start >= len(res):
      return False

   if res[start] != -1:
      return backtrack(elems, res, start + 1)

   for i in range(len(elems)):
      num = elems[i]
      dist = 0 if num == 1 else num

      if (start + dist) < len(res) and res[start + dist] == -1:
         res[start] = num
         res[start + dist] = num
         elems.pop(i)

         if not backtrack(elems, res, start):
            res[start] = -1
            res[start + dist] = -1
            elems.insert(i, num)
            continue
         else:
            return True
def solve(n):
   elems = [ i for i in range(n,0,-1)]
   res = [ -1 for i in range(n*2 - 1)]
   backtrack(elems, res)
   return res

n = 4
print(solve(n))

输入

4

输出

[4, 2, 3, 2, 4, 3, 1]

更新于：2021年10月6日

238 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告