LeetCode每日一题——1582. 二进制矩阵中的特殊位置

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

题目

给你一个大小为 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

提示:

rows == mat.length

cols == mat[i].length

1 <= rows, cols <= 100

mat[i][j] 是 0 或 1

思路

暴力搜索所有位置,发现1后将1先换成0,再判断所在行和列是否元素都为0,由于对列的判断稍有点复杂,这里可以引入transpose,将矩阵转置判断行即可。最后需要将修改的元素恢复至1。

题解

from numpy import transpose
class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        ans = 0
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j] == 1:
                    mat[i][j] = 0
                    # 矩阵转置
                    temp = transpose(mat)
                    # 判断行和列是否都没有1
                    if 1 not in temp[j] and 1 not in mat[i]:
                        ans += 1
                    # 恢复
                    mat[i][j] = 1
        return ans
目录
相关文章
|
2月前
|
存储 算法 NoSQL
LeetCode第73题矩阵置零
文章介绍了LeetCode第73题"矩阵置零"的解法,通过使用矩阵的第一行和第一列作为标记来记录哪些行或列需要置零,从而在不增加额外空间的情况下解决问题。
LeetCode第73题矩阵置零
|
2月前
|
算法 Java
LeetCode第67题二进制求和
这篇文章是关于LeetCode第67题二进制求和的解题思路和代码实现的分享。作者通过分析题目要求和二进制加法的规则,提供了一个Java语言的解决方案,并在最后总结了二进制在算法中的重要性。
LeetCode第67题二进制求和
|
2月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
41 6
|
2月前
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
27 4
|
2月前
|
算法 Python
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
20 0
【Leetcode刷题Python】73. 矩阵置零
|
4月前
|
算法
力扣经典150题第三十七题:矩阵置零
力扣经典150题第三十七题:矩阵置零
27 2
|
4月前
力扣随机一题 6/28 数组/矩阵
力扣随机一题 6/28 数组/矩阵
38 0
|
4月前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
4月前
|
算法
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
|
4月前
|
机器学习/深度学习 算法 数据挖掘
LeetCode题目74:搜索二维矩阵
LeetCode题目74:搜索二维矩阵