LEETCODE 1582. Special Positions in a Binary Matrix 解题思路分析

题目大意:

二进制矩阵中的特殊位置

给你一个大小为 rows x cols 的矩阵 mat,其中 mat[i][j] 是 0 或 1,请返回 矩阵 mat 中特殊位置的数目 。

特殊位置 定义:如果 mat[i][j] == 1 并且第 i 行和第 j 列中的所有其他元素均为 0(行和列的下标均 从 0 开始 ),则位置 (i, j) 被称为特殊位置。

示例 1:

输入:mat = [[1,0,0],
            [0,0,1],
            [1,0,0]]
输出:1
解释:(1,2) 是一个特殊位置,因为 mat[1][2] == 1 且所处的行和列上所有其他元素都是 0

示例 2:

输入:mat = [[1,0,0],
            [0,1,0],
            [0,0,1]]
输出:3
解释:(0,0), (1,1) 和 (2,2) 都是特殊位置

示例 3:

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

示例 4:

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

提示:

  • rows == mat.length
  • cols == mat[i].length
  • 1 <= rows, cols <= 100
  • mat[i][j] 是 0 或 1

前言:

最近很多朋友私信我,问到为什么最近博客更新变少了?这里统一回复一下,真的非常抱歉,最近接了一个私活,项目很大,而且是从零开始的那种。从项目架构到云服务器搭建,以及数据库设计,api设计,web端,app端甚至各种小程序端都有所涉及。事无巨细,全部亲力亲为,因此实在难以抽出时间来更新刷题博客。这个项目中运用到的技术也很广泛,总结了一下,大概包括以下内容:

SpringBoot,SpringSecurity,MyBatis,MyBatisGenerator,PageHelper,Swagger,Hibernator-Validator,Elasticsearch,RabbitMQ,Redis,MongoDB,Docker,Druid,OSS,JWT,LogStash,Lombok

Vue,Vue-router,Vuex,Element,Axios,v-charts,Js-cookie,nprogress

Android,iOS,MVVM,rx等

如果有时间的话,也很想和大家分享一下目前这个私活中学到的一些知识,希望能对大家有所帮助。虽然项目很忙,但今后我还会每周参加leetcode周赛,并尽量保持每周更新一些周赛题目的讲解。此外本网站的题目还会保持更新,大家可以随时查看leetcode每道题目的公司tag以及加锁题目内容。以下言归正传:

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

解题思路分析:

这道题难度不大,暴力解是可行的,算法优化可以在暴力解的基础上进行改进即可。

理论上我们循环每一个点,如果当前点是0的话跳过,是1的话我们在查看当前行与列上其他点是否都为0即可。优化的点就在于查看当前行与列这一步上。如果每一个点都查看一遍显然效率很低,因此我们可以将数据提前做一个预处理,即先统计出每一行与每一列上数字1的个数。这样一来循环到当前点时,如果是1,并且当前行与列上的1的个数也都是1的话,那么当前点即是特殊位置,返回结果加一即可。

实现代码:

public int numSpecial(int[][] mat) {
    int[] matR=new int[mat.length];
    for(int r=0;r<mat.length;r++){ // 统计每一行中数字1的个数
        for(int c=0;c<mat[0].length;c++){
            if(mat[r][c]==1) matR[r]++;
        }
    }
    int[] matC=new int[mat[0].length];
    for(int c=0;c<mat[0].length;c++){ // 统计每一列中数字1的个数
        for(int r=0;r<mat.length;r++){
            if(mat[r][c]==1) matC[c]++;
        }
    }
    int res=0;
    for(int r=0;r<mat.length;r++){ // 循环每一个点
        for(int c=0;c<mat[0].length;c++){
            // 如果当前点是1,并且当前行与列中1的个数都是1,返回结果加一
            if(mat[r][c]==1&&matR[r]==1&&matC[c]==1) res++;
        }
    }
    return res;
}

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

Runtime: 1 ms, faster than 100.00% of Java online submissions for Special Positions in a Binary Matrix.

Memory Usage: 39.5 MB, less than 75.00% of J

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1582-special-positions-in-a-binary-matrix-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。