최대 비트 OR 하위 집합 수 계산

2044. 최대 비트 OR 하위 집합 수 계산

난이도:중

주제: 배열, 역추적, 비트 조작, 열거

정수 배열 nums가 주어지면 nums 하위 집합의 최대 가능한 비트 OR를 찾고 비어 있지 않은 다른 하위 집합의 개수 최대 비트 OR.

b의 일부(0일 수도 있음) 요소를 삭제하여 b에서 a를 얻을 수 있는 경우 배열 a는 배열 b의

하위 집합입니다. 선택한 요소의 인덱스가 다른 경우 두 하위 집합은 다른 것으로 간주됩니다.

배열 a의 비트 OR은 a[0] OR a[1] OR ... OR a[a.length - 1] (

0-인덱스)와 같습니다.

예 1:

• 입력: 숫자 = [3,1]
• 출력: 2
• 설명: 하위 집합의 가능한 최대 비트 OR은 3입니다. 비트 OR이 3인 하위 집합이 2개 있습니다.
  [3]
  [3,1]

예 2:

• 입력: 숫자 = [2,2,2]
• 출력: 7
• 설명: [2,2,2]의 비어 있지 않은 모든 하위 집합은 2의 비트 OR을 갖습니다. 23 - 1 = 7개의 하위 집합이 있습니다.

예 3:

• 입력: 숫자 = [3,2,1,5]
• 출력: 6
• 설명: 하위 집합의 가능한 최대 비트 OR은 7입니다. 비트 OR이 7인 6개의 하위 집합이 있습니다.
  [3,5]
  [3,1,5]
  [3,2,5]
  [3,2,1,5]
  [2,5]
  [2,1,5]

제약조건:

1 <= nums.length <= 16
1 <= 숫자[i] <= 10
• 5

힌트:

가능한 모든 하위 집합을 열거할 수 있나요?
최대 비트 OR은 전체 배열의 비트 OR입니다.

해결책:

다음 단계를 따르세요.

1. 최대 비트 OR 계산: 하위 집합의 최대 비트 OR은 배열의 모든 요소에 걸쳐 비트 OR 연산을 수행하여 결정할 수 있습니다. 이는 가능한 최대 비트별 OR을 제공합니다.

2. 모든 하위 집합 열거: 배열의 크기가 작기 때문에(최대 16개) 비트 조작 기술을 사용하여 가능한 모든 하위 집합을 열거할 수 있습니다. 크기가 n인 배열의 경우 2^n개의 하위 집합이 가능합니다.

3. 유효한 하위 집합 계산: 각 하위 집합에 대해 비트별 OR을 계산하고 최대 비트별 OR과 일치하는지 확인합니다. 그렇다면 카운터를 증가시키세요.

이 솔루션을 PHP로 구현해 보겠습니다: 2044. 최대 비트 OR 하위 집합 개수

  
  
  설명:





최대 비트별 OR 계산:


루프를 사용하여 각 요소에 대해 비트 OR을 수행하여 배열의 최대 비트 OR을 계산합니다.



하위 집합 열거:


1에서 2^n - 1(n은 숫자의 길이)까지의 모든 숫자를 반복하여 비어 있지 않은 모든 하위 집합을 나타냅니다.
각 숫자에 대해 각 비트를 확인하여 하위 집합에 어떤 요소가 포함되어 있는지 확인합니다.



유효한 하위 집합 수:


현재 하위 집합에 대한 비트별 OR을 계산한 후 maxOR과 같은지 확인합니다. 그렇다면 카운터를 증가시킵니다.




이 솔루션은 제약 조건을 고려할 때 효율적이며 최대 16개의 배열에서 잘 작동하므로 평가할 하위 집합이 최대 65,535개가 됩니다.

연락처 링크

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

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


링크드인
깃허브



          

            
  

            
        
위 내용은 최대 비트 OR 하위 집합 수 계산의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!