資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢使二進位制字串交替所需的最小翻轉次數
假設我們有一個二進位制字串s。現在假設我們可以取s的某個字首並將其移到後面，然後找到需要翻轉的最小字元數，這樣就不會出現相同值的連續字元。
因此，如果輸入類似於s = "10010101111"，則輸出將為2，因為我們可以取字首"10"，然後將其移到後面，所以字串變為"01010111110"，然後將從右數的第3位和第5位翻轉為0 ("01010101010")。
為了解決這個問題，我們將遵循以下步驟：
ans := S的長度
N := S的長度
s := 0
對於 i 從 0 到 2 * N，執行：
s := s + int(S[i mod N] XOR (i AND 1))
如果 i >= N - 1，則：
ans := min(ans, s, N - s)
s := s - int(S[(i -(N - 1)) mod N] XOR ((i - (N - 1)) AND 1))
返回 ans
示例
讓我們看看下面的實現，以便更好地理解：
class Solution: def solve(self, S): ans = N = len(S) s = 0 for i in range(2 * N): s += int(S[i % N]) ^ (i & 1) if i >= N - 1: ans = min(ans, s, N - s) s -= int(S[(i - (N - 1)) % N]) ^ ((i - (N - 1)) & 1) return ans ob = Solution() s = "10010101111" print(ob.solve(s))
輸入
"10010101111"
輸出
2
更新於：2020年12月22日
瀏覽量：353
廣告