新闻详情

新闻详情

首页 / 资讯中心 / 详情

元宝 LeetCode 113.路径总和 || rust实现

发布时间:2026/11/16 11:57:36来源:尧图网络
元宝    LeetCode 113.路径总和 || rust实现
LeetCode 113Path Sum II是一道经典的 深度优先搜索DFS 回溯 题目。解题思路从根节点开始遍历用一个“path” 动态记录从根到当前节点的路径。用“current_sum” 记录当前路径上节点值的总和。当遇到叶子节点时检查路径总和是否等于“targetSum”。如果相等将当前“path” 的拷贝加入结果集。回溯在递归返回前将当前节点从“path” 中弹出以便探索其他分支。Rust 实现代码在 LeetCode 中“TreeNode” 通常定义为“OptionRcRefCell”。以下是可以直接提交的完整代码// 假设 LeetCode 已提供 TreeNode 的定义// #[derive(Debug, PartialEq, Eq)]// pub struct TreeNode {// pub val: i32,// pub left: OptionRcRefCell,// pub right: OptionRcRefCell,// }// impl TreeNode {// #[inline]// pub fn new(val: i32) - Self { … }// }use std::rc::Rc;use std::cell::RefCell;impl Solution {pub fn path_sum(root: OptionRcRefCell, target_sum: i32) - VecVec {let mut result: VecVec Vec::new();let mut path: Vec Vec::new();if let Some(node) root { Solution::dfs(node, target_sum, 0, mut path, mut result); } result } // 深度优先搜索 fn dfs( node: RcRefCellTreeNode, target_sum: i32, current_sum: i32, path: mut Veci32, result: mut VecVeci32 ) { // 取出当前节点的值并加入路径 let val node.borrow().val; path.push(val); let new_sum current_sum val; // 先克隆左右子节点的引用避免持有 borrow 导致递归时 panic let left node.borrow().left.clone(); let right node.borrow().right.clone(); // 判断是否为叶子节点 if left.is_none() right.is_none() { if new_sum target_sum { // 找到一条合法路径克隆当前路径存入结果 result.push(path.clone()); } } else { // 递归遍历左右子树 if let Some(left_node) left { Solution::dfs(left_node, target_sum, new_sum, path, result); } if let Some(right_node) right { Solution::dfs(right_node, target_sum, new_sum, path, result); } } // 回溯离开当前节点将其从路径中移除 path.pop(); }}关键点解析Rust 特性“RcRefCell” 的使用LeetCode 的树节点使用“Rc”引用计数允许多个所有者“RefCell” 提供内部可变性。在递归前通过“.clone()” 获取左右子节点的“OptionRc…”这样不会长期持有“RefCell” 的借用避免运行时 panic。回溯与所有权“path” 通过“mut Vec” 传递在递归前后分别执行“push” 和“pop”手动维护路径状态。“result.push(path.clone())” 这里必须“clone”因为“path” 后续还会被修改。3. 效率时间复杂度O(N)每个节点访问一次。空间复杂度O(N)递归栈深度及存储路径所需的空间。如果你希望改成迭代法使用显式栈或者想了解如何处理 i32 溢出等边界情况也可以告诉我
网站建设高端定制企业官网
RELATED

相关资讯

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

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/15 4:54:16

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

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

阅读更多 →
无法下载Windows系统iso文件 2026/11/15 2:04:12

无法下载Windows系统iso文件

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

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

【清华代码熊】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/16 6:47:19

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/14 16:35:50

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/15 4:06:36

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

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

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

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

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