374. Guess Number Higher or Lower

  • 34.3%

https://leetcode.com/problems/guess-number-higher-or-lower/

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

1
2
3
4
> -1 : My number is lower
> 1 : My number is higher
> 0 : Congrats! You got it!
>
1
2
3
4
5
> Example:
> n = 10, I pick 6.
>
> Return 6.
>

java

solution 1:

1ms, , 16 July 2016

https://discuss.leetcode.com/topic/51034/short-java-code-using-binary-search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* The guess API is defined in the parent class GuessGame.
@param num, your guess
@return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num); */

public class Solution extends GuessGame {
public int guessNumber(int n) {
int i = 1, j = n;
while(i < j){
int mid = i + (j - i) / 2;
if(guess(mid) == 0)
return mid;
else if(guess(mid) == 1)
i = mid + 1;
else
j = mid;
}
return i;
}
}

cpp

solution 1:

0ms, , 16 July 2016

https://discuss.leetcode.com/topic/51184/0ms-c-binary-search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);

class Solution {
public:
int guessNumber(int n) {
int maxNumber = n, minNumber = 1;
while(true){
int meanNumber = (maxNumber - minNumber) / 2 + minNumber;
int res = guess(meanNumber);
if(res == 0)
return meanNumber;
else if(res == 1)
minNumber = meanNumber + 1;
else
maxNumber = meanNumber - 1;
}
}
};

python

solution 1:

48ms, , 16 July 2016

https://discuss.leetcode.com/topic/51082/2-lines-as-usual

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num):

class Solution(object):
def guessNumber(self, n):
"""
:type n: int
:rtype: int
"""
lo, hi = 1, n
while lo < hi:
mid = (lo + hi) / 2
if guess(mid) == 1:
lo = mid + 1
else:
hi = mid
return lo

solution 2:

60ms, , 16 July 2016

https://discuss.leetcode.com/topic/51082/2-lines-as-usual

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num):

class Solution(object):
def guessNumber(self, n):
"""
:type n: int
:rtype: int
"""
lo, hi = 1, n
while lo < hi:
mid = (lo + hi) / 2
lo, hi = ((mid, mid), (mid+1, hi), (lo, mid-1))[guess(mid)]
return lo
谢谢你,可爱的朋友。