Java C++ leetcode面试零矩阵

目录
  • 题目要求
  • 思路：模拟
    • Java
    • C++
    • Rust
  • 总结

题目要求

思路：模拟

  • 定义两个数组分别记录每行or每列中为0的元素；
  • 0所在的行列清零也就意味着元素所在行or列有0则置零【废话连篇】；
  • 所以一次遍历找出有0的行列，一次遍历根据其将相应元素置零。

Java

class Solution {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        boolean[] rows = new boolean[n], cols = new boolean[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                if (matrix[i][j] == 0)
                    rows[i] = cols[j] = true;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                if (rows[i] || cols[j])
                    matrix[i][j] = 0;
        }
    }
}
  • 时间复杂度：O(n×m)
  • 空间复杂度：O(n+m)

C++

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        bool rows[n], cols[m];
        memset(rows, 0, sizeof(rows));
        memset(cols, 0, sizeof(cols));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                if (matrix[i][j] == 0)
                    rows[i] = cols[j] = true;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                if (rows[i] || cols[j])
                    matrix[i][j] = 0;
        }
    }
};
  • 时间复杂度：O(n×m)
  • 空间复杂度：O(n+m)

Rust

impl Solution {
    pub fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
        let (n, m) = (matrix.len(), matrix[0].len());
        let (mut rows, mut cols) = (vec![false; n], vec![false; m]);
        for i in 0..n {
            for j in 0..m {
                if matrix[i][j] == 0 {
                    rows[i] = true;
                    cols[j] = true;
                }
            }
        }
        for i in 0.. n {
            for j in 0..m {
                if rows[i] || cols[j] {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}
  • 时间复杂度：O(n×m)
  • 空间复杂度：O(n+m)

总结

因为是中等题所以纠结了半天是不是有什么精巧奇妙的算法解题……emmmm结果就只是通过修改给出数组来标记，空间复杂度能降到常数了，有意义但不大

以上就是Java C++ leetcode面试零矩阵的详细内容，更多关于Java C++ 面试零矩阵的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C C++ 题解LeetCode2360图中的最长环示例

    C C++ 题解LeetCode2360图中的最长环示例

    目录 题目描述 整理题意 解题思路分析 具体实现 复杂度分析 代码实现 总结 题目描述 题目链接:2360. 图中的最长环 给你一个 n 个节点的 有向图 ,节点编号为 0 到 n - 1 ,其中每个节点 至多 有一条出边. 图用一个大小为 n 下标从 0 开始的数组 edges 表示,节点 i 到节点 edges[i] 之间有一条有向边.如果节点 i 没有出边,那么 edges[i] == -1 . 请你返回图中的 最长 环,如果没有任何环,请返回 -1 . 一个环指的是起点和终点是 同一个 

  • C++ LeetCode1832题解判断句子是否为全字母句

    目录 LeetCode 1832.判断句子是否为全字母句 方法一:统计 AC代码 C++ LeetCode 1832.判断句子是否为全字母句 力扣题目链接:leetcode.cn/problems/ch… 全字母句 指包含英语字母表中每个字母至少一次的句子. 给你一个仅由小写英文字母组成的字符串 sentence ,请你判断 sentence 是否为 全字母句 . 如果是,返回 true :否则,返回 false . 示例 1: 输入:sentence = "thequickbrownfoxju

  • C++ LeetCode0547题解省份数量图的连通分量

    目录 LeetCode 547.省份数量 方法一:BFS求图的连通分量 AC代码 C++ LeetCode 547.省份数量 力扣题目链接:leetcode.cn/problems/nu… 有 n 个城市,其中一些彼此相连,另一些没有相连.如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连. 省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市. 给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i

  • C C++ 题解LeetCode1417重新格式化字符串

    目录 题目描述 整理题意 解题思路分析 具体实现 复杂度分析 代码实现 总结 题目描述 题目链接:1417. 重新格式化字符串 给你一个混合了数字和字母的字符串 s,其中的字母均为小写英文字母. 请你将该字符串重新格式化,使得任意两个相邻字符的类型都不同.也就是说,字母后面应该跟着数字,而数字后面应该跟着字母. 请你返回 重新格式化后 的字符串:如果无法按要求重新格式化,则返回一个 空字符串 . 提示: 1⩽s.length⩽5001 s 仅由小写英文字母和/或数字组成. 示例 1: 输入:s

  • Java C++题解leetcode902最大为N的数字组合数位DP

    目录 题目要求 阅读理解 思路:数位DP Java C++ 总结 题目要求 题目链接 阅读理解 思路:数位DP Java class Solution { public int atMostNGivenDigitSet(String[] digits, int n) { // 转存digits int[] nums = new int[digits.length]; for (int i = 0; i < digits.length; i++) nums[i] = Integer.parseIn

  • C++ LeetCode1945题解字符串转化后的各位数字之和

    目录 1945.字符串转化后的各位数字之和 方法一:计算 AC代码 C++ 1945.字符串转化后的各位数字之和 力扣题目链接:leetcode.cn/problems/su… 给你一个由小写字母组成的字符串 s ,以及一个整数 k . 首先,用字母在字母表中的位置替换该字母,将 s 转化 为一个整数(也就是,'a' 用 1 替换,'b' 用 2 替换,... 'z' 用 26 替换).接着,将整数 转换 为其 各位数字之和 .共重复 转换 操作 k 次 . 例如,如果 s = "zbax&qu

  • Java C++题解leetcode915分割数组示例

    目录 题目要求 思路一:两次遍历 Java C++ Rust 思路二:一次遍历 Java C++ Rust 题目要求 题目链接 思路一:两次遍历 题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值,那么就找这个分界点就好: 首先从后向前遍历,找[i,n−1]里最小的值: 然后从前向后遍历,找[0,i]里最大的值: 然后找满足max[i]<=min[i+1]的分割点i: 可以将2.3两步结合为一步完成,由于iii从前向后不断增大,所以用后面(较大)的值覆盖更新之前的值. 找到分界点的索引

  • Java C++ leetcode面试零矩阵

    目录 题目要求 思路:模拟 Java C++ Rust 总结 题目要求 思路:模拟 定义两个数组分别记录每行or每列中为0的元素: 0所在的行列清零也就意味着元素所在行or列有0则置零[废话连篇]: 所以一次遍历找出有0的行列,一次遍历根据其将相应元素置零. Java class Solution { public void setZeroes(int[][] matrix) { int n = matrix.length, m = matrix[0].length; boolean[] row

  • Java持久层面试题目及答案整理

    什么是ORM? 对象关系映射(Object-Relational Mapping,简称ORM)是一种为了解决程序的面向对象模型与数据库的关系模型互不匹配问题的技术: 简单的说,ORM是通过使用描述对象和数据库之间映射的元数据(在Java中可以用XML或者是注解),将程序中的对象自动持久化到关系数据库中或者将关系数据库表中的行转换成Java对象,其本质上就是将数据从一种形式转换到另外一种形式. Hibernate中SessionFactory是线程安全的吗?Session是线程安全的吗(两个线程能

  • java中Hibernate面试知识点整理

    作为常用的框架之一,Hibernate在面试的时候难免会被问到.好在涉及的都是一些理论方面的知识点,比如概念.原理.使用之类的.我们在面试之前可以针对这方面的题目,做一个充足的准备,即使有些人对hibernate框架的了解并不深入.下面我们就hibernate框架中常见的面试题带来介绍. 1. 为什么要使用 hibernate? (1).对JDBC做了轻量级的封装,简化了数据访问层编码. (2).Hibernate是一个ORM框架,开发者可以使用面向对象的思想操作数据库,使用更加方便. (3)

  • Java实现LeetCode（两数之和）

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回[0, 1] 思路一:最直接的思维,两次遍历查询,时间复杂度O(N*N). 代码: public static int[] twoSum1(int[] nums, int target) { int[] label =

  • Java实现LeetCode（螺旋矩阵）

    LeetCode54. 螺旋矩阵 java实现 题目 难度 中 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素. 示例 1: 输入:  [   [ 1, 2, 3 ],   [ 4, 5, 6 ],   [ 7, 8, 9 ]  ]  输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入:  [    [1, 2, 3, 4],    [5, 6, 7, 8],    [9,10,11,12]  ] 输出: [1,2,3,4,8

  • Java实现LeetCode（报数）

    Java实现LeetCode（报数）

    题目如下: public String countAndSay(int n) { if(n == 1){ return "1"; } //递归调用,然后对字符串处理 String str = countAndSay(n-1) + "*";//为了str末尾的标记,方便循环读数 char[] c = str.toCharArray(); int count = 1; StringBuilder s = new StringBuilder(); for(int i =

  • Java实现LeetCode（组合总和）

    leetcode题目 组合总和 -- leetcode 39 题目描述 给定一个无重复元素的数组 candidates 和一个目标数 target , 找出 candidates 中所有可以使数字和为 target 的组合. candidates 中的数字可以无限制重复被选取. 说明: 所有数字(包括 target)都是正整数. 解集不能包含重复的组合.  示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [   [7],   [2,2,3

  • Java 深入分析链表面试实例题目

    Java 深入分析链表面试实例题目

    目录 链表面试题一 问题描述: 问题分析: 问题讲解: 代码实现: 链表面试题二 问题描述: 问题分析: 问题讲解: 代码实现: 链表面试题一 判断链表是否是回文结构. 问题描述: 兄弟们,看图理解什么是链表的回文结构: 回文结构:正着读12 -> 23 ->34,倒着读12->23->34 奇数偶数都可以: 问题分析: 要判断是不是回文结构,那么我们就要遍历链表,一个从前往后走,一个从后往前走,对应的val值要相同,那么我们就必须修改链表的指向,这里就要用到快慢指针帮我们找到中间

  • Java C++ leetcode执行一次字符串交换能否使两个字符串相等

    Java C++ leetcode执行一次字符串交换能否使两个字符串相等

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 Java class Solution { public boolean areAlmostEqual(String s1, String s2) { if (s1.length() != s2.length()) return false; int a = -1, b = -1; for (int i = 0; i < s1.length(); i++) { if (s1.charAt(i) == s2.charAt

  • java锁synchronized面试常问总结

    目录 synchronized都问啥? synchronized是什么? synchronized锁什么? synchronized怎么用? 结语 synchronized都问啥? 如果Java面试有什么是必问的,synchronized必定占据一席之地.初出茅庐时synchronized的用法,成长后synchronized的原理,可谓是Java工程师的“一生之敌”. 按照惯例,先来看synchronized的常见问题(在线Excel同步更新中): 根据统计数据可以总结出synchronize

随机推荐