最佳利益 調整後的分數的最大值 (二進位操作) Leetcode #861

更新於 發佈於 閱讀時間約 3 分鐘

題目敘述

輸入給定一個二元的二維矩陣grid

每次可以翻轉一條row,讓每個元素的01反相

也可以翻轉一條column,讓每個元素的01反相

可以操作任意多次

最後把每條row視為一條二進位表達式的數字,並且進行加總,得到最後的分數

請問分數的最大值是多少


原本的英文題目敘述


測試範例

Example 1:

Input: grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation: 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

Example 2:

Input: grid = [[0]]
Output: 1

約束條件

Constraints:

  • m == grid.length

m代表grid的高度

  • n == grid[i].length

n代表grid的寬度

  • 1 <= m, n <= 20

高度m和寬度n都介於 1 ~ 20之間。

  • grid[i][j] is either 0 or 1.

每個陣列元素都是0或1。


演算法 讓1盡可能多,並且居首位(MSB)

分數是row by row的二進位數字加總。

因此,為了分數最大化,推演出幾個想法。


一.

讓bit 1居首位(MSB)

因為1XXX ... X > 0XXX ... X

最高位是1永遠會比最高位是0的二進位數字還大,不論後面的分布情況為何


二.

MSB決定之後,接下來就是讓bit1 盡可能多,為了一致性

我們採取column wise的掃描方式,從第二高位掃描到最低位

每個column都採取讓1盡可能多的方式

如果保持原狀的bit1必較多,就保持原狀。

如果反轉的bit1比較多,就反轉。



程式碼 讓1盡可能多,並且居首位(MSB)

class Solution:
def matrixScore(self, grid: List[List[int]]) -> int:

h, w = len(grid), len(grid[0])

# Let MSB of each first column be 1
score = h

# Check from second column to last column
for column in range(1, w):

# Update score in binary representation
score <<= 1

# Option_1
keep = sum( grid[row][column] ^ grid[row][0] for row in range(h) )

# Option_2
flip = h - keep

# Add best score we can get on current column
score += max(keep, flip)

return score

複雜度分析

時間複雜度: O(h*w)

需要一個2D掃描,掃描每個元素恰好一次。


空間複雜度: O(1)

主要計算都是in-place計算,並且所用到的都是固定尺寸O(1)的臨時變數。


Reference:

[1] Score After Flipping Matrix - LeetCode

avatar-img
91會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
給定一個方陣grid,請計算每個3x3窗口內的最大值,並且也以方陣的形式輸出答案。 原本的英文題目敘述 測試範例 Example 1: Input: grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]] Output: [[9,9]
輸入給定一個已經從小到大排序好,而且彼此互質的整數陣列, 請問任取兩數分別當作分子、分母,第k小的分數是多少? 輸出請以 [分子,分母] 的形式回傳答案。
題目敘述 輸入給定一個整數陣列,分別代表每小朋友的快樂值。 要求我們選擇其中最快樂的k位小朋友,累加這群小朋友的快樂值。 有一個特殊的規則,第一位選中的小朋友快樂值不變。 接著,第二位選中的小朋友快樂值-1 再接著,第三位選中的小朋友快樂值-2 快樂值扣到只剩下0就不再往下扣 .
題目敘述 輸入給定一個整數陣列,分別代表每位運動員在比賽中的成績。 分數最高的給予金牌"Gold Medal" 分數次高的給予金牌"Silver Medal" 分數第三高的給予金牌"Bronze Medal" 剩餘的名次依照順序給予"4", "5", ..., "n" 的編號。 輸出時以字串
題目敘述 輸入給定一個鏈結串列,整體看代表一個十進位的數字,各別看每個節點代表每個digit,分別從最高位~最低位個位數。 要求我們把原本的數字乘以二,並且以鏈結串列的形式返回答案。 原本的英文題目敘述
題目敘述 題目給定一個鏈結串列中的節點Node,要求我們從鏈結串列中刪除該節點。 題目保證該節點不是tail node。 題目要求我們in-place原位操作。 原本的英文題目敘述 測試範例 Example 1: Input: head = [4,5,1,9], node = 5
給定一個方陣grid,請計算每個3x3窗口內的最大值,並且也以方陣的形式輸出答案。 原本的英文題目敘述 測試範例 Example 1: Input: grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]] Output: [[9,9]
輸入給定一個已經從小到大排序好,而且彼此互質的整數陣列, 請問任取兩數分別當作分子、分母,第k小的分數是多少? 輸出請以 [分子,分母] 的形式回傳答案。
題目敘述 輸入給定一個整數陣列,分別代表每小朋友的快樂值。 要求我們選擇其中最快樂的k位小朋友,累加這群小朋友的快樂值。 有一個特殊的規則,第一位選中的小朋友快樂值不變。 接著,第二位選中的小朋友快樂值-1 再接著,第三位選中的小朋友快樂值-2 快樂值扣到只剩下0就不再往下扣 .
題目敘述 輸入給定一個整數陣列,分別代表每位運動員在比賽中的成績。 分數最高的給予金牌"Gold Medal" 分數次高的給予金牌"Silver Medal" 分數第三高的給予金牌"Bronze Medal" 剩餘的名次依照順序給予"4", "5", ..., "n" 的編號。 輸出時以字串
題目敘述 輸入給定一個鏈結串列,整體看代表一個十進位的數字,各別看每個節點代表每個digit,分別從最高位~最低位個位數。 要求我們把原本的數字乘以二,並且以鏈結串列的形式返回答案。 原本的英文題目敘述
題目敘述 題目給定一個鏈結串列中的節點Node,要求我們從鏈結串列中刪除該節點。 題目保證該節點不是tail node。 題目要求我們in-place原位操作。 原本的英文題目敘述 測試範例 Example 1: Input: head = [4,5,1,9], node = 5
你可能也想看
Google News 追蹤
Thumbnail
大家好,我是woody,是一名料理創作者,非常努力地在嘗試將複雜的料理簡單化,讓大家也可以體驗到料理的樂趣而我也非常享受料理的過程,今天想跟大家聊聊,除了料理本身,料理創作背後的成本。
Thumbnail
哈囉~很久沒跟各位自我介紹一下了~ 大家好~我是爺恩 我是一名圖文插畫家,有追蹤我一段時間的應該有發現爺恩這個品牌經營了好像.....快五年了(汗)時間過得真快!隨著時間過去,創作這件事好像變得更忙碌了,也很開心跟很多厲害的創作者以及廠商互相合作幫忙,還有最重要的是大家的支持與陪伴🥹。  
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
大家好,我是woody,是一名料理創作者,非常努力地在嘗試將複雜的料理簡單化,讓大家也可以體驗到料理的樂趣而我也非常享受料理的過程,今天想跟大家聊聊,除了料理本身,料理創作背後的成本。
Thumbnail
哈囉~很久沒跟各位自我介紹一下了~ 大家好~我是爺恩 我是一名圖文插畫家,有追蹤我一段時間的應該有發現爺恩這個品牌經營了好像.....快五年了(汗)時間過得真快!隨著時間過去,創作這件事好像變得更忙碌了,也很開心跟很多厲害的創作者以及廠商互相合作幫忙,還有最重要的是大家的支持與陪伴🥹。  
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~