바이트 점프 필기시험 1 - 마리 오 점프 보드 게임 (BFS)
12333 단어 알고리즘
한 배열 은 발판 을 대표 하고 숫자 는 앞으로 나 뒤로 뛰 어 내 릴 수 있 는 최대 거리 (예 를 들 어 3, 그러면 1, 2, 3 을 뛰 어도 된다) 를 대표 하 며 0 은 절벽 (뛰 어 올 라 넘 어 져 죽는다) 을 대표 한다.출생 지점 P 를 지정 하여 종점 까지 뛰 어야 할 최소 횟수 (종점 은 마지막 요소 뒤에 있 음), 출력
-1
에 도달 할 수 없습니다.입력: 첫 번 째 줄: 배열 길이 N, 출생 점 P 두 번 째 줄: N 개의 숫자 출력: 최소 횟수
예시:
:
7 4
10 0 2 1 1 0 1
:
3
1<= N <= 10000 1 <= P <= N
사고의 방향
LeetCode 의 jump game II, 하지만 그 는 뒤로 뛸 수 밖 에 없 었 다.
최소 횟수, 그럼 BFS 입 니 다. 코드 를 작성 하 세 요.
코드
하나의 대열 로 BFS 를 실현 하 다.
package shen.leetcode.solution.toutiao;
import java.util.LinkedList;
public class Solution_toutiao_0630 {
public static void main(String[] args) {
System.out.println(core(new int[]{10, 0, 2, 1, 1, 0, 1}, 7));
}
public static LinkedList<Node> q = new LinkedList<>();
public static int core(int arr[], int start) {
q.offer(new Node(start - 1, 0));
while (!q.isEmpty()) {
Node curNode = q.poll();
if (arr[curNode.index] == 0) {
continue;
}
int maxLength = arr[curNode.index];
if (curNode.index + maxLength > arr.length - 1) {// , ,
return curNode.step + 1;
}
if (curNode.index - maxLength >= 0) { //
for (int i = curNode.index - maxLength; i <= curNode.index - maxLength + 2 * arr[curNode.index]; i++) {
if (i == curNode.index) continue;
q.offer(new Node(i, curNode.step + 1));
}
} else {
int begin = maxLength - curNode.index;
for (int i = begin; i <= begin + 2 * arr[curNode.index] - begin; i++) {
if (i == curNode.index) continue;
q.offer(new Node(i, curNode.step + 1));
}
}
}
return -1;
}
public static class Node {
int index;
int step;
public Node(int index, int step) {
this.index = index;
this.step = step;
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.