Trung tâm cá nhân
sách gpt4 ai đã đi

[Thuật toán Ninja] Từ Minesweeper đến các phép toán ma trận: Khám phá bài toán Matrix Zeroing | LeetCode73 Matrix Zeroing

In lại 作者：撒哈拉 更新时间：2025-02-08 21:15:54 59 4
mua khóa gpt4 Nike

从扫雷游戏到矩阵操作：探索矩阵置零问题

生活中的算法

想象你在玩扫雷游戏，当你点到一个地雷时，不仅这个格子会被标记，与它同行同列的格子也都会受到影响。或者想象一个办公室的座位表，如果某个位置发现了感染者，为了安全起见，需要将该员工所在的整行（同排同事）和整列（对面同事）都标记为密切接触者需要检测.

这种"一点触发，全行全列响应"的场景在生活中很常见:

  • 学校课程表中，如果某个老师请假，那一整行的课程都需要调整
  • 表格处理软件中，调整某个单元格的格式，可以统一设置整行整列
  • 影院选座系统中，如果一个座位损坏，可能需要锁定那一排和那一列的预订功能

Mô tả vấn đề

LeetCode第73题"矩阵置零"是这样描述的：给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法.

Ví dụ:

输入：matrix = [ [1,1,1], [1,0,1], [1,1,1] ] 输出：[ [1,0,1], [0,0,0], [1,0,1] ]

最直观的解法：额外空间标记

就像在处理办公室防疫时，先用一张新表记录下所有需要检测的位置，然后统一处理.

让我们用一个简单的例子来理解:

原矩阵： [1,2,0] [3,4,5] 1. 记录0所在的位置： - 第0行，第2列有个0 2. 标记需要置零的行和列： - 需要置零的行：[0] - 需要置零的列：[2] 3. 根据记录修改矩阵： [0,0,0] // 第0行全置零 [3,4,0] // 第2列置零

优化解法：原地标记

仔细思考会发现，我们可以用矩阵的第一行和第一列来记录标记信息，就像用办公室的墙上的记事板来标记需要处理的区域。这样就不需要额外的空间了.

原地标记的原理

  1. 先记录第一行和第一列是否原本包含0
  2. 用第一行和第一列作为标记板
  3. 处理剩余的矩阵
  4. 最后根据第一步的记录处理第一行和第一列

示例演示

用下面的矩阵来说明:

[1,2,3] [4,0,6] [7,8,9] 1. 记录第一行和第一列的状态： - 第一行没有0 - 第一列没有0 2. 用第一行和第一列标记： - 因为matrix[1][1]=0，所以： - 标记第一行：matrix[0][1]=0 - 标记第一列：matrix[1][0]=0 3. 根据标记处理矩阵主体： [1,0,3] [0,0,0] [7,0,9] 4. 最后根据第一步的记录处理第一行第一列

Java代码实现

public void setZeroes(int[][] matrix) { if (matrix == null || matrix.length == 0) return; int m = matrix.length; int n = matrix[0].length; // 记录第一行和第一列是否原本包含0 boolean firstRowHasZero = false; boolean firstColHasZero = false; // 检查第一行 for (int j = 0; j < n; j++) { if (matrix[0][j] == 0) { firstRowHasZero = true; break; } } // 检查第一列 for (int i = 0; i < m; i++) { if (matrix[i][0] == 0) { firstColHasZero = true; break; } } // 使用第一行和第一列作为标记 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) { matrix[i][0] = 0; // 标记该行 matrix[0][j] = 0; // 标记该列 } } } // 根据标记处理非第一行第一列的部分 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } // 处理第一行 if (firstRowHasZero) { for (int j = 0; j < n; j++) { matrix[0][j] = 0; } } // 处理第一列 if (firstColHasZero) { for (int i = 0; i < m; i++) { matrix[i][0] = 0; } } }

解法比较

让我们比较这两种方法:

额外空间标记:

  • 时间复杂度：O(m×n)
  • 空间复杂度：O(m+n)
  • 优点：思路清晰，实现简单
  • 缺点：需要额外空间

原地标记:

  • 时间复杂度：O(m×n)
  • 空间复杂度：O(1)
  • 优点：不需要额外空间
  • 缺点：实现稍复杂，需要额外记录第一行列的状态

解题技巧总结

这道题给我们的启发:

  1. 矩阵问题中，往往可以利用矩阵本身来存储信息
  2. 处理特殊情况（如第一行列）时，可以单独考虑
  3. 分步骤处理复杂问题可以让思路更清晰
  4. 在修改数据时，注意保护原始信息

类似的问题还有:

  • 生命游戏
  • 旋转图像
  • 岛屿数量

bản tóm tắt

通过矩阵置零这道题，我们学会了如何巧妙地利用矩阵本身来存储信息，避免使用额外空间。这种思维方式不仅适用于本题，在处理需要原地修改数据的矩阵问题时都很有启发。记住，当遇到需要在矩阵中标记信息的问题时，考虑能否利用矩阵本身的某些位置来存储标记！ 。

作者：忍者算法 公众号：忍者算法 。

我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～ 。

完整GitHub项目 。

最后此篇关于【忍者算法】从扫雷游戏到矩阵操作：探索矩阵置零问题｜LeetCode73矩阵置零的文章就讲到这里了,如果你想了解更多关于【忍者算法】从扫雷游戏到矩阵操作：探索矩阵置零问题｜LeetCode73矩阵置零的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

59 4 0
Bài viết được đề xuất: Thực hành RocketMQ—7. Triển khai cụm sản xuất và các tham số sản xuất
Bài viết được đề xuất: Tìm hiểu cách triển khai DeepSeek cục bộ trong 1 phút, ngay cả người mới cũng có thể làm được!
Bài viết được đề xuất: DeepSeek không còn bị đóng băng nữa và máy chủ đang bận. Vui lòng thử lại sau (khuyến nghị để thu thập!)
Bài viết được đề xuất: Xây dựng trợ lý AI của riêng bạn trong năm phút: Hướng dẫn tích hợp sâu Ollama+DeepSeek+AnythingLLM
Sa mạc Sahara
Hồ sơ cá nhân

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá Didi Taxi miễn phí
Mã giảm giá Didi Taxi
Các bài viết nóng hổi trên toàn bộ trang web
Giấy chứng nhận ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com