一、前记(1/3)

最近有在认真的学习。最近把CISCN的报名弄完成了一下,这就标志着有可能是大学里最后一场网络安全竞赛就要来了。(爷青结😢)

二、题目描述

这道题我在看的时候就感觉奇奇怪怪。作为一个CRYPTO手,我一般要得到平方根的结果直接就是:import math,来进行各种数学运算。但是在这个里面应该是要学习一些算法吧。

三、解题思路

1、我的思路

方法一:调用math库

没啥说的,注意题目要求就行
参考代码

import math
class Solution:
    def mySqrt(self, x: int) -> int:
        return int(math.sqrt(x))

方法二:暴力破解

因为指数型增长还是比较吓人的,所以用循环的方法做题也是可以的,但是运算过程确实会心知肚明的慢。
参考代码:

class Solution:
    def mySqrt(self, x: int) -> int:
        i=1
        while i*i<=x:
            i+=1
        return i-1

2、别人的思路

OMG!看到别人的思路真的是厉害又完整,属实羡慕。

方法1:二分法。

其实这个方法俺也会,但是写起来有点复杂(就偷懒了😜)。核心思想就是,平方根的结果不会超过本身的数值。那么我们就可以得到一个数值范围:(0,x)。在这个数值范围里面,我们可以使用二分法进行查找。最终找到合适的数值。
参考代码:

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        left, right = 0, x + 1
        # [left, right)
        while left < right:
            mid = left + (right - left) // 2
            if mid ** 2 == x:
                return mid
            if mid ** 2 < x:
                left = mid + 1
            else:
                right = mid
        return left - 1

方法2:牛顿迭代法(new)

介绍的话就一句:牛顿迭代法是已知的实现求方根最快的方法之一。(又是一篇算法要总结,QAQ!!!)
原理
参考代码:

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        num = x
        while num * num > x:
            num = (num + x // num) // 2
        return num

四、学到了什么?

1、牛顿迭代法解决求方根的算法。

2、二分法和暴力破解的方法解决问题的思想。