解答
public class GuessGame { public int pick; public int guess(int num) { if (pick == num) { return 0; } return pick < num ? -1 : 1; } } public class Solution extends GuessGame { public int guessNumber(int n) { if (n == 1) { return 1; } int result = 0; int start = 1; int end = n; int value = 0; do { if (start == end) { value = start; } else { value = start / 2 + end / 2; } result = guess(value); switch (result) { case 0: break; case 1: start = value + 1; break; case -1: end = value - 1; break; } } while (result != 0); return value; } }
要点
求解过程中,需要注意做加法时可能出现的溢出现象。
使用如下代码来求解value
,可以有效的规避溢出现象。
value = begin +(end - begin)/2;
准备的用例,如下
@Before public void before() { t = new Solution(); } @Test public void test001() { t.pick = 6; assertEquals(6, t.guessNumber(10)); } @Test public void test002() { t.pick = 1; assertEquals(1, t.guessNumber(1)); } @Test public void test003() { t.pick = 1; assertEquals(1, t.guessNumber(2)); } @Test public void test004() { t.pick = 2; assertEquals(2, t.guessNumber(2)); } @Test public void test005() { t.pick = 1702766719; assertEquals(1702766719, t.guessNumber(2126753390)); } @Test public void test006() { t.pick = 3; assertEquals(3, t.guessNumber(3)); } @Test public void test006001() { t.pick = 2; assertEquals(2, t.guessNumber(3)); } @Test public void test007() { t.pick = 4; assertEquals(4, t.guessNumber(4)); } @Test public void test008() { t.pick = 3; assertEquals(3, t.guessNumber(4)); }
若非注明,均为原创,欢迎转载,转载请注明来源:LeetCode第374题 – 猜数字大小