비트별 AND 0보다 큰 조합의 최대 조합-PHP 튜토리얼-php.cn

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

Susan Sarandon

풀어 주다： 2024-11-07 22:24:03

원래의

625명이 탐색했습니다.

Largest Combination With Bitwise AND Greater Than Zero

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

난이도:중

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

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

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

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

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

크기를 반환합니다.

예 1:

입력:
출력:
설명:

예 2:

입력:
출력:
설명:

제약조건:

^{1 5}
^{1 7}

힌트:

해결책:

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

솔루션 개요

비트 분석
: 후보의 각 숫자는 최대 24비트의 이진수로 표현될 수 있으므로(1
각 위치에서 설정된 비트 계산: 각 비트 위치에 대해 해당 비트가 1로 설정된 후보의 숫자 수를 계산합니다. 여러 숫자가 동일한 위치에서 비트를 공유하는 경우 잠재적으로 해당 비트 위치에서 0보다 큰 비트 AND와 조합을 형성합니다.
가장 큰 수 찾기: 주어진 위치에 설정된 비트가 있는 가장 큰 숫자가 답이 될 것입니다. 이는 비트별 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
?>

로그인 후 복사