Sunday, June 26, 2016

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.





Monday, June 20, 2016

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: