#LeetCode:278. First Bad Version

灆洢 2020-05-02 11:28:06

此題要找出版本序列中第一個壞版本是哪一個版本。

直接使用循序搜尋會超過時間,故此題必須使用二分搜尋法來找。要注意的一個重點是,當要透過上下限來切一半的時候,不可以直接使用 (upper + lower) / 2,因為 upper + lower 有機會會超過 32 位元整數的上限,故要使用下限當作基底,往上加差距的一半的方法:lower + (upper - lower) / 2

Kotlin(224ms)

/*******************************************************
 * LeetCode 278. First Bad Version                     *
 * Author: Maplewing [at] knightzone.studio            *
 * Version: 2020/05/02                                 *
 *******************************************************/
/* The isBadVersion API is defined in the parent class VersionControl.
       def isBadVersion(version: Int): Boolean = {} */
class Solution: VersionControl() {    
    override fun firstBadVersion(n: Int) : Int {
        var lowerBound = 1
        var upperBound = n

        while (lowerBound <= upperBound) {
            val currentValue = lowerBound + (upperBound - lowerBound) / 2
            val isCurrentBadVersion = isBadVersion(currentValue)
            if (isCurrentBadVersion) {
                upperBound = currentValue - 1
            } else lowerBound = currentValue + 1
        }

        return lowerBound
    }
}

在〈“#LeetCode:278. First Bad Version”〉中有 2 則留言

  1. 小龜表示:

    可以用Python就沒有overflow的問題了 😛

    • 灆洢表示:

      蠻有道理的!XD 其實只要預設整數型態上限不要卡在 32 位元的限制的語言應該都可以!XD
      其實我剛開始也是將它轉成 64 位元去做,做完後才改的wwwwwww

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料