lintcode Guess Number Game(Java)
2808 단어 알고리즘
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 - 100 에서 숫자 20 을 추출 하고 매번 하 나 를 맞 히 는 것 (API guess (int num 제공) 은 20, 0 으로 돌아 가 는 것 과 같 습 니 다. 20 보다 크 면 - 1, 20 보다 작 으 면 1 로 돌아 가 고 0 으로 돌아 갈 때 까지 합 니 다.
샘플 n = 10, I pick 4 (but you don 't know) Return 4. Correct!
2. 해법
사실은 이분법 으로 문 제 를 푸 는 것 이 고 관건 적 인 단 계 는 바로 중간 노드 를 계산 하 는 것 이다.int middle = (start + end) / 2, 넘 칠 수 있 습 니 다. 아래 방법 은 int middle = start + (end - start) / 2; /중간 노드 의 알고리즘
/* The guess API is defined in the parent class GuessGame.
@param num, your guess
@return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num); */
public class Solution extends GuessGame {
/**
* @param n an integer
* @return the number you guess
*/
public int guessNumber(int n) {
// Write your code here
int start = 0;
int end = n;
while (start < end){
int middle = start + (end - start)/2;//
int result = guess(middle);
if (result == -1){
end = middle - 1;
}else if (result == 1){
start = middle + 1;
}else if (result == 0){
return middle;
}
}
return start;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
