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 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告