LeetCode 面试题 01.08. 零矩阵

这篇具有很好参考价值的文章主要介绍了LeetCode 面试题 01.08. 零矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题目

  编写一种算法,若M × N矩阵中某个元素为0,则将其所在的行与列清零。

  点击此处跳转题目。

示例 1:

输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]

示例 2:

输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

二、C# 题解

  此题有很多方法解,无外乎都是记录需要清零的行与列,这种写法太无聊了。这里提出一种递归的方式,只需要遍历矩阵一次即可。当遇到 0 时,使用 set0 变量记录该位置,遍历完成后,重置所有 set0

public class Solution {
    public void SetZeroes(int[][] matrix) {
        BFS(ref matrix, 0, 0); // 广度优先遍历
    }

    public void BFS(ref int[][] matrix, int i, int j) {
        int m = matrix.Length, n = matrix[0].Length;

        if (i == m && j == 0) return; // 递归出口

        // 计算下一个位置
        int next_i = i, next_j = j + 1;
        if (next_j == n) {
            next_j = 0;
            next_i++;
        }

        bool set0 = matrix[i][j] == 0;   // 记录当前状态,是否需要清零

        BFS(ref matrix, next_i, next_j); // 继续遍历

        // 最后执行清零
        if (set0) {
            for (int p = 0; p < n; p++) matrix[i][p] = 0;
            for (int q = 0; q < m; q++) matrix[q][j] = 0;
        }
    }
}
  • 时间复杂度: O ( m × n ) O(m\times n) O(m×n)
  • 空间复杂度:由矩阵中 0 出现的次数决定。

  该方法依据元素记录,因此当矩阵中 0 出现次数过多时,会有重复操作,只适合处理稀疏 0 矩阵。

  矩阵中 0 过于密集时,使用记录行列的方式会更好些,但可能需要更多的空间和遍历次数。文章来源地址https://www.toymoban.com/news/detail-669284.html

到了这里,关于LeetCode 面试题 01.08. 零矩阵的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2023-08-01 LeetCode每日一题(英雄的力量)

    点击跳转到题目位置 给你一个下标从 0 开始的整数数组 nums ,它表示英雄的能力值。如果我们选出一部分英雄,这组英雄的 力量 定义为: i 0 ,i 1 ,… i k 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i0],nums[i1] … nums[ik])2 * min(nums[i0],nums[i1] … nums[ik]) 。 请你

    2024年02月14日
    浏览(60)
  • LeetCode 面试题 02.08. 环路检测

      给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。若环不存在,请返回 null 。   如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索

    2024年02月10日
    浏览(34)
  • LeetCode 面试题 16.08. 整数的英语表示

      给定一个整数,打印该整数的英文描述。 示例 1: 输入: 123 输出: “One Hundred Twenty Three” 示例 2: 输入: 12345 输出: “Twelve Thousand Three Hundred Forty Five” 示例 3: 输入: 1234567 输出: “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven” 示例 4: 输入: 1234567891 输出: “One Billi

    2024年02月06日
    浏览(33)
  • LeetCode 面试题 04.08. 首个共同祖先

      设计并实现一个算法,找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意:这不一定是二叉搜索树。   例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]   点击此处跳转题目。 示例 1: 输入: root = [3,5,1,6,2,0,8,null,null,7,

    2024年02月08日
    浏览(37)
  • leetcode 542. 01 Matrix(01矩阵)

    矩阵中只有0,1值,返回每个cell到最近的0的距离。 思路: 0元素到它自己的距离是0, 只需考虑1到最近的0是多少距离。 BFS. 先把元素1处的距离更新为无穷大。 0的位置装入queue。 从每个0出发,走上下左右4个方向,遇到0不需要处理,遇到1,距离为当前距离+1. 如果当前距离

    2024年02月12日
    浏览(39)
  • LeetCode 面试题 17.08 —— 马戏团人塔

    首先,我们对人的身高按照从小到大排序, 特别注意,对于身高相等的人,要按照体重从高到低排序 。这时候,序列已经满足了在上面的人要比下面的人矮一点,然后,我们只需要保证提取到一个最长的体重的上升子序列即可。这一步骤也就是 LeetCode 300——最长上升子序列

    2024年04月28日
    浏览(28)
  • leetcode 542. 01 矩阵

    给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。 示例 1: 输入:mat = [[0,0,0],[0,1,0],[0,0,0]] 输出:[[0,0,0],[0,1,0],[0,0,0]] 示例 2: 输入:mat = [[0,0,0],[0,1,0],[1,1,1]] 输出:[[0,0,

    2024年02月16日
    浏览(34)
  • LeetCode 面试题 01.01. 判定字符是否唯一

      实现一个算法,确定一个字符串 s 的所有字符是否全都不同,点击此处跳转。 示例 1: 输入: s = “leetcode” 输出: false 示例 2: 输入: s = “abc” 输出: true 限制: 0 = len(s) = 100 s[i] 仅包含小写字母 如果你不使用额外的数据结构,会很加分。   使用数组记录出现次数,时

    2024年02月12日
    浏览(36)
  • 【每日一题】Leetcode - 面试题 17.08. Circus Tower LCCI

    Leetcode - 面试题 17.08. Circus Tower LCCI Sorting heights to be ascending order and weights to be descending order. dp[i] = j represents person[i] as the bottom of tower, the tower height is amount of j, to calculate the dp[i] we find the maximum of dp[0 ~ (i-1)] what the person[0 ~ (i-1)] shorter and lighter than person[i], increase it of one, it’s th

    2024年02月13日
    浏览(44)
  • LeetCode 面试题 04.01. 节点间通路

      节点间通路。给定有向图,设计一个算法,找出两个节点之间是否存在一条路径。   点击此处跳转题目。 示例1: 输入: n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2 输出: true 示例2: 输入: n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3],

    2024年02月09日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包