演算法練習 Leetcode 力扣 69. Sqrt(x) Python, Java, C++, Scala 解法

這題是經典演算法二分查找(binary search)的應用。做題之前先複習binary search的經典實現,注意幾個細節。但是和一般binary search不同,這題不是找一個特定的數,而是要找到一個整數正好是sqrt(x)的整數部分,而又不能直接求出sqrt(x)。我想了一下,可以表達成從[0, x]中找出一個整數,這個整數ans滿足ans^2 <= x,而同時(ans + 1)^2 > x

Python實現

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        l = 0
        h = x
        while l <= h:
            m = l + (h - l) / 2
            sq = m ** 2
            if sq <= x and (m + 1) ** 2 > x:
                return m
            elif sq > x:
                h = m - 1
            else:
                l = m + 1
        

Scala 實現1 使用while loop,思路比較像Java

import scala.util.control.Breaks._

object Solution {
    def mySqrt(x: Int): Int = {
        var l: Int = 0
        var h: Int = x
        while (l <= h) {
            val m : Int = l + (h - l) / 2
            val sq: Double = 1.0 * m * m 
            if (sq <= x && (m + 1.0) * (m + 1.0) > x) {    
                return m
            } else if (sq > x) {
                h = m - 1
            } else {
                l = m + 1
            }
        }
        -1
    }
}

和 Python 不一樣的是,Scala Int 平方後會溢出,而float精度不夠,必須用double才能過OJ。用Long(64位)也可以。

Scala 實現2 使用recursion代替while loop,平方用Long表示

object Solution {
    def mySqrt(x: Int): Int = {
        helper(x, 0, x)
    }
    
    def helper(x: Int, l: Int, h: Int): Int = {
        val m: Int = l + (h - l) / 2
        val sq: Long = m.asInstanceOf[Long] * m.asInstanceOf[Long]
        
        if (sq <= x && (m + 1).asInstanceOf[Long] * (m + 1).asInstanceOf[Long] > x) {
            m
        } else if (sq > x) {
            helper(x, l, m - 1)
        } else {
            helper(x, m + 1, h)
        }
    }
}

Scala 實現3 使用recursion代替while loop,平方用Double表示

import scala.util.control.Breaks._

object Solution {
    def mySqrt(x: Int): Int = {
        helper(x, 0, x)
    }
    
    def helper(x: Int, l: Int, h: Int): Int = {
        val m: Int = l + (h - l) / 2
        val sq: Double = 1.0 * m * m
        
        if (sq <= x && (m + 1.0) * (m + 1.0) > x) {
            m
        } else if (sq > x) {
            helper(x, l, m - 1)
        } else {
            helper(x, m + 1, h)
        }
    }
}

時間上好像沒差太多,半斤八兩。

Leave a Comment

Your email address will not be published.