leetcode 367 有效的完全平方数

思考

之前看代码随想录的训练营发现他们每天做题老师都会要求在csdn上写博客作为一个思考的成果或者说记录一下，遂以为这样干应该对刷题有很大的帮助，但是一直没有下决心去写，一是自身的懒惰在作祟，二是自身内心觉得写代码题解没什么太大的作用，但既然别人都写，私以为可以尝试一下， 于是在某天早上顶着巨大的内心挣扎写下这篇题解，也尝了自己一大心愿，虽然这是me不想干的事情。

leetcode 367 有效的完全平方数

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

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

thinks

这道题目是看答案然后才写的，正常来说直接使用暴力解法就可以，但是我暴力解法思路知道，可是一旦动键盘，就开始踉踉跄跄，哎，还是写的代码太少了

暴力解法：从1开始，慢慢增大然后相乘用一个变量保存，判断是不是=题目要求的数值，若等于则返回true，若不等于则继续下一次遍历，需要注意的是循环要求要求x*x<=num,这样才有意义

class Solution {
public:
    bool isPerfectSquare(int num) {
        long x=1,square=1;
        while(square<=num){
            if(square==num){
                return true;
            }
            x++;
            square=x*x;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

二分法：二分法其实有一套模板，定义左右区间，然后在左区间小于等于右区间的循环中来判断中间变量与要比较值的差异，若小于，则left=mid+1,若大于 right=mid-1,有个注意的点是左闭右闭还有左闭右开对left和right的影响，左闭右闭right=mid-1，左闭右开right=mid

class Solution {
public:
    bool isPerfectSquare(int num) {
        int l=0,r=num;
        while(r>=l){
            int mid=l+(r-l)/2;
            if((long long)mid*mid>num){
                r=mid-1;
            }else if((long long)mid*mid<num){
                l=mid+1;
            }else{
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17