最大数の等しい行を得るために列を反転する

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
• 説明: 最初の 2 列の値を反転すると、最後の 2 行の値は同じになります。

制約:

• m == 行列.長さ
• n == 行列[i].length
• 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 で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が最大数の等しい行を得るために列を反転するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。