num이라는 숫자 목록이 있고 쿼리 목록도 있다고 가정합니다. 여기서 각 쿼리 요소에는 [i, j]가 포함됩니다. 따라서 이 쿼리는 [i, j](둘 다 포함)의 하위 목록이 산술 시퀀스인지 여부를 묻습니다. 따라서 마지막으로 true를 반환하는 쿼리 수를 찾아야 합니다.
따라서 입력이 nums =[2, 4, 6, 8, 7, 6, 5, 2] 쿼리 =[[3, 4],[0, 3],[2, 4]]인 경우 출력은 2가 됩니다. [2, 4, 6, 8]은 산술 시퀀스이므로 쿼리 [0, 3]이 참입니다. [8, 7]의 경우도 산술 시퀀스이므로 쿼리 [3, 4]도 참입니다. 그러나 [6, 8, 7]은 산술 수열이 아니므로 [2, 4]는 참이 아닙니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- nums가 비어 있으면
- 0을 반환
- n :=숫자 크기
- diff :=0에서 n - 2 범위의 각 i에 대한 요소(nums[i + 1] - nums[i])가 있는 목록
- rle :=크기 목록(n - 1) 및 0으로 채우기
- 0 ~ n - 2 범위의 i에 대해
- i> 0이고 diff[i]가 diff[i - 1]과 같으면
- rle[i] :=rle[i - 1] + 1
- 그렇지 않으면
- rle[i] :=1
- i> 0이고 diff[i]가 diff[i - 1]과 같으면
- ans :=0
- 쿼리의 각 (i, j)에 대해 다음을 수행합니다.
- i가 j와 같으면
- ans :=ans + 1
- 그렇지 않으면
- ans :=ans + (rle[j - 1]>=(j - i)인 경우 1, 그렇지 않은 경우 0)
- i가 j와 같으면
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(nums, queries): if not nums: return 0 n = len(nums) diff = [nums[i + 1] - nums[i] for i in range(n - 1)] rle = [0] * (n - 1) for i in range(n - 1): if i > 0 and diff[i] == diff[i - 1]: rle[i] = rle[i - 1] + 1 else: rle[i] = 1 ans = 0 for i, j in queries: if i == j: ans += 1 else: ans += rle[j - 1] >= (j - i) return ans nums = [2, 4, 6, 8, 7, 6, 5, 2] queries = [[3, 4],[0, 3],[2, 4]] print(solve(nums, queries))
입력
[2, 4, 6, 8, 7, 6, 5, 2], [[3, 4],[0, 3],[2, 4]]
출력
2