新闻详情

新闻详情

首页 / 资讯中心 / 详情

元宝 LeetCode 130. 被围绕的区域 Rust实现

发布时间:2026/11/21 14:37:23来源:尧图网络
元宝    LeetCode 130. 被围绕的区域 Rust实现
这是 LeetCode 130 题 “被围绕的区域” 的 Rust 实现。题目描述给定一个“m x n” 的矩阵“board”由字符“‘X’” 和“‘O’” 组成找到所有被“‘X’” 围绕的区域并将这些区域里所有的“‘O’” 用“‘X’” 填充。注意任何边界上的“‘O’” 以及与边界“‘O’” 相连的“‘O’” 都不会被填充。解题思路DFS深度优先搜索与 Python 版本思路一致采用逆向思维标记边界连通区从矩阵四条边界上的“‘O’” 出发利用 DFS 将所有与边界相连的“‘O’” 临时标记为“‘#’”。原地更新矩阵遍历整个矩阵将剩余的“‘O’”被完全包围的替换为“‘X’”。将标记为“‘#’” 的边界连通区还原为“‘O’”。Rust 注意事项在 Rust 中递归修改二维向量非常安全我们可以把“board” 作为可变引用“mut VecVec” 传入递归函数通过索引直接修改。为了避免“usize” 减法溢出坐标计算使用“i32” 并在访问时转换为“usize”。Rust 代码实现LeetCode 风格核心代码impl Solution {pub fn solve(board: mut VecVec) {if board.is_empty() || board[0].is_empty() {return;}let m board.len() as i32; let n board[0].len() as i32; // 定义 DFS 递归函数 fn dfs(board: mut VecVecchar, r: i32, c: i32) { let m board.len() as i32; let n board[0].len() as i32; // 越界检查 if r 0 || r m || c 0 || c n { return; } let (r_usize, c_usize) (r as usize, c as usize); // 如果不是 O直接返回已访问过或本身是 X if board[r_usize][c_usize] ! O { return; } // 标记为与边界连通 board[r_usize][c_usize] #; // 向四个方向递归 dfs(board, r 1, c); dfs(board, r - 1, c); dfs(board, r, c 1); dfs(board, r, c - 1); } // 从四条边界出发 for i in 0..m { dfs(board, i, 0); // 第一列 dfs(board, i, n - 1); // 最后一列 } for j in 0..n { dfs(board, 0, j); // 第一行 dfs(board, m - 1, j); // 最后一行 } // 重新遍历替换字符 for i in 0..m as usize { for j in 0..n as usize { if board[i][j] O { board[i][j] X; // 被包围的 O 变为 X } else if board[i][j] # { board[i][j] O; // 边界连通的还原为 O } } } }}完整可运行示例含本地测试如果你想在本地运行可以使用以下完整代码包含“main” 函数struct Solution;impl Solution {pub fn solve(board: mut VecVec) {if board.is_empty() || board[0].is_empty() {return;}let m board.len() as i32; let n board[0].len() as i32; fn dfs(board: mut VecVecchar, r: i32, c: i32) { let m board.len() as i32; let n board[0].len() as i32; if r 0 || r m || c 0 || c n { return; } let (r_usize, c_usize) (r as usize, c as usize); if board[r_usize][c_usize] ! O { return; } board[r_usize][c_usize] #; dfs(board, r 1, c); dfs(board, r - 1, c); dfs(board, r, c 1); dfs(board, r, c - 1); } for i in 0..m { dfs(board, i, 0); dfs(board, i, n - 1); } for j in 0..n { dfs(board, 0, j); dfs(board, m - 1, j); } for i in 0..m as usize { for j in 0..n as usize { if board[i][j] O { board[i][j] X; } else if board[i][j] # { board[i][j] O; } } } }}fn print_board(board: VecVec) {for row in board {for ch in row {print!({} , ch);}println!();}println!();}fn main() {// 示例 1let mut board1 vec![vec![‘X’, ‘X’, ‘X’, ‘X’],vec![‘X’, ‘O’, ‘O’, ‘X’],vec![‘X’, ‘X’, ‘O’, ‘X’],vec![‘X’, ‘O’, ‘X’, ‘X’]];println!(“示例1原始矩阵:”);print_board(board1);Solution::solve(mut board1); println!(示例1处理后:); print_board(board1); // 预期输出: // X X X X // X X X X // X X X X // X O X X // 示例 2 let mut board2 vec![vec![X]]; Solution::solve(mut board2); println!(示例2处理后: {:?}, board2); // 输出: [[X]]}编译与运行rustc main.rs -o surround_regions./surround_regions或者使用 cargo run复杂度分析时间复杂度O(m × n)其中 m 和 n 分别是矩阵的行数和列数。每个单元格最多被访问两次。空间复杂度O(m × n)最坏情况下矩阵全是“‘O’”递归调用栈的深度会达到 m × n。 延展思考避免递归栈溢出如果矩阵极大如 10^4 \times 10^4 递归 DFS 可能导致栈溢出。可以改用显式栈迭代 DFS或 队列BFS 来实现。并查集Union-Find创建一个虚拟节点代表“边界外”将所有边界上的“‘O’” 与虚拟节点合并最后检查内部“‘O’” 是否与虚拟节点连通。需要我为你提供迭代法BFS 队列的 Rust 实现或者讲解并查集解法吗
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/21 14:14:45

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/21 14:14:26

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/20 20:45:42

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/20 16:11:20

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/20 18:41:01

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/21 14:13:11

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉