题解 | #求平方根#

求平方根，向下取整 其实方法mysqrta已经可以求出平方根了，min为1，max为x 不过由于我小时候我爸教过我怎么笔算平方根，所以这里写一下，大概是根据a^2=b^2+2bc+c^2计算。 因为没有办法直接得出x = a^2，所以，先算b。 比如说 1234 先得出 300^2 < 123456 < 400^2,所以用1234-300^2，再计算十位数，最后计算个位数。 mysqrta计算的是结果高位第一个的值，循环次数是由1-3二分，或者4-9二分查找。 mysqrtb计算的是c的值，是在x-b^2 > 2b^c+c^2 成立的基础上的c最大值 算法复杂度为log以100为底，x为真数，再乘以log以2为底10为真数，即 log(100,x)log(2,10)=log(2,x)/2 算法复杂度减半了

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param x int整型 
# @return int整型
#
class Solution:

        # write code here
        @staticmethod
        def mysqrta(min,max,x):
            middle = int((max + min)/2)
            while (max > min):
                if middle*middle < x:
                    min = middle + 1
                elif middle*middle > x:
                    max = middle - 1
                else:
                    break
                middle = int((max + min) / 2)
            if(middle * middle > x):
                return (middle-1)
            else:
                return middle
        @staticmethod
        def mysqrtb(min,max,num,result):
            middle = int((max + min)/2)
            while (max > min):
                if num > (result * 10 * 2 + middle)*middle:
                    min = middle + 1
                elif num < (result * 10 * 2 + middle)*middle:
                    max = middle - 1
                else:
                    break
                middle = int((max + min) / 2)
            if (result * 10 * 2 + middle)*middle > num:
                return (middle-1)
            else:
                return middle
            
        def mysqrt(self , x: int) -> int:
            char_x = str(x)
            start_i = 0
            result = 0
            p_result = 0
            if(len(char_x)%2==0):
                num = int(char_x[0])*10+int(char_x[1])
                start_i += 2
                result = self.mysqrta(4,9,num)
            else:
                num = int(char_x[0])
                start_i += 1
                result = self.mysqrta(1,3,num)

            p_result = result * result

            for i in range(start_i,len(char_x),2):
                num = (num - p_result)*100+int(char_x[i])*10+int(char_x[i+1])
                max = int(num/(result*20))
                min = int(num/(result*20+10))
                if max <= (min+1):
                    d = min
                else:
                    d = self.mysqrtb(min,max,num,result)
                p_result = (result * 10 * 2 + d)*d
                result = result * 10 + d
            return result