LeetCode第374题 – 猜数字大小

题目

解答

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));
}