Python程式：查詢應用操作後的字典序最小字串

假設我們有一個只包含數字字元的字串 s，以及兩個值 a 和 b。我們可以對 s 應用以下兩種操作中的任意一種，任意次數，並且可以按任意順序進行：

  • 將 'a' 加到 s 的所有奇數位置的項 (從 0 開始索引)。如果數字是 9，則新增任何值後會迴圈回 0。

  • 將 's' 向右旋轉 b 個位置。

因此，我們必須找到透過對 s 應用上述操作任意多次可以獲得的字典序最小字串。

例如，如果輸入為 s = "5323" a = 9 b = 2，則輸出為 2050，因為如果我們按照以下步驟：

  • 旋轉："5323"
  • 新增："5222"
  • 新增："5121"
  • 旋轉："2151"
  • 新增："2050"

為了解決這個問題，我們將遵循以下步驟：

  • seen := 一個新的集合
  • deq := 一個新的佇列，其中包含一個元素 's'
  • 當 deq 不為空時，執行以下操作：
    • curr := 從 deq 中刪除的第一個元素
    • 將 curr 插入 seen 集合
    • ad := 對 curr 執行給定的加法操作
    • 如果 ad 不在 seen 中，則
      • 將 ad 插入 deq 的末尾
      • 將 ad 插入 seen 集合
    • ro := 對 curr 執行旋轉操作
    • 如果 ro 不在 seen 中，則
      • 將 ro 插入 deq 的末尾
      • 將 ro 插入 seen 集合
  • 返回 seen 的最小值

示例

讓我們看看下面的實現，以便更好地理解：

from collections import deque
def add_(s,a):
   res = ''
   for idx, i in enumerate(s):
      if idx % 2 == 1:
         num = (int(i) + a) % 10
         res += str(num)
      else:
         res += i

   return res

def rotate_(s, b):
   idx = len(s)-b
   res = s[idx:] + s[0:idx]
   return res

def solve(s, a, b):
   seen = set()
   deq = deque([s])

   while deq:
      curr = deq.popleft()
      seen.add(curr)

      ad = add_(curr, a)
      if ad not in seen:
         deq.append(ad)
         seen.add(ad)

      ro = rotate_(curr, b)
      if ro not in seen:
         deq.append(ro)
         seen.add(ro)

   return min(seen)

s = "5323"
a = 9
b = 2
print(solve(s, a, b))

輸入

"5323", 9, 2

輸出

2050

更新於：2021年10月5日

瀏覽量：227

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告