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

feellikelearning March 23, 2020 0 Comments

這題是經典演算法二分查找（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)
        }
    }
}

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