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

时间上好像没差太多，半斤八两。