deeprun

Same Tree

 문제 설명

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 will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API int guess(int num), which returns three possible results:

• -1: Your guess is higher than the number I picked (i.e. num > pick).
• 1: Your guess is lower than the number I picked (i.e. num < pick).
• 0: your guess is equal to the number I picked (i.e. num == pick).

Return the number that I picked.

 제한 사항

• 1 <= n <= 231 - 1
• 1 <= pick <= n

 입출력 예

Example 1:

Input: n = 10, pick = 6
Output: 6

Example 2:

Input: n = 1, pick = 1
Output: 1

Example 3:

Input: n = 2, pick = 1
Output: 1

 Python 코드

Python code 

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:

class Solution: 
    def guessNumber(self, n: int) -> int: 
        left, right = 1, n 
        
        while True: 
            middle_num = int((left + right) / 2) 
            if guess(middle_num) == 1: 
                left = middle_num + 1 
            elif guess(middle_num) == -1: 
                right = middle_num - 1 
            else: 
                return middle_num

* 참고 링크 : https://somjang.tistory.com/entry/leetCode-374-Guess-Number-Higher-or-Lower-Python

 C++ 코드

C ++ code

//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Guess Number Higher or Lower.
//Memory Usage: 7.3 MB, less than 100.00% of C++ online submissions for Guess Number Higher or Lower.

// 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 left = 1, right = n, cur = left+(right-left)/2;

        while(true){
            switch(guess(cur)){
                case -1:
                    right = cur-1;
                    cur = left+(right-left)/2;
                    break;
                case 1:
                    left = cur+1;
                    cur = left+(right-left)/2;
                    break;
                case 0:
                    return cur;
            }
        }
        return 0;
    }
};

* 참고 링크 : https://github.com/keineahnung2345/leetcode-cpp-practices/blob/master/374.%20Guess%20Number%20Higher%20or%20Lower.cpp

 출처

https://leetcode.com/problems/guess-number-higher-or-lower/