[Leetcode 系列] 平方根 Sqrt(x) 的php解法

/ 0 评 / 阅读 33

平时开发从来都是拿来就用, 也没去想程序是怎么求平方根的。翻了一些文章,看到有人提到可以把给出的数(大于1)想象成一个1*(给的数)的长方形,要做的就是保证面积不变,缩短长边,延长短边,直到长边短边尽量相同。做leetcode果然增长见识。下面是代码:


class Solution {

    /**
     * @param Integer $x
     * @return Integer
     */
    function mySqrt($x) {
        if($x<=1){
            return $x;
        }

        $w=1; // 短边
        $l=$x; // 初始长边即给的数
        while (true){
            $l=($w+$l)/2; // 缩短长边。真实的平方根必定是介于长边和短边之间的某个数。
            $w=$x/$l; // 保证面积相同,求短边。
            $_l=floor($l);
            if($_l===floor($w)){ // 按照leetcode要求只要保证整数位正确就好。
                break;
            }
        }
        return $_l;
    }
}

当然,算法不一定最优,也就是提供一个思路。

发表评论

电子邮件地址不会被公开。 必填项已用*标注