Java C++ 算法题解leetcode1582二进制矩阵特殊位置

2024-05-03 07:13:42

题目要求

思路：模拟

直接按题意模拟，先算出每行每列中“111”的个数，然后判断统计行列值均为111的位置即可。

Java

class Solution {
    public int numSpecial(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        int res = 0;
        int[] row = new int[n], col = new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                row[i] += mat[i][j];
                col[j] += mat[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 1 && row[i] == 1 && col[j] == 1)
                    res++;
            }
        }
        return res;
    }
}

时间复杂度：O(m×n)
空间复杂度：O(m+n)

C++

class Solution {
public:
    int numSpecial(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        int res = 0;
        vector<int> row(n), col(m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                row[i] += mat[i][j];
                col[j] += mat[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 1 && row[i] == 1 && col[j] == 1)
                    res++;
            }
        }
        return res;
    }
};

时间复杂度：O(m×n)
空间复杂度：O(m+n)

Rust

这里的迭代函数用得不是很熟练，参考了好多才勉强理解下来。

impl Solution {
    pub fn num_special(mat: Vec<Vec<i32>>) -> i32 {
        let row = mat.iter().map(|row| row.iter().sum::<i32>()).collect::<Vec<_>>();
        let col = (0..mat[0].len()).map(|i| mat.iter().map(|col| col[i]).sum::<i32>()).collect::<Vec<_>>();
        (0..mat.len()).fold(0, |res, i| res + (0..mat[i].len()).filter(|&j| mat[i][j] == 1 && row[i] == 1 &&col[j] == 1).count() as i32)
    }
}

时间复杂度：O(m×n)
空间复杂度：O(m+n)

以上就是Java C++ 算法题解leetcode1582二进制矩阵特殊位置的详细内容，更多关于Java C++ 二进制矩阵特殊位置的资料请关注我们其它相关文章！

Java C++题解leetcode672灯泡开关示例

目录题目要求思路:找规律 Java C++ Rust 总结题目要求思路:找规律找到尽可能最精简的通项表达,今日参考:京城打工人首先,归纳每个开关会影响的灯,其中(k=0,1,2,…): 开关反转灯编号一 k 二 2k 三 2k+1 四 3k+1 可见灯以6盏为周期具有相同变化,所以以下只需要推导第一个周期里的6盏灯即可. 观察前6盏灯: 灯开关 1 一.三.四 2 一.二 3 一.三 4 一.二.四 5 一.三 6 一.二发现灯2.6和3.5分别受同样的开关影响,所以状态相同
Java C++算法题解leetcode1592重新排列单词间的空格

目录题目要求思路:模拟 Java C++ Rust 题目要求思路:模拟模拟就完了统计空格数量和单词数量,计算单词间应有的空格数,将它们依次放入结果字符串,若有余数则在末尾进行填补. Java class Solution { public String reorderSpaces(String text) { int n = text.length(), spcnt = 0; List<String> words = new ArrayList<>(); for (int
Java C++题解leetcode消失的两个数字实例

目录题目要求思路:数学推导 Java C++ Rust 总结题目要求思路:数学推导不重复的数组序列可以根据高斯公式计算所有元素的总和: 用当前数组长度加上两个缺失的数字可以得到所有数字长度,即可应用公式. 减去当前数组和即可得到缺失数字和sumsumsum: 两个缺失的数字分别位于m=sum2m=\frac{sum}{2}m=2sum两边: 遍历当前数组中所有小于(或大于)mmm的值,找到缺失的一个: 同样利用两个“和”的差值得到: 利用sumsumsum即可得到另一个. Java c
Java C++题解 leetcode第k个数实例

目录题目要求思路一:小根堆 Java C++ 思路二:多路归并[多指针] Java C++ Rust 总结题目要求思路一:小根堆中文题目描述不太清晰,但其实由题目可以发现,当x满足条件时,3x.5x.7x分别也都满足条件. 将满足条件的数依次放入优先队列存放用于后续计算,由于每次要取待计算队列中最小的数x,所以定义小根堆: 弹出x,计算3x.5x.7x并入队: 用一个哈希表记录防止重复入队. 每次取数(pop)时进行计数,到第k次结束,当前队首即为答案. Java <学到了> 1L也
Java C++题解leetcode判定是否为字符重排

目录题目要求思路一:排序 Java C++ Rust 思路二:词频统计 Java C++ Rust 总结题目要求思路一:排序 Java class Solution { public boolean CheckPermutation(String s1, String s2) { if(s1.length() != s2.length()) return false; char[] sort1 = s1.toCharArray(); Arrays.sort(sort1); char[]
Java C++ 题解leetcode1619删除某些元素后数组均值

目录题目要求思路:模拟 Java C++ Rust 题目要求思路:模拟根据题意模拟即可: 排序然后只取中间符合条件的数加和然后计算均值: 根据给出的数组长度n为20的倍数,5%可直接取n/20: 两边各去除5%,则剩余长度为0.9n. Java class Solution { public double trimMean(int[] arr) { Arrays.sort(arr); int n = arr.length, tot = 0; for (int i = n / 20; i
Java C++ 算法题解leetcode1582二进制矩阵特殊位置

目录题目要求思路:模拟 Java C++ Rust 题目要求思路:模拟直接按题意模拟,先算出每行每列中“111”的个数,然后判断统计行列值均为111的位置即可. Java class Solution { public int numSpecial(int[][] mat) { int n = mat.length, m = mat[0].length; int res = 0; int[] row = new int[n], col = new int[m]; for (int i =
Java C++ 算法题解leetcode145商品折扣后最终价格单调栈

目录题目要求思路一:暴力模拟 Java C++ Rust 思路二:单调栈 Java C++ Rust 题目要求思路一:暴力模拟由于数据范围不算离谱,所以直接遍历解决可行. Java class Solution { public int[] finalPrices(int[] prices) { int n = prices.length; int[] res = new int[n]; for (int i = 0; i < n; i++) { int discount = 0; fo
Java C++ 算法题解leetcode669修剪二叉搜索树示例

目录题目要求思路一:模拟迭代 Java C++ 思路二:递归 Java C++ Rust 题目要求思路一:模拟迭代依次判断每个节点是否合法: 首先找出结果的根,若原根小了就拉右边的过来,大了拉左边的过来做新根: 然后分别判断左右子树的大小,由于二叉搜索树的性质,子树只需要判断一边就好: 左子树判断是否>low,合法就向左下走,不合法往右下: 右子树判断是否<high,合法就向右下走,不合法往左下. Java class Solution { public TreeNode trimBS
Java C++ 算法题解leetcode1608特殊数组特征值

目录题目要求思路一:枚举 + 二分 Java C++ 思路二:二分枚举 Java C++ 思路三:倒序枚举 Java C++ 题目要求思路一:枚举 + 二分逐一枚举值域内的所有值,然后二分判断是否合法. Java class Solution { public int specialArray(int[] nums) { Arrays.sort(nums); int n = nums.length; for (int x = 0; x <= nums[n - 1]; x++) { //
Java C++算法题解leetcode801使序列递增的最小交换次数

目录题目要求思路:状态机DP 实现一:状态机 Java C++ Rust 实现二:滚动数组 Java C++ Rust 总结题目要求思路:状态机DP 实现一:状态机 Java class Solution { public int minSwap(int[] nums1, int[] nums2) { int n = nums1.length; int[][] f = new int[n][2]; for (int i = 1; i < n; i++) f[i][0] = f[i][1]
java算法题解牛客BM99顺时针旋转矩阵示例

目录题目描述解题思路实践代码解法1 解法2 题目描述 BM99 顺时针旋转矩阵描述有一个NxN整数矩阵,请编写一个算法,将矩阵顺时针旋转90度. 给定一个NxN的矩阵,和矩阵的阶数N,请返回旋转后的NxN矩阵. 数据范围:0<n<300,矩阵中的值满足0≤val≤1000 要求:空间复杂度 O(N^2),时间复杂度 O(N^2) 进阶:空间复杂度 O(1),时间复杂度 O(N^2) 示例1输入:[[1,2,3],[4,5,6],[7,8,9]],3返回值:[[7,4,1],[8,5
java算法题解Leetcode15三数之和实例

目录题目解题思路题目 15. 三数之和给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例 1:输入:nums = [-1,0,1,2,-1,-4]输出:[[-1,-1,2],[-1,0,1]]示例 2:输入:nums = []输出:[]示例 3:输入:nums = [0]输出:[]提示:0 <= nums.length <=
java回溯算法解数独问题

本文实例为大家分享了java回溯算法解数独问题,供大家参考,具体内容如下下面来详细讲一下如何用回溯算法来解数独问题. 下图是一个数独题,也是号称世界上最难的数独.当然了,对于计算机程序来说,只要算法是对的,难不难就不知道了,反正计算机又不累.回溯算法基本上就是穷举,解这种数独类的问题逻辑比较简单. 不管算法懂不懂,先把类建出来,变量定义好,那放大学试卷上就是可以拿两分了. package shudu; /** * Created by wolf on 2016/3/17. */ public
java实现的顺时针/逆时针打印矩阵操作示例

java实现的顺时针/逆时针打印矩阵操作.分享给大家供大家参考,具体如下: public class SnakeMatrix { /** * 定义矩阵的阶数 */ private int n; //填充矩阵的值 private int k = 1; private int[][] data; /** * 定义矩阵移动的方向 */ public enum Direction { left, right, up, down, } SnakeMatrix(int n) { this.n = n; da

Java C++ 算法题解leetcode1582二进制矩阵特殊位置

目录

题目要求

思路：模拟

Java

C++

Rust

相关推荐

随机推荐