367. Valid Perfect Square

Q:

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

A:

********** 在所有的可能的平方根里，进行二分查找**********

class Solution {
public:
    bool isPerfectSquare(int num) {
        if(num == 1)
            return true;
        int low = 2, up = num/2+1;
        while(low < up)
        {
            long mid = low + (up - low) /2;
            if(mid * mid == num)
                return true;
            if (mid * mid > num)
            {
                up = mid;
            }else{
                low = mid+1;
            }
        }
        return false;
    }
};

Mistakes:

if we declare:

int mid; 

mid * mid   would be an int,  but can overflow, thus need long.

315. Count of Smaller Numbers After Self

Q:

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

A:
*********首先意识到，这就是数组的插入排序啊。  n* log(n)  应该是足够快了
****嗯，就是找到需要插入的位置，再返回这个位置就可以了。********
******可是，反过来想，如果是数组的话，需要每次挪动啊。******？？？？

******sol： 不需要真的插入，只需要记录其后面有多少个就行。然后，记录其前面的。 不对，这样，还是需要记录进去，否则怎么查呢？ *******


Sol 2： 先排序，



Mistakes: