“This is the fifth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

  • Related articles

    LeetCode brush questions summary: LeetCode brush questions

    1. Title Description

    Guess the number size

    The rules of the guessing game are as follows:

    For each round, I pick a random number from 1 to N. Guess which number you picked. If you’re wrong, I’ll tell you if your guess is bigger or smaller than my pick. You can get the guess result by calling a predefined interface int guess(int num), which returns three possible values (-1, 1 or 0) :

    -1: I picked a smaller number than you guessed pick < num 1: I picked a larger number than you guessed pick > num 0: I picked the same number as you guessed. A: congratulations! You guessed it! Pick == num returns the number I selected.

    Second, train of thought analysis

    • Look at the examples in the title, let’s clarify the idea ~

    • Example 1:

      Input: n = 10, pick = 6 Output: 6Copy the code

    • Example 2:

      Input: n = 1, pick = 1 Output: 1Copy the code

    • Example 3:

    • Input: n = 2, pick = 1 Output: 1Copy the code

    • Example 4:

    • Input: n = 2, pick = 2 Output: 2Copy the code

    • That’s the point. Don’t be fooled!

      • -1: My number is small
      • 1: My numbers are bigger
      • 0: Congratulations! You guessed it!

    • This minus one means that the real answer is smaller, or in other words, you guessed bigger, not smaller! Don’t be misled!

    AC code

    • Dichotomy YYDS!

      public class Solution extends GuessGame{ public int guessNumber(int n){ int low=1,high=n; While (low<=high){// int mid=low+(high-low)/2; // call guess int res=guess(mid); if(res! =0){ if(res==-1){ high=mid-1; }else { low=mid+1; } }else{ return mid; } } return 0; }}Copy the code

    • Execution Result:

    • After finishing, I went to find the solution of other gods, and found that basically are using dichotomy to solve, but they write more concise and clear!

    • In my opinion, the expression of this question is very misleading. In fact, the ultimate purpose is to make us call GUESS method as little as possible to find the segmentation point.

    • There is the value of mid, do not cross the line! This can be received with /2 or directly with long!

The road ahead is long, I see no end, I will search high and low

If you think I bloggers write well! Writing is not easy, please like, follow, comment and give encouragement to the blogger ~ Hahah