diff options
author | Jack Sangdahl <jack@pngu.org> | 2024-11-21 20:22:58 -0700 |
---|---|---|
committer | Jack Sangdahl <jack@pngu.org> | 2024-11-21 20:22:58 -0700 |
commit | d6266bc3b34b80c084e29d9ca179d09a7491860f (patch) | |
tree | f8b47c306d8e12f587d31b7e8919e956b4a90dd5 | |
parent | 2a0efea1b8cef058268235321d17471aaf3d44ff (diff) | |
download | leetcode-d6266bc3b34b80c084e29d9ca179d09a7491860f.tar.gz leetcode-d6266bc3b34b80c084e29d9ca179d09a7491860f.zip |
1072. flip columns for maximum number of equal rows
-rw-r--r-- | flip_col_max_equal_row.c | 55 | ||||
-rw-r--r-- | flip_col_max_equal_row.py | 30 |
2 files changed, 85 insertions, 0 deletions
diff --git a/flip_col_max_equal_row.c b/flip_col_max_equal_row.c new file mode 100644 index 0000000..9a81f35 --- /dev/null +++ b/flip_col_max_equal_row.c @@ -0,0 +1,55 @@ +// 1072. Flip Columns For Maximum Number of Equal Rows +#include "leetcode.h" + +/* + * you are given an 'm x n' binary matrix 'matrix'. you choose any number of + * columns in the matrix and flip every cell in that column (ie. change the + * value of the cell from 0 to 1 or vice versa). return the maximum number of + * rows that have all values equal after some number of flips. + */ + +bool rows_equal(int *r1, int *r2, int n) { + for (int i = 0; i < n; i++) + if (r1[i] != r2[i]) + return false; + return true; +} + +void flip_row(int *row, int *flipped, int numCols) { + for (int i = 0; i < numCols; i++) + flipped[i] = 1 - row[i]; +} + +int maxEqualRowsAfterFlips(int **matrix, int matrixSize, int *matrixColSize) { + int *flipped = (int *)malloc(matrixColSize[0] * sizeof(int)), ans = 0; + for (int i = 0; i < matrixSize; i++) { + int same_row_cnt = 0; + flip_row(matrix[i], flipped, matrixColSize[0]); + for (int j = 0; j < matrixSize; j++) + if (rows_equal(matrix[i], matrix[j], matrixColSize[0]) || + rows_equal(flipped, matrix[j], matrixColSize[0])) + same_row_cnt++; + if (same_row_cnt > ans) + ans = same_row_cnt; + } + free(flipped); + return ans; +} + +int main() { + int m1i[2][2] = {{0, 1}, {1, 1}}, m2i[2][2] = {{0, 1}, {1, 0}}, + m3i[3][3] = {{0, 0, 0}, {0, 0, 1}, {1, 1, 0}}; + struct two_d_arr m1, m2, m3; + two_d_arr_init(&m1, 2, 2, m1i); + two_d_arr_init(&m2, 2, 2, m2i); + two_d_arr_init(&m3, 3, 3, m3i); + printf("%d\n", maxEqualRowsAfterFlips(m1.arr, m1.row_size, + m1.col_size)); // expect: 1 + printf("%d\n", maxEqualRowsAfterFlips(m2.arr, m2.row_size, + m2.col_size)); // expect: 2 + printf("%d\n", maxEqualRowsAfterFlips(m3.arr, m3.row_size, + m3.col_size)); // expect: 2 + two_d_arr_free(&m1); + two_d_arr_free(&m2); + two_d_arr_free(&m3); +} diff --git a/flip_col_max_equal_row.py b/flip_col_max_equal_row.py new file mode 100644 index 0000000..6590d4e --- /dev/null +++ b/flip_col_max_equal_row.py @@ -0,0 +1,30 @@ +# 1072. Flip Columns For Maximum Number of Equal Rows + +""" +you are given an 'm x n' binary matrix 'matrix'. you choose any number of +columns in the matrix and flip every cell in that column (ie. change the +value of the cell from 0 to 1 or vice versa). return the maximum number of +rows that have all values equal after some number of flips. +""" + + +class Solution(object): + def maxEqualRowsAfterFlips(self, matrix): + """ + :type matrix: List[List[int]] + :rtype: int + """ + cnt = {} + for row in matrix: + norm = tuple(cell if row[0] == 0 else 1 - cell for cell in row) + if norm not in cnt: + cnt[norm] = 0 + cnt[norm] += 1 + return max(cnt.values()) + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxEqualRowsAfterFlips(matrix=[[0, 1], [1, 1]])) + print(obj.maxEqualRowsAfterFlips(matrix=[[0, 1], [1, 0]])) + print(obj.maxEqualRowsAfterFlips(matrix=[[0, 0, 0], [0, 0, 1], [1, 1, 0]])) |