新闻详情

新闻详情

首页 / 资讯中心 / 详情

DeepSeek LeetCode 109. 有序链表转换二叉搜索树 Scala实现

发布时间:2026/11/17 10:57:23来源:尧图网络
DeepSeek    LeetCode 109. 有序链表转换二叉搜索树 Scala实现
LeetCode 109. 有序链表转换二叉搜索树 — Scala 实现思路转数组 递归构建链表有序BST 中序遍历也有序。最直接的做法把链表值收集到 Array[Int]。递归取中点作为根左右子区间分别构建左右子树自然得到平衡 BST。代码方案一转数组// Definition for singly-linked list.classListNode(var_x:Int0){varnext:ListNodenullvarx:Int_x}// Definition for a binary tree node.classTreeNode(var_value:Int0){varvalue:Int_valuevarleft:TreeNodenullvarright:TreeNodenull}objectSolution{defsortedListToBST(head:ListNode):TreeNode{// 1. 链表转数组valbufscala.collection.mutable.ArrayBuffer.empty[Int]varcurheadwhile(cur!null){bufcur.x curcur.next}valarrbuf.toArray// 2. 递归构建平衡 BSTdefbuild(lo:Int,hi:Int):TreeNode{if(lohi)nullelse{valmid(lohi)1valnodenewTreeNode(arr(mid))node.leftbuild(lo,mid-1)node.rightbuild(mid1,hi)node}}build(0,arr.length-1)}}代码方案二中序遍历模拟空间 O(log n)不额外开数组用可变的链表当前节点指针配合中序递归objectSolution{defsortedListToBST(head:ListNode):TreeNode{// 1. 计算链表长度varn0varpheadwhile(p!null){n1;pp.next}// 用一个可变的当前链表指针模拟中序遍历varcur:ListNodeheaddefbuild(lo:Int,hi:Int):TreeNode{if(lohi)nullelse{valmid(lohi)1// 先构建左子树会消费链表前半部分valleftbuild(lo,mid-1)// 当前链表节点即根valrootnewTreeNode(cur.x)curcur.next root.leftleft// 再构建右子树root.rightbuild(mid1,hi)root}}build(0,n-1)}}复杂度分析方案 时间复杂度 空间复杂度转数组 O(n) O(n)数组中序模拟 O(n) O(log n)递归栈关键点中序模拟的核心先递归左子树此时链表指针 cur 恰好停在当前根位置取完根后指针后移再递归右子树。这样把链表的顺序和BST 的中序顺序对齐无需随机访问。Scala 的 var cur 闭包捕获嵌套函数 build 能直接读写外层 var cur等价于其他语言的 nonlocal / 可变引用写起来比 Rust 简洁很多。1无符号右移取中点避免 (lo hi) 溢出虽然本题范围安全但这是好习惯。推荐方案二空间更优且不依赖额外数组Scala 中可读性也好推荐优先掌握。
网站建设高端定制企业官网
RELATED

相关资讯

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

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/17 7:04:08

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

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

阅读更多 →
无法下载Windows系统iso文件 2026/11/17 5:42:44

无法下载Windows系统iso文件

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

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/16 19:23:38

【清华代码熊】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/17 6:55:04

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/17 5:57:47

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/16 17:28:18

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

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

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

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

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