翻轉列以獲得最大相等行數

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 == 矩陣.length
• n == 矩陣[i].length
• 1
• 矩陣[i][j]為0或1。

提示：

1. 翻轉列的子集就像是對每行執行某個數字 K 的位元異或運算。我們想要 X 行 X ^ K = 全 0 或全 1。這與 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 上給

存儲庫

一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！ 如果您想要更多類似的有用內容，請隨時關注我：

領英
GitHub

以上是翻轉列以獲得最大相等行數的詳細內容。更多資訊請關注PHP中文網其他相關文章！