Python程式：查詢合併後剩餘的最少顏色數

假設我們有一個顏色列表（R、G、B）。如果兩種不同的顏色彼此相鄰，則它們可以轉換為第三種顏色的單個顏色項。我們必須找到在任何可能的轉換序列之後剩餘的最少顏色數。

因此，如果輸入類似於 colors = ["G", "R", "G", "B", "R"]，則輸出將為 1，因為它可以像下面這樣轉換：

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

  • n := colors 的大小
  • 如果 colors 只有唯一的一種顏色，則
    • 返回 n
  • 如果 n <= 1，則
    • 返回 n
  • x := 0
  • d := 一個鍵值對對映 {("R", 1), ("G", 2), ("B", 3)}
  • 對於 colors 中的每個 c，執行
    • x := x XOR d[c]
  • 如果 x 等於 0，則返回 2，否則返回 1

示例（Python）

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

 線上演示

class Solution:
   def solve(self, colors):
      n = len(colors)
      if len(set(colors)) == 1:
         return n
      if n <= 1:
         return n
      x = 0
      d = {"R": 1, "G": 2, "B": 3}
      for qux in colors:
         x ^= d[qux]
      return 2 if x == 0 else 1   
ob = Solution()
colors = ["G", "R", "G", "B", "R"]
print(ob.solve(colors))

輸入

["G", "R", "G", "B", "R"]

輸出

1

更新於: 2020年12月12日

144 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告