算法练习 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.