第一题 x的平方根

题目

二分查找

对于算术平方根的计算，我们可以使用二分查找不断缩小边界，最终找到其算术平方根

具体代码

func mySqrt(x int) int {
    l, r := 0, x
    ans := -1
    for l <= r {
        mid :=  (r + l) / 2
        if mid * mid <= x {
            ans = mid
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return ans
}

效果如下

牛顿迭代法

代码

func mySqrt(x int) int {
    if x == 0 {
        return 0
    }
    C, x0 := float64(x), float64(x)
    for {
        xi := 0.5 * (x0 + C/x0)
        if math.Abs(x0 - xi) < 1e-7 {
            break
        }
        x0 = xi
    }
    return int(x0)
}

复杂度分析

时间复杂度：O(logx)。

空间复杂度：O(1)。

第二题 两数相除

题目

思路

官解的思路较为复杂

仅供参考

对于除法
可以用更朴素的减法思维来计算
借鉴快速幂和快速乘的思想
我们从2的n次幂找起
每次找到刚好比被除数小的除数*2^n
并在结果中加入2^n

代码如下

func divide(dividend int, divisor int) int{
    if dividend == math.MinInt32 { // 考虑被除数为最小值的情况
        if divisor == 1 {
            return math.MinInt32
        }
        if divisor == -1 {
            return math.MaxInt32
        }
    }
    if divisor == math.MinInt32 { // 考虑除数为最小值的情况
        if dividend == math.MinInt32 {
            return 1
        }
        return 0
    }
    if dividend == 0 { // 考虑被除数为 0 的情况
        return 0
    }
    a := dividend
    b := divisor
    sign := 1
    if (a>0&&b<0) || (a<0&&b>0) {
        sign = -1
    }
    if a<0 {a=-a}
    if b<0 {b=-b}
    res := div(a,b)
    if sign>0{return res}else{
        return -res
    }
}
func div( a int,  b int)int {
    if a < b {
        return 0
    }
    count :=1

    tb := b // 在后面的代码中不更新b
    for (tb + tb) <= a {
        count = count + count // 最小解翻倍
        tb = tb + tb         // 当前测试的值也翻倍
    }
    return count + div(a-tb, b)
}

溢出处理可以参考官解

用减法完成除法的思想详细可以了解组成原理中定点数的除法运算

复杂度分析

时间复杂度：O(logn)。其中n为商的大小

空间复杂度：O(logn)。div中递归调用栈的最大深度为logn