배열이 1에서 n까지의 순열을 보유하고 있다고 가정합니다. 크기가 n인 이진 문자열이 있고 처음에 모든 비트가 0으로 설정된 경우. 이제 1에서 n까지의 각 단계 i(인덱싱은 2진 문자열과 arr 모두에 대해 1부터 시작)에서 arr[i] 위치의 비트는 1로 설정됩니다. 또한 다른 값 m이 있고 최신 값을 찾아야 합니다. m 크기의 그룹이 존재하는 단계. 여기서 1의 그룹은 1의 연속적인 부분 문자열을 의미하므로 어느 방향으로도 확장될 수 없습니다. 길이가 정확히 m인 그룹이 존재하는 최신 단계를 찾아야 합니다. 그러한 그룹을 찾을 수 없으면 -1을 반환합니다.
따라서 입력이 arr =[3,5,1,2,4] m =3과 같으면 초기 이진 문자열이 "00000"이고 다음 단계를 따르기 때문에 출력은 4가 됩니다.
-
"00100", 그룹:["1"]
-
"00101", 그룹:["1", "1"]
-
"10101", 그룹:["1", "1", "1"]
-
"11101", 그룹:["111", "1"]
-
"11111", 그룹:["11111"]
여기에서 크기 3의 그룹이 존재하는 마지막 단계는 4단계입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=arr의 크기
-
숫자 :=0
-
as :=-1
-
l :=크기가 n인 배열, 0으로 채움
-
r :=크기가 n인 배열, 0으로 채움
-
범위 0에서 n - 1에 있는 i에 대해 수행
-
커 :=1
-
idx :=arr[i] - 1
-
r[idx]가 m과 같으면
-
숫자 :=숫자 - 1
-
-
l[idx]가 m과 같으면
-
숫자 :=숫자 - 1
-
-
cur :=cur + l[idx] + r[idx]
-
num :=num + cur는 m
과 동일합니다. -
숫자> 0이면
-
ans :=ans의 최대값, i + 1
-
-
idx - l[idx]> 0이면
-
r[idx - l[idx] - 1] :=cur
-
-
idx + r[idx]
-
l[idx + r[idx] + 1] :=cur
-
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
def solve(arr, m): n = len(arr) num = 0 ans = -1 l = [0] * n r = [0] * n for i in range(n): cur = 1 idx = arr[i] - 1 if r[idx] == m: num -= 1 if l[idx] == m: num -= 1 cur += l[idx] + r[idx] num += cur == m if num > 0: ans = max(ans, i + 1) if idx - l[idx] > 0: r[idx - l[idx] - 1] = cur if idx + r[idx] < n - 1: l[idx + r[idx] + 1] = cur return ans arr = [3,5,1,2,4] m = 3 print(solve(arr, m))
입력
[3,5,1,2,4], 3
출력
4