크기가 n인 시퀀스 번호가 있다고 가정합니다. 모든 쌍(p, q)이 좋은 쌍인 nums의 부분열의 최대 크기를 찾아야 합니다. pait는 다음 조건 중 하나 이상을 충족하는 경우에만 좋은 쌍이라고 합니다. 1. p의 고유한 소수 제수의 패리티가 b의 패리티와 동일합니다. 예를 들어, 값 18에는 2와 3이라는 두 개의 서로 다른 소수가 있습니다. 2. p의 모든 양수 제수 합계의 패리티는 q와 같습니다.
따라서 입력이 nums =[2,3,6,8]과 같으면 출력은 3
이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=숫자 크기
- 3개의 빈 목록 cnt, total, result 정의
- 숫자 단위의 각 i에 대해 다음을 수행합니다.
- 카운트:=0, 전체:=0
- prime :=새 목록
- num의 각 j에 대해 다음을 수행합니다.
- (범위 2에서 j까지의 모든 k에 대한 j mod k)가 true이면
- 소수 끝에 j 삽입
- (범위 2에서 j까지의 모든 k에 대한 j mod k)가 true이면
- 소수의 각 j에 대해 다음을 수행합니다.
- i mod j가 0이면
- 카운트 :=카운트 + 1
- i mod j가 0이면
- 카운트가 짝수이면
- cnt 끝에 '홀수' 삽입
- 그렇지 않으면
- cnt 끝에 '짝수' 삽입
- 1~i 범위의 j에 대해
- i mod j가 0과 같으면
- tot :=tot + j
- i mod j가 0과 같으면
- tot가 홀수이면
- 총계 끝에 '홀수' 삽입
- 그렇지 않으면
- 총계 끝에 '짝수' 삽입
- 0에서 n-2 사이의 i에 대해 다음을 수행합니다.
- i+1 ~ n - 1 범위의 j에 대해
- cnt[i]가 cnt[j]와 같거나 total[i]가 total[j]와 같으면
- 결과 끝에 숫자[i] 삽입
- j가 n-2와 같으면
- 결과 끝에 숫자[j] 삽입
- cnt[i]가 cnt[j]와 같거나 total[i]가 total[j]와 같으면
- i+1 ~ n - 1 범위의 j에 대해
- result :=결과에서 새 집합의 새 목록
- 결과의 반환 크기
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(nums):
n = len(nums)
cnt = []
total = []
result = []
for i in nums:
count = 0
tot = 0
prime = []
for j in nums:
if all(j % k for k in range(2, j)) == True:
prime.append(j)
for j in prime:
if i % j == 0:
count += 1
if count % 2:
cnt.append('odd')
else:
cnt.append('even')
for j in range(1,i+1):
if i % j == 0:
tot += j
if tot % 2:
total.append('odd')
else:
total.append('even')
for i in range(n-1):
for j in range(i+1, n):
if cnt[i] == cnt[j] or total[i] == total[j]:
result.append(nums[i])
if j == n-1:
result.append(nums[j])
result = list(set(result))
return len(result)
nums = [2,3,6,8]
print(solve(nums)) 입력
15, 3, 8
출력
3