LeetCode 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix (最少翻转次数将二进制矩阵全部置为0)
2023-03-14 09:46:20 时间
给一个矩阵mat,每个格子都是0或1,翻转一个格子会将该格子以及相邻的格子(有共同边)全部翻转(0变为1,1变为0)
求问最少需要翻转几次将所有格子全部置为0。
这题的重点是数据范围,比赛结束看了眼数据范围想把自己锤死= =
m == mat.length
n == mat[0].length
1 <= m <= 3
1 <= n <= 3
mat[i][j]
is 0 or 1.
也就是。。。。最多也就9个格子。。。。。暴力怎么都能搞出来的。。。。。
首先分析每个格子要么不反转,要么翻转一次,因为翻转2次的效果和不反转是一样的,不需要在考虑两次及以上的情况。
所以问题很简单,DFS 瞎搞搞就好了~~~
/** * @param {number[][]} mat * @return {number} */ /** * 获取一个二维数组的行数和列数 * @param {any[][]} matrix */ const getMatrixRowAndCol = (matrix) => matrix.length === 0 ? [0, 0] : [matrix.length, matrix[0].length]; /** * 翻转矩阵第index个元素 * @param {any [][]} matrix * @param {number} index * @param {any} value */ function flipMatrix(matrix, x, y, r, c) { let dir = [[0,1],[0,-1],[1,0],[-1,0]]; matrix[x][y] = 1 - matrix[x][y]; for (let i = 0; i < 4; i++) { let nx = x + dir[i][0]; let ny = y + dir[i][1]; if (nx < r && nx >= 0 && ny < c && ny >= 0) { matrix[nx][ny] = 1 - matrix[nx][ny]; } } } var minFlips = function(mat) { let [r, c] = getMatrixRowAndCol(mat); const dfs = (i, j, cnt) => { // console.log(i,j,cnt); if (i === r) { if (mat.every(col => col.every(item => !item))) return cnt; return -1; } if (j === c) { return dfs(i+1, 0, cnt); } let result = -1; // not flip (i, j) if ((result = dfs(i, j+1, cnt)) != -1) { return result; } // flip (i, j) flipMatrix(mat, i, j, r, c); if ((result = dfs(i, j+1, cnt+1)) != -1) { return result; } flipMatrix(mat, i, j, r, c); return -1; } return dfs(0, 0, 0); };
当然,既然题目是二进制矩阵,所以可以有更优雅点的做法,就是用一个二进制数来表示一种情况,二进制数的每一个表示对应格子是否翻转。那么,如果有n个格子,0~(2^n-1) 就可以表示所有情况了。
/** * @param {number[][]} mat * @return {number} */ /** * 获取一个二维数组的行数和列数 * @param {any[][]} matrix */ const getMatrixRowAndCol = (matrix) => matrix.length === 0 ? [0, 0] : [matrix.length, matrix[0].length]; /** * 翻转矩阵第index个元素 * @param {any [][]} matrix * @param {number} index * @param {any} value */ function flipMatrix(matrix, x, y, r, c) { let dir = [[0,1],[0,-1],[1,0],[-1,0]]; matrix[x][y] = 1 - matrix[x][y]; for (let i = 0; i < 4; i++) { let nx = x + dir[i][0]; let ny = y + dir[i][1]; if (nx < r && nx >= 0 && ny < c && ny >= 0) { matrix[nx][ny] = 1 - matrix[nx][ny]; } } } var minFlips = function(mat) { let [r, c] = getMatrixRowAndCol(mat); let n = r * c; // 一共有 n 个格子 每个格子有两种选择 不翻转(0) 翻转(1) // 所以可以用 n 位二进制数来表示格子的翻转情况 let stateNum = (1 << n) - 1; for (let state = 0; state <= stateNum; state++) { // 获取 mat 的一个副本用来修改 let copyMat = mat.map(item => ([...item])); let flipCnt = 0; // state 代表一种翻转情况 每一个二进制都表示对应格子是否翻转 for (let i = 0; i < r; i++) { for (let j = 0; j < c; j++) { let index = i * c + j; if ((1 << index) & state) { flipCnt++; flipMatrix(copyMat, i, j, r, c); } } } if (copyMat.every(col => col.every(item => !item))) return flipCnt; } return -1; };
最后,稍微不那么暴力的做法,首先枚举第一行的翻转方式,如果第一行某个格子反转后为1,那么对应位置第2行必翻转,否则就必须不翻转,以此类推。。。代码就是把上面的稍微改动下。
/** * @param {number[][]} mat * @return {number} */ /** * 获取一个二维数组的行数和列数 * @param {any[][]} matrix */ const getMatrixRowAndCol = (matrix) => matrix.length === 0 ? [0, 0] : [matrix.length, matrix[0].length]; /** * 翻转矩阵元素 (x,y) */ function flipMatrix(matrix, x, y, r, c) { let dir = [[0,1],[0,-1],[1,0],[-1,0]]; matrix[x][y] = 1 - matrix[x][y]; for (let i = 0; i < 4; i++) { let nx = x + dir[i][0]; let ny = y + dir[i][1]; if (nx < r && nx >= 0 && ny < c && ny >= 0) { matrix[nx][ny] = 1 - matrix[nx][ny]; } } } var minFlips = function(mat) { let [r, c] = getMatrixRowAndCol(mat); let stateNum = (1 << c) - 1; for (let state = 0; state <= stateNum; state++) { // 获取 mat 的一个副本用来修改 let copyMat = mat.map(item => ([...item])); let flipCnt = 0; // state 代表一种翻转情况 每一个二进制都表示对应格子是否翻转 // console.log(state); for (let i = 0; i < r; i++) { for (let j = 0; j < c; j++) { let index = i * c + j; if ((i === 0 && (1 << index) & state) || (i !== 0 && copyMat[i-1][j])) { // console.log(i, j); flipCnt++; flipMatrix(copyMat, i, j, r, c); } } } if (copyMat.every(col => col.every(item => !item))) return flipCnt; } return -1; };
相关文章
- 尝试十种作法 让你离牛逼程序猿更进一步
- 如何选择大数据应用程序
- 让PHP程序员工作更高效的四大神器
- 云计算是否会减少数据中心的工作机会
- 编程涉及到的同步、异步、阻塞和非阻塞对比简介
- 程序员都应该学写“规范”的代码
- 也谈C#之Json,从Json字符串到类代码
- 文本分析了4000万条Stack Overflow讨论帖,这些是程序员最推荐的编程书(附代码)
- 他从谷歌和Facebook学到八大生活经验
- 为什么要使用R语言?历数R的优势与缺点
- 又是数据与分析,研究发现60%的高管认为他们在分析方面的支出将会提升
- 程序员学会八大开发技巧 涨薪不是问题
- 技术人必读:从编程到管理——程序员的晋升之路
- 程序员获取新编程技能必备这些技巧
- 具备这些特性 说明你是个优秀程序员
- 面对糟糕的旧代码 千万不要重写
- 信锐技术企业级Wi-Fi 最安全 会营销
- 程序员反是最痛恨软件的人 这是为什么
- 【干货】全球大数据领域开源工具汇总
- 大数据的提升:Hadoop即服务的迅猛发展