target이라는 숫자 목록이 있다고 가정합니다. 이제 주어진 목록과 길이가 같고 X가 1로 채워진 목록 X를 고려합시다. 다음 작업을 원하는 만큼 수행할 수 있습니다. X의 인덱스 i를 선택하고 X[i]를 X의 현재 합으로 설정합니다. 마지막으로 X가 대상으로 전환될 수 있는지 여부를 확인합니다.
따라서 입력이 target =[5, 9, 3]과 같으면 출력은 처음에 X =[1, 1, 1]과 같이 True가 되고 총합 3으로 업데이트하고 배열은 [1, 1]이 됩니다. , 3], 현재 합은 5, 업데이트 [5, 1, 3], 현재 합은 9이므로 목록은 [5, 9, 3]이 되며 대상입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- nums에 요소가 하나만 있으면
- 숫자가 1일 때 true를 반환
- q :=모든 숫자의 값이 음수인 큐
- q를 힙으로 만들기
- s :=모든 숫자의 합
- 좋아요 :=맞습니다
- ok가 True인 동안 do
- x :=힙에서 요소 삭제 및 무효화
- d :=s - x
- x2 :=x mod d if d> 1 그렇지 않으면 1
- s :=s + x2 - x
- ok :=x는 x2와 동일하지 않습니다.
- x :=x2
- 힙 q에 -x 삽입
- q의 모든 요소가 -1일 때 true를 반환
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시
class Solution: def solve(self, nums): if len(nums) == 1: return nums == [1] from heapq import heapify, heappop, heappush q = [-x for x in nums] heapify(q) s = sum(nums) ok = True while ok: x = -heappop(q) d = s - x x2 = x % d if d > 1 else 1 s += x2 - x ok = x != x2 x = x2 heappush(q, -x) return all(x == -1 for x in q) ob = Solution() target = [5, 9, 3] print(ob.solve(target))
입력
[5, 9, 3]
출력
True