[LeetCode] 374. Guess Number Higher or Lower

轉自LeetCode

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 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!

Example:

n = 10, I pick 6.

Return 6.

<Solution>

典型的 binary search 的題目

code 如下

C++

	// 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 start = 1, end = n;
	int mid;
	while(start < end) {
	mid = start + (end - start) / 2;
	if(!guess(mid)) {
	return mid;
	}
	else if(guess(mid) == 1) {
	start = mid + 1;
	}
	else {
	end = mid;
	}
	}
	return start;
	}
	};

view raw guessNumber.cpp hosted with ❤ by GitHub

kotlin

	/**
	* The API guess is defined in the parent class.
	* @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
	* fun guess(num:Int):Int {}
	*/
	class Solution:GuessGame() {
	override fun guessNumber(n:Int):Int {
	var left = 1
	var right = n
	while(left < right) {
	val mid = left + (right - left) / 2
	when {
	guess(mid) == 0 -> return mid
	guess(mid) > 0 -> left = mid+1
	else -> right = mid
	}
	}
	return right
	}
	}

view raw guess_number_higher_or_lower.kt hosted with ❤ by GitHub