[Leetcode]374. Guess Number Higher or Lower
https://leetcode.com/problems/guess-number-higher-or-lower/description/
先二分搜索试试看。这个二分跟普通的二分就一点不一样,不是让你二分search 而是二分看是什么数,换汤不换药,以前是已知数让你看在不在,现在是他告诉你大小,你自己缩小范围,信息点给的是一样的,guess(int num)这个函数来指示大了还是小了,我们好挪动范围。这道题最神奇的地方在于,题目对-1, 和1这个返回值 的理解。我一开始就理解反了,真么着都不对,心塞塞,后来调过来就好了,呵呵。还有一个不能饶恕的错误,第一次提交竟然因为没检查low 比 high小 而Stack Overflow 了!不能再犯!
但是感觉狗家给这个题不是很正常,边界条件要问好,估计这才是重点。
AC Solution, Recursion:
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.看着就是二分搜索,但是每太看懂他的意思,他的guess function用来干啥的呢。
先二分搜索试试看。这个二分跟普通的二分就一点不一样,不是让你二分search 而是二分看是什么数,换汤不换药,以前是已知数让你看在不在,现在是他告诉你大小,你自己缩小范围,信息点给的是一样的,guess(int num)这个函数来指示大了还是小了,我们好挪动范围。这道题最神奇的地方在于,题目对-1, 和1这个返回值 的理解。我一开始就理解反了,真么着都不对,心塞塞,后来调过来就好了,呵呵。还有一个不能饶恕的错误,第一次提交竟然因为没检查low 比 high小 而Stack Overflow 了!不能再犯!
但是感觉狗家给这个题不是很正常,边界条件要问好,估计这才是重点。
AC Solution, Recursion:
public class Solution extends GuessGame {
int result = 0; public int guessNumber(int n) { return helper(1, n); } public int helper(int low, int high){ if(low >= high){ return low; } int mid = low + (high - low) / 2; if(guess(mid) == 0){ return mid; } else if(guess(mid) == 1){ return helper(mid+1, high); } else{ return helper(low, mid-1); } } }AC Solution, Iteration:
public class Solution extends GuessGame { public int guessNumber(int n) { int low = 1; int high = n; while(low <= high){ int mid = low + (high - low)/2; if(guess(mid) == 0){ return mid; } if(guess(mid) == 1){ low = mid + 1; } else { high = mid -1; } } return -1; } }
Comments
Post a Comment