최대 동일한 행 수를 위해 열 뒤집기

1072. 최대 동일한 행 수를 위해 열 뒤집기

난이도:중

주제: 배열, 해시 테이블, 행렬

m x n 이진 행렬 행렬이 주어졌습니다.

행렬에서 원하는 수의 열을 선택하고 해당 열의 모든 셀을 뒤집을 수 있습니다(예: 셀 값을 0에서 1로 또는 그 반대로 변경).

몇 번 뒤집은 후 모든 값이 동일한 최대 행 수를 반환합니다.

예 1:

• 입력: 행렬 = [[0,1],[1,1]]
• 출력: 1
• 설명: 아무 값도 뒤집지 않으면 1행의 모든 ​​값이 동일해집니다.

예 2:

• 입력: 행렬 = [[0,1],[1,0]]
• 출력: 2
• 설명: 첫 번째 열의 값을 뒤집은 후 두 행의 값이 동일해졌습니다.

예 3:

• 입력: 행렬 = [[0,0,0],[0,0,1],[1,1,0]]
• 출력: 2
• 설명: 처음 두 열의 값을 뒤집은 후 마지막 두 행의 값이 동일합니다.

제약조건:

• m == 행렬.길이
• n == 행렬[i].길이
• 1
• 행렬[i][j]는 0 또는 1입니다.

힌트:

1. 열의 하위 집합을 뒤집는 것은 각 행에 숫자 K의 비트별 XOR을 수행하는 것과 같습니다. 우리는 X ^ K = 모두 0 또는 모두 1인 X 행을 원합니다. 이는 X = X^K ^K = (모두 0 또는 모두 1) ^K와 동일하므로 반대 비트가 설정된 행의 개수를 계산하려고 합니다. 예를 들어 K = 1이면 X = (00000...001 또는 1111....110) 행을 계산합니다.

해결책:

해시 맵을 활용하면 특정 열을 뒤집어 동일하게 만들 수 있는 행을 그룹화할 수 있습니다. 동일하게 만들 수 있는 행은 동일한 패턴이거나 보완적인 패턴(비트 부정)을 갖습니다.

단계별 해결 방법은 다음과 같습니다.

연산:

1. 각 행에 대해 패턴과 보완 패턴을 계산합니다.
   • 패턴은 그대로 행입니다.
   • 보완 패턴은 행의 모든 ​​비트를 뒤집은 결과입니다.
2. 해시 맵을 사용하여 패턴과 그 보완의 발생 횟수를 계산합니다.
3. 단일 패턴 또는 그 보색의 최대 개수가 결과를 제공합니다.

이 솔루션을 PHP로 구현해 보겠습니다. 1072. 최대 동일한 행 수를 위해 열 뒤집기

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

// Example usage
$matrix1 = [[0, 1], [1, 1]];
$matrix2 = [[0, 1], [1, 0]];
$matrix3 = [[0, 0, 0], [0, 0, 1], [1, 1, 0]];

echo maxEqualRowsAfterFlips($matrix1) . "\n"; // Output: 1
echo maxEqualRowsAfterFlips($matrix2) . "\n"; // Output: 2
echo maxEqualRowsAfterFlips($matrix3) . "\n"; // Output: 2
?>

설명:

1. 패턴 및 보완:
   • 각 행의 패턴은 연결된 행(예: 010)입니다.
   • 보수는 행의 모든 ​​비트를 뒤집습니다(예: 101).
2. 해시 맵: 각 패턴과 그 보완의 발생 횟수를 셉니다. 이는 동일하게 만들 수 있는 그룹 행에 도움이 됩니다.
3. 최대 개수: 단일 패턴 또는 해당 보완의 최대 개수를 찾아 동일하게 만들 수 있는 행 수를 결정합니다.

복잡성:

• 시간 복잡도: O(m x n), 여기서 m은 행 수이고 n은 열 개수입니다.
• 공간 복잡도: O(m x n), 해시 맵에 패턴을 저장하는 데 사용됩니다.

이 솔루션은 제약 조건을 준수하며 문제 규모에 비해 효율적입니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 최대 동일한 행 수를 위해 열 뒤집기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!