Perfect Square

367. Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16 Returns: True Example 2:

Input: 14 Returns: False

三种解法

(1)二分法

class Solution {
public:
    bool isPerfectSquare(int num) {
        if(num < 1) return false;

        //此处上界和下界均定义成long型，防止int产生的溢出
        long lb = 1, ub = num/2 + 1;

        while(lb <= ub){
            long mid = (ub - lb) /2 + lb;

            if(mid * mid == num)
                return true;
            else if(mid * mid < num)
                lb = mid + 1;
            else
                ub = mid - 1;
        }
        return false;
    }
};

(2)牛顿法

class Solution {
public:
    bool isPerfectSquare(int num) {
        if(num < 1) return false;
        long t = num /2 +1;

        while(t * t > num)
            t = (t + num/t)/2;

        return t*t == num;
    }
};

(3)数学方法，根据数学结论

$$ n^2 = 1 + 3 + 5 +...+(2n-1)

$$

class Solution {
public:
    bool isPerfectSquare(int num) {
        int i = 1;

        while(num > 0){
            num -= i;
            i += 2;
        }
        return num == 0;
    }
};

279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

两种解法，动态规划和BFS (1)动态规划 状态转移公式

$$dp[i] = dp[i - jj] + 1 (jj < n)$$

int numSquares(int n){
  int *dp = new int[n+1];

  fill(dp, dp + n + 1, INT_MAX);
  dp[0] = 0;

  for(int i = 1; i * i < n; i++)
    dp[i*i] = 1;

  for(int i = 1; i < n + 1; ++i)
    for(int j = 1; j*j <= i; j++)
      dp[i] = min(dp[i - j*j] + 1, dp[i]);

  return dp[n];
}

(2)BFS的方法

class Solution {
public:
    int numSquares(int n) {
        if(n <= 0)  return 0;

        vector<int> perfectSquares;
        vector<int> cntPerfectSquares(n + 1);

        for(int i = 1; i * i <= n; i++){
            perfectSquares.push_back(i*i);
            cntPerfectSquares[i*i] = 1;
        }

        if(perfectSquares.back() == n)
            return 1;

        queue<int> searchQ;
        for(auto i:perfectSquares)
            searchQ.push(i);

        int curNum = 1;
        while(!searchQ.empty()){
            curNum++;
            int queSize = searchQ.size();
            //逐层遍历
            for(int i = 0; i < queSize; i++){
                int tmp = searchQ.front();
                for(auto j:perfectSquares){
                    if(tmp + j == n)
                        return curNum;
                    else if(tmp + j < n && cntPerfectSquares[tmp+j] == 0){
                        cntPerfectSquares[tmp+j] = curNum;
                        searchQ.push(tmp+j);
                    }else if(tmp + j > n)
                        break;
                }
                searchQ.pop();
            }
        }
        return 0;
    }
};

(3)数学的方法

class Solution {
public:
    int numSquares(int n) {
        while (n % 4 == 0) n /= 4;
        if (n % 8 == 7) return 4;
        //为1和2的情况
        for (int a = 0; a * a <= n; ++a) {
            int b = sqrt(n - a * a);
            if (a * a + b * b == n) {
                return !!a + !!b;
            }
        }
        return 3;
    }
};