X

LEETCODE 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix 解题思路分析

题目大意:

转化为全零矩阵的最少反转次数

给你一个 m x n 的二进制矩阵 mat。

每一步,你可以选择一个单元格并将它反转(反转表示 0 变 1 ,1 变 0 )。如果存在和它相邻的单元格,那么这些相邻的单元格也会被反转。(注:相邻的两个单元格共享同一条边。)

请你返回将矩阵 mat 转化为全零矩阵的最少反转次数,如果无法转化为全零矩阵,请返回 -1 。

二进制矩阵的每一个格子要么是 0 要么是 1 。

全零矩阵是所有格子都为 0 的矩阵。

示例 1:

输入:mat = [[0,0],[0,1]]
输出:3
解释:一个可能的解是反转 (1, 0),然后 (0, 1) ,最后是 (1, 1) 。

示例 2:

输入:mat = [[0]]
输出:0
解释:给出的矩阵是全零矩阵,所以你不需要改变它。

示例 3:

输入:mat = [[1,1,1],[1,0,1],[0,0,0]]
输出:6

示例 4:

输入:mat = [[1,0,0],[1,0,0]]
输出:-1
解释:该矩阵无法转变成全零矩阵

提示:

  • m == mat.length
  • n == mat[0].length
  • 1 <= m <= 3
  • 1 <= n <= 3
  • mat[i][j] 是 0 或 1 。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1284

解题思路分析:

这是一道变形的广度优先搜索bfs题目,在matrix当前状态下,我们有m*n种变换的可能性,m和n为矩阵的长和宽。分别变换矩阵上的每一个点,将变换后的状态存入到Queue中,便于下一次的变换。另外建立一个visited列表,避免重复操作,记录下已经变换过的状态,如果再遇到该状态可以无视。因为matrix最大是3乘3,数量级很小,我们可以利用二进制数来记录当前状态。比如[[1,0],[0,1]]可以记录为1001。同理[[0,0],[0,0]]为0。

当bfs中遇到状态为0时,说明已经找到结果,返回当前步数即可。

实现代码:

public int minFlips(int[][] mat) {
    Queue<int[][]> q = new LinkedList<>(); // bfs用的Queue
    List<Integer> visited = new ArrayList<>(); // 记录已访问过的状态
    // 如果当前mat的状态为0(全0矩阵),返回0。
    if(getKey(mat)==0) return 0;
    // 将当前状态存入已访问数组
    visited.add(getKey(mat));
    // 将当前矩阵加入Queue
    q.offer(mat);
    // 返回结果
    int res=0;
    // 以下为bfs常规操作
    // 当Queue数量大于0,一直bfs。
    while(q.size()>0){
        // 当前Queue的size
        int count=q.size();
        // 循环count次
        while(count-->0){
            // 取出queue中的一个矩阵
            int[][] m = q.poll();
            // 循环矩阵每一个点,对该点及四周进行变换操作
            for(int i=0;i<m.length;i++){
                for(int j=0;j<m[0].length;j++){
                    // 注意不要在原数组上进行操作。
                    // 先copy一份当前矩阵
                    int[][] copy=Arrays
                    .stream(m).map(el->el.clone()).toArray($->m.clone());
                    // 变换矩阵当前点的值
                    copy[i][j]=(copy[i][j]==1?0:1);
                    // 变换当前点四周的值(如果四周存在)
                    if(i>0) copy[i-1][j]=(copy[i-1][j]==1?0:1);
                    if(i<m.length-1) copy[i+1][j]=(copy[i+1][j]==1?0:1);
                    if(j>0) copy[i][j-1]=(copy[i][j-1]==1?0:1);
                    if(j<m[0].length-1) copy[i][j+1]=(copy[i][j+1]==1?0:1);
                    // 计算变换后的状态
                    int key=getKey(copy);
                    // 如果状态为0,返回。
                    if(key==0) return res+1;
                    // 若该状态不在已访问列表中
                    if(!visited.contains(key)){
                        // 将该状态存入已访问列表
                        visited.add(key);
                        // 将当前修改后的矩阵存入Queue
                        q.offer(copy);
                    }
                }
            }
        }
        res++; // 返回结果加一
    }
    return -1;
}
int getKey(int[][] m){
    int key=0;
    for(int i=0;i<m.length;i++){
        for(int j=0;j<m[0].length;j++){
            key|= (m[i][j]<<(i*m[0].length+j));
        }
    }
    return key;
}

本题解法执行时间为13ms。

Runtime: 13 ms, faster than 100.00% of Java online submissions for Minimum Number of Flips to Convert Binary Matrix to Zero Matrix.

Memory Usage: 36.2 MB, less than 100.00% of Java online submissions for Minimum Number of Flips to Convert Binary Matrix to Zero Matrix.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1284-minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix-解题思路分析/
Categories: leetcode
kwantong: