All s Together II를 그룹화하기 위한 최소 스왑

2134. All 1's Together II

를 그룹화하기 위한 최소 스왑

중간

스왑은 배열에서 두 개의 고유한 위치를 가져와 그 값을 바꾸는 것으로 정의됩니다.

원형 배열은 첫 번째 요소와 마지막 요소를 인접으로 간주하는 배열로 정의됩니다.

이진 순환 배열 숫자가 주어지면 배열에 있는 모든 1을 모든 위치로 그룹화하는 데 필요한 최소 스왑 수를 반환합니다.

예 1:

• 입력: 숫자 = [0,1,0,1,1,0,0]
• 출력: 1
• 설명: 다음은 1을 모두 그룹화하는 몇 가지 방법입니다.
  • [0,0,1,1,1,0,0] 1개의 스왑을 사용합니다.
  • [0,1,1,1,0,0,0] 1개의 스왑을 사용합니다.
  • [1,1,0,0,0,0,1] 2개의 스왑을 사용합니다(배열의 순환 속성 사용).
  • 0개의 스왑으로 1을 모두 그룹화할 수 있는 방법은 없습니다.
  • 따라서 필요한 최소 스왑 횟수는 1입니다.

예 2:

• 입력: 숫자 = [0,1,1,1,0,0,1,1,0]
• 출력: 2
• 설명: 다음은 모든 1을 그룹화하는 몇 가지 방법입니다.
  • [1,1,1,0,0,0,0,1,1] 2개의 스왑을 사용합니다(배열의 순환 속성 사용).
  • [1,1,1,1,1,0,0,0,0] 2개의 스왑을 사용합니다.
  • 0 또는 1개의 교환으로 1을 모두 그룹화할 수 있는 방법은 없습니다.
  • 따라서 필요한 최소 스왑 횟수는 2입니다.

예 3:

• 입력: 숫자 = [1,1,0,0,1]
• 출력: 0
• 설명: 배열의 순환 특성으로 인해 모든 1이 이미 그룹화되어 있습니다.
  • 따라서 필요한 최소 스왑 횟수는 0입니다.

제약조건:

• 1 <= nums.length <= 10⁵
• nums[i]는 0 또는 1입니다.

힌트:

1. 함께 그룹화되는 1의 개수는 고정되어 있습니다. 전체 배열이 가지고 있는 1의 개수입니다.
2. 이 번호로 전체 전화하세요. 그런 다음 전체 크기(둘러싸일 수 있음)의 모든 하위 배열을 확인하고 하위 배열을 모두 1로 만드는 데 필요한 스왑 수를 확인해야 합니다.
3. 필요한 스왑 횟수는 하위 배열의 0 개수입니다.
4. 배열의 순환 속성을 제거하기 위해 원래 배열을 자체 배열에 추가할 수 있습니다. 그런 다음 각 하위 배열의 총 길이를 확인합니다.
5. 매번 하위 배열의 0 개수를 다시 계산하지 않으려면 어떻게 해야 하나요? 슬라이딩 윈도우 기술이 도움이 될 수 있습니다.

해결책:

이 문제를 해결하려면 다음 단계를 따르세요.

1. 전체 1 개수 계산: 이는 함께 그룹화하는 데 필요한 1의 개수입니다.
2. 배열 확장: 원형 특성을 처리하려면 배열을 자체에 추가하세요.
3. 슬라이딩 윈도우 기법 사용: 확장 어레이에 슬라이딩 윈도우 기법을 적용하여 필요한 최소 스왑 수를 찾습니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2134. All 1's Together II를 그룹화하기 위한 최소 스왑

  
  
  설명:




총 1 개수 계산: 원본 배열에서 총 1 개수를 계산합니다.

배열 확장: 원형 특성을 처리하기 위해 원본 배열을 자체적으로 연결합니다.

초기 창: 전체 1 개수와 동일한 크기의 초기 창에서 0의 개수를 셉니다.

슬라이딩 창: 확장된 어레이를 가로질러 창을 슬라이드합니다. 각각의 새로운 위치에 대해 창에 들어오고 나가는 요소를 기반으로 0의 개수를 업데이트합니다.

최소값 찾기: 필요한 최소 스왑 수에 해당하는 0의 최소 개수를 추적합니다.


이 솔루션은 원형 배열을 선형 문제로 변환하여 효율적으로 처리하고 슬라이딩 윈도우 기술을 사용하여 전체 1 개수와 동일한 크기의 각 윈도우에서 실행 개수를 0으로 유지합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.


링크드인
깃허브



          

            
  

            
        
위 내용은 All s Together II를 그룹화하기 위한 최소 스왑의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!