Python程式：查詢使字串排序所需的最小操作次數

假設我們有一個字串s。我們必須對s執行以下操作，直到得到一個排序的字串：

  • 選擇最大的索引i，使得1 <= i < s的長度，並且s[i] < s[i - 1]。

  • 選擇最大的索引j，使得i <= j < s的長度，並且對於範圍[i, j]（包括i和j）內的所有可能的k值，都有s[k] < s[i - 1]。

  • 交換索引i - 1和j處的兩個字元。

  • 反轉從索引i開始的字尾。

我們必須找到使字串排序所需的操作次數。答案可能非常大，因此返回結果模10^9 + 7。

因此，如果輸入類似於s = "ppqpp"，則輸出將為2，因為

  • 在第一次操作中，i=3，j=4。交換s[2]和s[4]以獲得s="ppppq"，然後反轉從索引3開始的子字串。現在，s="pppqp"。

  • 在第二次操作中，i=4，j=4。交換s[3]和s[4]以獲得s="ppppq"，然後反轉從索引4開始的子字串。現在，s = "ppppq"。

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

  • d := 一個大小為26的陣列，並用0填充

  • a := 0，t := 1

  • m := 10^9 + 7

  • n := 'a'的ASCII碼

  • 對於s中每個索引i和字元c的反向順序，從索引1開始，執行以下操作：

    • j := c的ASCII碼 - n

    • d[j] := d[j] + 1

    • a :=(a + d[從索引0到j-1]的所有元素的總和) * (t/d[j]的商) mod m

    • t := t * (i/d[j]的商)

  • 返回a

示例

讓我們看看以下實現以獲得更好的理解

def solve(s):
   d = [0]*26
   a = 0
   t = 1
   m = 10**9 + 7
   n = ord('a')
   for i,c in enumerate(s[::-1],1):
      j = ord(c) - n
      d[j] += 1
      a = (a+sum(d[:j])*t//d[j]) % m
      t = t*i//d[j]
   return a

s = "ppqpp"
print(solve(s))

輸入

"ppqpp"

輸出

2

更新於: 2021年10月8日

223 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告