文章目录

题目

一、解题思路

二、结果

1.注意点

2.C++代码

总结

---

题目

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如  sqrt 。

示例 1：

输入：num = 16
输出：true

示例 2：

输入：num = 14
输出：false

提示：

1 <= num <= 2^31 - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-perfect-square

一、解题思路

看到这个题想必大家很快的就是想到用库函数，或者用num=x*x去判断，或者二分查找的方法去解决；这里我介绍用牛顿迭代法去解决这一问题。

牛顿迭代法：一种近似求解方程（近似求解函数零点）的方法。其本质是借助泰勒级数，从初始值开始快速向函数零点逼近。

一句话解释牛顿法求根的意思就是：欲求方程f(x)=0的根，就是任意取出函数上一点（xn,f(xn)）在函数上的切线与x的交点作为下一个xn+1，然后再把（xn+1,f(xn+1)）这个点的切线与x的交点作为下一个xn+2，反复迭代下去，找到最接近的根的x。

我们构建方程y=f(x)=x2−num，求y=0的根，存在即是平方数。

导数f′(x)=2x，任意得到切线方程y−(xi2​−num)=2xi​(x−xi​)

切线于x轴的交点，就容易的到下一个迭代节点x的值

 

二、结果

1.注意点

• num是正整数，我们只需要考虑x正半轴的根。
• 记得要把x转为整型

2.C++代码

 代码如下（示例）：

class Solution {
public:
    bool isPerfectSquare(int num) {
        double x0 = num;
        while (true) {
            double x1 = (x0 + num / x0) / 2;//下一个迭代节点
            //差值小于一个很小的值，我们就认为其以及很接近了
            if (x0 - x1 < 1e-6) {
                break;
            }
            x0 = x1;
        }
        //要转为整型
        int x = (int) x0;
        return x * x == num;
    }
};

 

---

总结

虽然这道题很简单，可以很快想到简单的思路，但这里的用到了牛顿迭代法，挺牛的。。

坚持加油！！！！