![Re: [閒聊] 每日leetcode](https://i.imgur.com/pD41PYS.jpeg)
Re: [閒聊] 每日leetcode
※ 引述《JIWP (神楽めあ的錢包)》之銘言：
: 1072. Flip Columns For Maximum Number of Equal Rows
: 有m*n的binary matrix
: 可以選擇任一行，將那一行的元素翻轉(1->0、0->1)
: 這個操作可以做任意次
: 請問經過任意次操作後
: 可以得到最多幾個列(列裡面的元素全為1或0)
一開始看hint根本看不懂在工三小
就用暴力法解 代碼很醜就不貼了 測資大小才300所以O(n^3)可以過
看了下解答區讚最多的思路
簡單來說一個列只可能是全0或全1
假設你翻轉了一個列為全0，所有和他長的一樣的列也會變全0
然後和他剛好完全相反的會變全1
0101 -> 翻轉成全0 -> 0000
0101 -> -> 0000
1010 -> 翻轉成全1 -> 1111
0011 -> 不全0或全1-> 1100
這兩個的數量加起來就是翻轉後的相等列，取最大就好
直接run只贏過50%
對列做字串hash跳過長的一樣的列 跑得跟我暴力法一樣慢(???)
最後改用標記法不hash就贏過99%
又學到一課
Java Code
----------------------------------------------------
class Solution {
public int maxEqualRowsAfterFlips(int[][] matrix) {
int ans = 0;
int m = matrix.length;
int n = matrix[0].length;
boolean[] visited = new boolean[m];
for (int i = 0; i < m; i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
int[] flip = new int[n];
for (int j = 0; j < n; j++) {
flip[j] = 1 - matrix[i][j];
}
int cnt = 0;
for (int j = i; j < m; j++) {
if (Arrays.equals(matrix[j], matrix[i]) ||
Arrays.equals(matrix[j], flip)) {
visited[j] = true;
cnt++;
}
}
ans = Math.max(ans, cnt);
}
return ans;
}
}
----------------------------------------------------
--
https://i.imgur.com/pD41PYS.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.191.3 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1732297819.A.C64.html
留言