[F 外商面試考題] Minimum Number of Flips to Make the Binary String Alternating

題目

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)

網頁瀏覽量: 1


尚未有留言,成為第一個留言的人吧!

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *