주어진 범위 내에서 점프 값을 선택하여 주어진 이진 문자열의 끝에 도달할 수 있는지 확인합니다.

이진 문자열은 0과 1의 두 가지 유형의 문자만 포함하는 문자열입니다. 이진 문자열과 두 개의 정수 L과 R이 주어졌습니다. 문자열 값이 '0'인 인덱스에서 'L'과 'R'(포함) 사이의 크기 점프를 수행할 수 있습니다. 0번째 인덱스에서 시작해서 마지막 인덱스에 도달할 수 있는지 알아내야 합니다.

예제 예

으아아아

Explanation

은 다음과 같이 번역됩니다.

Explanation

0 인덱스에서 세 번 점프한 다음 4로 두 번 더 점프하여 원하는 최종 인덱스에 도달할 수 있습니다.

으아아아

Explanation

은 다음과 같이 번역됩니다.

Explanation

두 번의 점프를 할 수 있습니다. 각 점프는 2 또는 3입니다. 0번째 인덱스에서 점프하면 2번째 인덱스나 3번째 인덱스에 도달한 다음 '1' 인덱스 값으로만 ​​점프할 수 있고 더 이상 점프할 수 없습니다.

방법 1

Idea

의 중국어 번역은

Idea

입니다.

다이나믹 프로그래밍의 개념을 적용하는 아이디어입니다. 특정 위치에 접근할 수 있는지 여부를 나타내는 배열을 유지할 수 있습니다.

한 위치를 달성할 수 있다면 다음 l~r 위치도 달성할 수 있습니다.

구현

문자열, 왼쪽 위치, 오른쪽 위치를 매개변수로 받아 부울 값을 반환하는 함수를 만들어 보겠습니다.

이 함수에서는 배열을 반복하고 중첩된 for 루프를 사용하여 범위를 반복하고, 현재 위치에서 현재 범위 위치를 뺀 위치에 도달 가능한지 확인하고, 도달 가능한 경우 해당 위치에 도달할 수 있는 것입니다.

결국 최종 답변을 나타내는 DP 배열의 마지막 인덱스 상태를 반환하게 됩니다.

Example

의 중국어 번역은 다음과 같습니다:

Example

으아아아

출력

으아아아

시간 복잡도와 공간 복잡도

위 코드의 시간 복잡도는 O(N^2)입니다. 여기서 N은 주어진 문자열의 크기입니다. 중첩된 for 루프를 사용했는데 그 결과 N^2의 시간 복잡도가 발생했습니다.

위 코드의 공간 복잡도는 O(N)입니다. 왜냐하면 DP 상태를 저장하기 위해 길이 N의 배열을 사용하기 때문입니다.

방법 2

이 방법은 이전 방법보다 더 나은 버전입니다. 이 방법에서는 우리가 할 수 있는 점프 수를 얻기 위해 정수를 유지합니다. 각 점프에서 점프가 가능하면 카운트를 늘리고 어떤 위치에서도 점프가 불가능하면 카운트를 줄일 수 있습니다.

DP 배열의 각 인덱스에 데이터를 저장하고 나중에 사용하겠습니다.

Example

의 중국어 번역은 다음과 같습니다:

Example

으아아아

출력

으아아아

시간 복잡도와 공간 복잡도

위 코드의 시간 복잡도는 O(N)입니다. 여기서 N은 주어진 문자열의 크기입니다. 시간 복잡도가 선형이 되도록 단일 루프를 사용하여 문자열을 반복합니다.

위 코드의 공간 복잡도는 O(N)입니다. 왜냐하면 DP 상태를 저장하기 위해 길이 N의 배열을 사용하기 때문입니다.

결론

이 튜토리얼에서는 첫 번째 인덱스부터 시작하여 주어진 문자열의 끝 부분에 '0'이 포함된 인덱스에서 주어진 수의 인덱스를 이동하여 주어진 문자열에 도달할 수 있는지 여부를 결정하는 코드를 구현했습니다. 동적 계획법을 채택했는데, 시간 복잡도는 O(N^2), O(N), 공간 복잡도는 O(N)입니다.

위 내용은 주어진 범위 내에서 점프 값을 선택하여 주어진 이진 문자열의 끝에 도달할 수 있는지 확인합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!