第367题---Valid Perfect Square

• 题意描述
  • 给定一个数，判断它是不是完美的平方数
• 思路一
  • 暴力破解，直接从1–INT_MAX遍历，平方，判断
  • 暴力优化，遍历1—INT_MAX/2之间的数
• 思路二
  • 二分的思想，取中间数，判断平方，如果相等返回true；大于返回end = mid;小于设置 start = mid+1（判断mid的平法，整数溢出的判断，long）（也可以判断num/mid 和mid之间的比较）

• 代码

  class Solution {
  public:
      bool isPerfectSquare(int num) {
          if(num == 1)
              return true;
          int start = 1;
          int end = num;
          while(start < end) {
              // why mid is int type will error, and mid is long type will correct.
              // maybe int * int will beyond the int type wide
              long mid = start + (end - start) / 2;
              if(mid * mid < num)
                  start = mid + 1;
              else if(mid * mid > num)
                  end = mid;
              else 
                  return true;
          }
          return start * start == num;
      }
  };

• 思路三

  • 完美平方数的性质，1 = 1 2 2 = 1+ 3 n n = 1 + 3 + … +(2n-1)
• 代码

  class Solution {
  public:
      bool isPerfectSquare(int num) {
          int n = 1;
          while(num > 0) {
              num -= n;
              n += 2;
          }
          return num == 0;
      }
  };