Skip to content

leet code

950 - sqrt

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int mySqrt(int x) {
        if(x<=1) return x;

        long left = 1;
        long right = x/2;
        long target = 0;
        long mid = 0;

        while(left <= right)
        {
            mid = left + (right-left)/2;
            target = mid*mid;

            if(target == x)
            {
                return mid;
            }else if(target > x)
            {
                right = mid-1;
            }else
            {
                left = mid+1;
            }
        }
        return right;
    }
};

951 - Guess Number Higher Or Lower

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return         -1 if num is lower than the guess number
 *                  1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

class Solution {
public:
    int guessNumber(int n) {
        if(guess(n)==0) return n;

        int left = 1;
        int right = n;
        int mid = 0;
        int g = 0;

        while(left<=right)
        {
            mid = left + (right - left)/2;
            printf("mid: %d\n", mid);
            g = guess(mid);
            if(g == 0) return mid;
            else if(g < 0 )
            {
                right = mid-1;
            }else
            {
                left = mid+1;
            }
        }
        return left;
    }
};