최대 비트 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 1 5

힌트:

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

해결책:

다음 단계를 따르세요.

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

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

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

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

<?php /**
 * @param Integer[] $nums
 * @return Integer
 */
function countMaxBitwiseORSubsets($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$nums1 = [3, 1];
echo countMaxBitwiseORSubsets($nums1) . "\n"; // Output: 2

$nums2 = [2, 2, 2];
echo countMaxBitwiseORSubsets($nums2) . "\n"; // Output: 7

$nums3 = [3, 2, 1, 5];
echo countMaxBitwiseORSubsets($nums3) . "\n"; // Output: 6
?>

설명:

1. 최대 비트별 OR 계산:

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

2. 하위 집합 열거:

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

3. 유효한 하위 집합 수:

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

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

연락처 링크

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

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

• 링크드인
• 깃허브

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