題目
Leetcode 1888. Minimum Number of Flips to Make the Binary String Alternating
給定一個字串 s ，由 0 跟 1 組成，可以有兩種操作
- Type-1: 移除第一個字元放到最後
- Type-2: 翻轉 s 中的任一字元，例如，如果是 0 變成 1
運用這兩種操作能讓 s 變成 alternating，如 010101… or 1010101… ，必須返回操作 type-2 最少的次數
Input: s = "111000" Output: 2 Explanation: Use the first operation two times to make s = "100011". Then, use the second operation on the third and sixth elements to make s = "101010".
思路
Type-2 可以想成算從 1 開始跟從 0 開始，如 010101… or 1010101… 分別要翻轉的次數
用 Swift 實作 Code 如下
func calMinUseType2(_ s:[Character]) -> Int {
let arr = Array(s)
if arr.count == 0 { return 0 }
var count1 = 0
var count2 = 0
for index in 0..<arr.count {
let charNum = Int(String(arr[index]))
if index % 2 == 0 {
if charNum == 1 {
count1 += 1
}
if charNum == 0 {
count2 += 1
}
} else {
if charNum == 0 {
count1 += 1
}
if charNum == 1 {
count2 += 1
}
}
}
return min(count1, count2)
}再加上 Type-1 操作後
class Solution {
func calMinUseType2(_ s:[Character]) -> Int {
let arr = Array(s)
if arr.count == 0 { return 0 }
var count1 = 0
var count2 = 0
for index in 0..<arr.count {
let charNum = Int(String(arr[index]))
if index % 2 == 0 {
if charNum == 1 {
count1 += 1
}
if charNum == 0 {
count2 += 1
}
} else {
if charNum == 0 {
count1 += 1
}
if charNum == 1 {
count2 += 1
}
}
}
return min(count1, count2)
}
func minFlips(_ s: String) -> Int {
var results = [Int]()
var nums = Array(s)
for _ in 0..<s.count {
let first = nums.removeFirst()
nums = Array(String(nums) + String(first))
let count = calMinUseType2(nums)
results.append(count)
}
return results.min()!
}
}
果不其然會 Time Limit Exceeded…
調整一下 traverse 的方式，用 s + s 然後 slide range
class Solution {
func minFlips(_ s: String) -> Int {
var counter1 = 0 // squeunce start with 0 (0,1,0,1..)
var counter2 = 0 // squeunce start with 1 (1,0,1,0...)
var minCounter = Int.max
var n = s.count
for (index, val) in (s + s).enumerated() {
if(val != (index % 2 == 0 ? "0" : "1")) {
counter1 += 1
}
if(val != (index % 2 == 0 ? "1" : "0")) {
counter2 += 1
}
if(index >= n) {
if(val != ((index - n) % 2 == 0 ? "0" : "1")) {
counter1 -= 1
}
if(val != ((index - n) % 2 == 0 ? "1" : "0")) {
counter2 -= 1
}
}
if(index >= n) {
minCounter = min(minCounter, min(counter1, counter2))
}
}
return minCounter
}
}時間複雜度: O(n)
空間複雜度: O(1)
