iT邦幫忙

2021 iThome 鐵人賽

DAY 26
0
自我挑戰組

每日LeetCode解題紀錄系列 第 26

LeetCode解題 Day26

782. Transform to Chessboard

https://leetcode.com/problems/transform-to-chessboard/


題目解釋

你會得到一個n*n大小的表格,內容不是0就是1,每一次都可以互換兩個row或兩個col,請把這個表格變成西洋棋盤的樣式,也就是每個01不相臨。

回傳需要互換幾次,如果無法變成西洋棋盤樣式則回傳-1

example

https://i.imgur.com/cVUl7hn.png


解法

  • 這題超難,目前答案來不及消化,先卡位
  • 9/27 補上

首先,要能排成西洋棋盤樣式需要符合下面條件:

  1. 所有的表格中的row只有兩種樣式,和任一row相同或和任一row完全相反;這同樣適用於column,不過我們不用兩樣都檢查,只要row或colume符合規則,另一個就同樣符合規則

  2. 每個row的"1""0"的數量要一樣(表格長寬為偶數)或是差一個(表格長寬為奇數)

符合西洋棋盤樣式的row有兩種樣式10101...01010...,至於要交換幾次才能變成西洋棋盤則如下:

  1. 分別計算目前最外邊的row和column與 0 1 交錯的樣式有幾格不同,例如1001001010有2格不同,和10101則有3格不同

  2. 我們沒辦法把目前樣式變成有奇數個不同的那種樣式,所以第1點那種3格不同的樣式就不考慮了;如果都是差偶數個的話,選短的那個

  3. 最後把row和colume的差加起來,因為我們是2個2個交換,所以最後要除以2

程式碼

class Solution:
    def movesToChessboard(self, board: List[List[int]]) -> int:
        
        n=len(board)
        
        rows = []
        for i in board:
            rows.append(''.join(map(str, i)))
        
        count_row = Counter(rows)
        keys = list(count_row)
        
        if len(keys) != 2: return -1 
        # 只能有兩種版型
        if abs(count_row[keys[0]] - count_row[keys[1]]) > 1: return -1 
        # 版型數量不是剛好,就是差一個
        if abs(keys[0].count('0') - keys[0].count('1')) > 1: return -1 
        # 每個版型的0和1數量不是剛好,就是差一個
        if any(a == b for a, b in zip(*keys)): return -1
        # 兩個版型當然不能長的一模一樣
        
        
        patt1 = ([0, 1]*(n//2+1))[:n] # 101010...
        patt2 = ([1, 0]*(n//2+1))[:n] # 010101...
        #兩種西洋棋盤樣式
        
        diffr1, diffr2, diffc1, diffc2 = 0,0,0,0
        for a, b in zip(board[0], patt1):
            if a != b:
                diffr1 += 1
                # row和西洋棋盤樣式1差幾個
                
        for a, b in zip(board[0], patt2):
            if a != b:
                diffr2 += 1
                # row和西洋棋盤樣式2差幾個
        
        for a, b in zip(list(board[i][0] for i in range(n)), patt1):
            if a != b:
                diffc1 += 1
                # column和西洋棋盤樣式1差幾個
            
        for a, b in zip(list(board[i][0] for i in range(n)), patt2):
            if a != b:
                diffc2 += 1
                # column和西洋棋盤樣式2差幾個
        
        cands_x = [x for x in [diffr1, diffr2] if x % 2 == 0]
        cands_y = [y for y in [diffc1, diffc2] if y % 2 == 0]
        # 差奇數個的那種不考慮
        
        
        return (min(cands_x) + min(cands_y)) // 2

上一篇
LeetCode解題 Day25
下一篇
LeetCode解題 Day27
系列文
每日LeetCode解題紀錄30

1 則留言

0

感謝大老解題

我要留言

立即登入留言