비트별 AND 0보다 큰 조합의 최대 조합

2275. 비트 단위 AND 0보다 큰 조합

난이도:중

주제: 배열, 해시 테이블, 비트 조작, 계산

nums 배열의 비트 AND는 nums에 있는 모든 정수의 비트 AND입니다.

• 예를 들어 nums = [1, 5, 3]의 경우 비트 AND는 1 & 5 & 3 = 1과 같습니다.
• 또한 nums = [7]의 경우 비트 AND는 7입니다.

양의 정수 후보 배열이 제공됩니다. 모든 조합의 비트 AND를 평가합니다. 후보자의 각 번호는 각 조합에서 한 번만 사용할 수 있습니다.

비트 AND 0보다 큰 후보 조합의 가장 큰

크기를 반환합니다.

예 1:

• 입력:
후보 = [16,17,71,62,12,24,14]
• 출력:
4
• 설명:
  [16,17,62,24] 조합에는 16 & 17 & 62 & 24 = 16 >의 비트 AND가 있습니다. 0.
  조합의 크기는 4입니다.
  4보다 큰 크기의 조합에는 0보다 큰 비트 AND가 없음을 알 수 있습니다.
  둘 이상의 조합이 가장 큰 크기를 가질 수 있습니다.
  예를 들어 [62,12,24,14] 조합에는 62 & 12 & 24 & 14 = 8 >의 비트 AND가 있습니다. 0.

예 2:

• 입력:
후보 = [8,8]
• 출력:
2
• 설명:
  가장 큰 조합 [8,8]은 8 & 8 = 8 >의 비트 AND를 갖습니다. 0.
  조합의 크기가 2이므로 2를 반환합니다.

제약조건:

• ^{1 5}
• ^{1 7}

힌트:

비트별 AND가 0보다 크려면 조합의 모든 숫자에 대해 적어도 하나의 비트가 1이어야 합니다.
후보의 길이는 24비트이므로 모든 비트 위치에 대해 비트별 AND가 해당 비트 위치에서 1을 갖도록 가장 큰 조합의 크기를 계산할 수 있습니다.

해결책:

조합의 모든 숫자에 걸쳐 이진 표현에서 하나 이상의 비트 위치가 설정(1)으로 유지되는 숫자 그룹을 식별하는 데 중점을 두어야 합니다.

솔루션 개요

1. 비트 분석

   : 후보의 각 숫자는 최대 24비트의 이진수로 표현될 수 있으므로(1

2. 각 위치에서 설정된 비트 계산: 각 비트 위치에 대해 해당 비트가 1로 설정된 후보의 숫자 수를 계산합니다. 여러 숫자가 동일한 위치에서 비트를 공유하는 경우 잠재적으로 해당 비트 위치에서 0보다 큰 비트 AND와 조합을 형성합니다.

3. 가장 큰 수 찾기: 주어진 위치에 설정된 비트가 있는 가장 큰 숫자가 답이 될 것입니다. 이는 비트별 AND 결과가 다음보다 큰 가능한 가장 큰 조합을 나타내기 때문입니다. 제로.

예

후보 고려 = [16, 17, 71, 62, 12, 24, 14]:

• 각 숫자를 바이너리로 변환하고 비트 위치를 분석합니다.
• 모든 숫자에 걸쳐 각 비트가 몇 번이나 설정되었는지 계산합니다.
• 모든 비트 위치에서 최대 개수를 찾습니다.

이 솔루션을 PHP: 2275로 구현해 보겠습니다. 비트 단위 AND 0보다 큰 조합의 최대 조합

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

// Example usage
$candidates = [16, 17, 71, 62, 12, 24, 14];
echo largestCombination($candidates); // Output: 4
?>

설명:

1. 각 비트 위치를 통한 루프: 0부터 23까지 각 비트 위치를 반복합니다.
2. 비트 세트가 있는 숫자 계산: 각 위치에 대해 특정 비트 세트가 있는 후보자의 숫자가 몇 개인지 계산합니다.
3. 최대 조합 크기 업데이트: 모든 비트 위치에서 가장 높은 수를 추적합니다.
4. 결과 반환: 결과는 필요에 따라 0보다 큰 비트 AND를 사용하여 가장 큰 조합 크기입니다.

복잡성 분석

• 시간 복잡도: O(n x 24) = O(n), 여기서 n은 각 숫자에 대해 24개의 연산(각 비트 위치당 하나씩)을 수행하기 때문입니다.
• 공간 복잡도: O(1), 고정된 양의 추가 공간만 사용하기 때문입니다.

이 접근 방식은 입력 크기 제한(candidates.length <= 10⁵)을 처리하는 데 충분히 효율적입니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 비트별 AND 0보다 큰 조합의 최대 조합의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!