当前位置: 首页 > news >正文

Python | Leetcode Python题解之第230题二叉搜索树中第K小的元素

题目:

题解:

class AVL:"""平衡二叉搜索树(AVL树):允许重复值"""class Node:"""平衡二叉搜索树结点"""__slots__ = ("val", "parent", "left", "right", "size", "height")def __init__(self, val, parent=None, left=None, right=None):self.val = valself.parent = parentself.left = leftself.right = rightself.height = 0  # 结点高度:以node为根节点的子树的高度(高度定义:叶结点的高度是0)self.size = 1  # 结点元素数:以node为根节点的子树的节点总数def __init__(self, vals):self.root = self._build(vals, 0, len(vals) - 1, None) if vals else Nonedef _build(self, vals, l, r, parent):"""根据vals[l:r]构造平衡二叉搜索树 -> 返回根结点"""m = (l + r) // 2node = self.Node(vals[m], parent=parent)if l <= m - 1:node.left = self._build(vals, l, m - 1, parent=node)if m + 1 <= r:node.right = self._build(vals, m + 1, r, parent=node)self._recompute(node)return nodedef kth_smallest(self, k: int) -> int:"""返回二叉搜索树中第k小的元素"""node = self.rootwhile node:left = self._get_size(node.left)if left < k - 1:node = node.rightk -= left + 1elif left == k - 1:return node.valelse:node = node.leftdef insert(self, v):"""插入值为v的新结点"""if self.root is None:self.root = self.Node(v)else:# 计算新结点的添加位置node = self._subtree_search(self.root, v)is_add_left = (v <= node.val)  # 是否将新结点添加到node的左子结点if node.val == v:  # 如果值为v的结点已存在if node.left:  # 值为v的结点存在左子结点,则添加到其左子树的最右侧node = self._subtree_last(node.left)is_add_left = Falseelse:  # 值为v的结点不存在左子结点,则添加到其左子结点is_add_left = True# 添加新结点leaf = self.Node(v, parent=node)if is_add_left:node.left = leafelse:node.right = leafself._rebalance(leaf)def delete(self, v) -> bool:"""删除值为v的结点 -> 返回是否成功删除结点"""if self.root is None:return Falsenode = self._subtree_search(self.root, v)if node.val != v:  # 没有找到需要删除的结点return False# 处理当前结点既有左子树也有右子树的情况# 若左子树比右子树高度低,则将当前结点替换为右子树最左侧的结点,并移除右子树最左侧的结点# 若右子树比左子树高度低,则将当前结点替换为左子树最右侧的结点,并移除左子树最右侧的结点if node.left and node.right:if node.left.height <= node.right.height:replacement = self._subtree_first(node.right)else:replacement = self._subtree_last(node.left)node.val = replacement.valnode = replacementparent = node.parentself._delete(node)self._rebalance(parent)return Truedef _delete(self, node):"""删除结点p并用它的子结点代替它,结点p至多只能有1个子结点"""if node.left and node.right:raise ValueError('node has two children')child = node.left if node.left else node.rightif child is not None:child.parent = node.parentif node is self.root:self.root = childelse:parent = node.parentif node is parent.left:parent.left = childelse:parent.right = childnode.parent = nodedef _subtree_search(self, node, v):"""在以node为根结点的子树中搜索值为v的结点,如果没有值为v的结点,则返回值为v的结点应该在的位置的父结点"""if node.val < v and node.right is not None:return self._subtree_search(node.right, v)elif node.val > v and node.left is not None:return self._subtree_search(node.left, v)else:return nodedef _recompute(self, node):"""重新计算node结点的高度和元素数"""node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))node.size = 1 + self._get_size(node.left) + self._get_size(node.right)def _rebalance(self, node):"""从node结点开始(含node结点)逐个向上重新平衡二叉树,并更新结点高度和元素数"""while node is not None:old_height, old_size = node.height, node.sizeif not self._is_balanced(node):node = self._restructure(self._tall_grandchild(node))self._recompute(node.left)self._recompute(node.right)self._recompute(node)if node.height == old_height and node.size == old_size:node = None  # 如果结点高度和元素数都没有变化则不需要再继续向上调整else:node = node.parentdef _is_balanced(self, node):"""判断node结点是否平衡"""return abs(self._get_height(node.left) - self._get_height(node.right)) <= 1def _tall_child(self, node):"""获取node结点更高的子树"""if self._get_height(node.left) > self._get_height(node.right):return node.leftelse:return node.rightdef _tall_grandchild(self, node):"""获取node结点更高的子树中的更高的子树"""child = self._tall_child(node)return self._tall_child(child)@staticmethoddef _relink(parent, child, is_left):"""重新连接父结点和子结点(子结点允许为空)"""if is_left:parent.left = childelse:parent.right = childif child is not None:child.parent = parentdef _rotate(self, node):"""旋转操作"""parent = node.parentgrandparent = parent.parentif grandparent is None:self.root = nodenode.parent = Noneelse:self._relink(grandparent, node, parent == grandparent.left)if node == parent.left:self._relink(parent, node.right, True)self._relink(node, parent, False)else:self._relink(parent, node.left, False)self._relink(node, parent, True)def _restructure(self, node):"""trinode操作"""parent = node.parentgrandparent = parent.parentif (node == parent.right) == (parent == grandparent.right):  # 处理需要一次旋转的情况self._rotate(parent)return parentelse:  # 处理需要两次旋转的情况:第1次旋转后即成为需要一次旋转的情况self._rotate(node)self._rotate(node)return node@staticmethoddef _subtree_first(node):"""返回以node为根结点的子树的第1个元素"""while node.left is not None:node = node.leftreturn node@staticmethoddef _subtree_last(node):"""返回以node为根结点的子树的最后1个元素"""while node.right is not None:node = node.rightreturn node@staticmethoddef _get_height(node) -> int:"""获取以node为根结点的子树的高度"""return node.height if node is not None else 0@staticmethoddef _get_size(node) -> int:"""获取以node为根结点的子树的结点数"""return node.size if node is not None else 0class Solution:def kthSmallest(self, root: TreeNode, k: int) -> int:def inorder(node):if node.left:inorder(node.left)inorder_lst.append(node.val)if node.right:inorder(node.right)# 中序遍历生成数值列表inorder_lst = []inorder(root)# 构造平衡二叉搜索树avl = AVL(inorder_lst)# 模拟1000次插入和删除操作random_nums = [random.randint(0, 10001) for _ in range(1000)]for num in random_nums:avl.insert(num)random.shuffle(random_nums)  # 列表乱序for num in random_nums:avl.delete(num)return avl.kth_smallest(k)

相关文章:

Python | Leetcode Python题解之第230题二叉搜索树中第K小的元素

题目&#xff1a; 题解&#xff1a; class AVL:"""平衡二叉搜索树&#xff08;AVL树&#xff09;&#xff1a;允许重复值"""class Node:"""平衡二叉搜索树结点"""__slots__ ("val", "parent&quo…...

Python酷库之旅-第三方库Pandas(018)

目录 一、用法精讲 44、pandas.crosstab函数 44-1、语法 44-2、参数 44-3、功能 44-4、返回值 44-5、说明 44-6、用法 44-6-1、数据准备 44-6-2、代码示例 44-6-3、结果输出 45、pandas.cut函数 45-1、语法 45-2、参数 45-3、功能 45-4、返回值 45-5、说明 4…...

九科bit-Worker RPA 内容学习

入门阶段&#xff0c; 花时间学习和记忆细枝末节&#xff0c;可能会反而分散新手去理解核心逻辑的精力&#xff0c;并且不常用的知识也很容易被遗忘。 简介&#xff1a; 什么是RPA&#xff1f; RPA&#xff08;Robotic Process Automation&#xff0c;机器人流程自动化&#x…...

vscode编译环境配置-golang

1. 支持跳转 如果单测函数上方不显示run test | debug test&#xff0c;需要安装Code Debugger&#xff08;因为以前的go Test Explorer不再被维护了&#xff09; 2. 单测 指定单个用例测试 go test -v run TestXXXdlv 调试 需要安装匹配的go版本和delve版本&#xff08;如…...

【JavaEE】网络编程——UDP

&#x1f921;&#x1f921;&#x1f921;个人主页&#x1f921;&#x1f921;&#x1f921; &#x1f921;&#x1f921;&#x1f921;JavaEE专栏&#x1f921;&#x1f921;&#x1f921; 文章目录 1.数据报套接字(UDP)1.1特点1.2编码1.2.1DatagramSocket1.2.2DatagramPacket…...

JAVA毕业设计147—基于Java+Springboot的手机维修管理系统(源代码+数据库)

基于JavaSpringboot的手机维修管理系统(源代码数据库)147 一、系统介绍 本项目分为用户、管理员、维修员三种角色 1、用户&#xff1a; 注册、登录、新闻公告、售后申请、申请列表、意见反馈、个人信息、密码修改 2、管理员&#xff1a; 用户管理、用户管理、栏目管理、网…...

力扣第228题“汇总区间”

在本篇文章中&#xff0c;我们将详细解读力扣第228题“汇总区间”。通过学习本篇文章&#xff0c;读者将掌握如何遍历和汇总区间&#xff0c;并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释&#xff0c;以便于理解。 问题描述 力扣第228题“汇总区间”描…...

部署大语言模型并对话

在阿里云的https://developer.aliyun.com/adc/scenario/b105013328814fe995c0f091d708d67d 选择函数计算 设置服务器配置 复制公网地址 这个地址不能直接 在返回应用&#xff0c;创建应用LLM 对话页面 Open WebUI 点击下面的创建应用 部署完成后访问域名 打开访问地址...

WebSocket、socket.io-client

WebSocket WebSocket 是一种网络通信协议&#xff0c;它提供了一个在单个长期持久的 TCP 连接上进行全双工&#xff08;full-duplex&#xff09;通信的通道。 WebSocket 允许客户端和服务器之间进行双向的数据交换&#xff0c;这意味着服务器可以主动向客户端推送数据&#x…...

Maven 仓库

在 Maven 世界中&#xff0c;任何一个依赖、插件或者项目构建的输出&#xff0c;都可以称为 构件 。 坐标和依赖是构件在 Maven 世界中的逻辑表示方式&#xff0c;构件的物理表示方式是文件&#xff0c;Maven 通过仓库来统一管理这些文件。 任何一个构件都有一组坐标唯一标识。…...

给后台写了一个优雅的自定义风格的数据日志上报页面

highlight: atelier-cave-dark 查看后台数据日志是非常常见的场景,经常看到后台的小伙伴从服务器日志复制一段json数据字符串,然后找一个JSON工具网页打开,在线JSON格式化校验。有的时候,一些业务需要展示mqtt或者socket的实时信息展示,如果不做任何修改直接展示一串字符…...

【React Native优质开源项目】

&#x1f308;个人主页: 程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…...

Android 自动更新时间的数字时钟 TextClock

TextClock 继承 TextView &#xff0c;使用方法和 TextView 一样。 它专门用于显示数字时钟&#xff0c;可以自定义显示格式。 只要在布局文件里添加&#xff0c;它会自动更新时间&#xff0c;不需要添加刷新逻辑。 布局文件&#xff0c; <?xml version"1.0"…...

【Linux Git入门】Git的介绍

文章目录 前言git简介git是什么git的作用为什么要学习git安装git总结前言 在现代软件开发中,版本控制系统已经成为了不可或缺的工具。其中,Git是最受欢迎的版本控制系统之一。Git是由Linux的创造者Linus Torvalds在2005年创建的,用于管理Linux内核的开发。Git是一个分布式版…...

kafka面试题(基础-进阶-高阶)

目录 Kafka 基础篇 1.Kafka 的用途有哪些?使用场景如何? 2.Kafka 中的ISR、AR 又代表什么?ISR 的伸缩又指什么 3.Kafka 中的 HW、LEO、LSO、LW 等分别代表什么? 4.Kafka 中是怎么体现消息顺序性的? 5.Kafka 中的分区器、序列化器、拦截器是否了解?它们之间的处理顺序…...

《系统架构设计师教程(第2版)》第11章-未来信息综合技术-07-大数据技术概述

文章目录 1. 大数据的定义2. 大数据的研究内容2.1 面临的问题2.2 面临的挑战2.3 分析步骤2.3.1 数据获取和记录2.3.2 信息抽取和清洗2.3.3 数据集成、聚集和表示2.3.4 查询处理、数据建模和分析2.3.5 解释 3.大数据的应用领域3.1 制造业的应用3.2 服务业的应用3.3 交通行业的应…...

前端面试题54(断点续传讲解)

断点续传是一种在上传或下载大文件时&#xff0c;如果因为网络问题中断&#xff0c;可以从已经上传或下载的部分继续&#xff0c;而不是重新开始的技术。这对于提高用户体验和节省带宽非常有帮助。下面我将分别从HTTP协议层面、前端实现思路以及一个简单的前端实现示例来讲解断…...

YOLOv10改进 | Conv篇 | RCS-OSA替换C2f实现暴力涨点(减少通道的空间对象注意力机制)

一、本文介绍 本文给大家带来的改进机制是RCS-YOLO提出的RCS-OSA模块&#xff0c;其全称是"Reduced Channel Spatial Object Attention"&#xff0c;意即"减少通道的空间对象注意力"。这个模块的主要功能是通过减少特征图的通道数量&#xff0c;同时关注空…...

【C++BFS】690. 员工的重要性

本文涉及知识点 CBFS算法 LeetCode690. 员工的重要性 你有一个保存员工信息的数据结构&#xff0c;它包含了员工唯一的 id &#xff0c;重要度和直系下属的 id 。 给定一个员工数组 employees&#xff0c;其中&#xff1a; employees[i].id 是第 i 个员工的 ID。 employees[…...

视频调整帧率、分辨率+音画同步

# python data_utils/pre_video/multi_fps_crop_sync.pyimport cv2 import os from tqdm import tqdm import subprocess# 加载人脸检测模型 face_cascade cv2.CascadeClassifier(cv2.data.haarcascades haarcascade_frontalface_default.xml)def contains_face(frame):gray …...

【深度学习】关于模型加速

模型转为半精度的会加快推理速度吗 将模型转为半精度&#xff08;通常指16位浮点数&#xff0c;即FP16&#xff09;确实可以加快推理速度&#xff0c;同时还能减少显存&#xff08;GPU内存&#xff09;的使用。以下是一些关键点&#xff1a; 加快推理速度的原因 减少计算量&a…...

Python中time模块用法示例详解

前言 仅供个人学习用&#xff0c;如果对各位朋友有参考价值&#xff0c;给个赞或者收藏吧 ^_^ 一、time模块介绍 time模块是Python中处理时间相关操作的核心工具&#xff0c;提供了时间获取、格式化、转换、延迟以及计时等多种功能。 总的来说time模块中时间可以有3种格式&…...

解决POST请求中文乱码问题

解决POST请求中文乱码问题 1、乱码原因2、解决方法3、具体步骤 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496; 在Web开发中&#xff0c;处理POST请求时经常遇到中文乱码问题&#xff0c;这主要是由于服务器在接收到POST请求的数据后&#x…...

Axure-黑马

Axure-黑马 编辑时间2024/7/12 来源&#xff1a;B站黑马程序员 需求其他根据&#xff1a;visio&#xff0c;墨刀 Axure介绍 Axure RP是美国Axure Software Solution给公司出品的一款快速原型大的软件&#xff0c;一般来说使用者会称他为Axure 应用场景 拉投资使用 给项目团…...

Centos解决服务器时间不准的问题

CentOS 系统时间老是自己变化可能有以下几个原因&#xff1a; 硬件时钟问题&#xff1a;服务器的硬件时钟可能出现故障或不准确。 时区设置错误&#xff1a;如果时区设置不正确&#xff0c;可能导致显示的时间与实际期望的时间不符。 系统服务异常&#xff1a;与时间同步相关…...

摸鱼大数据——Kafka——Kafka的shell命令使用

Kafka本质上就是一个消息队列的中间件的产品&#xff0c;主要负责消息数据的传递。也就说学习Kafka 也就是学习如何使用Kafka生产数据&#xff0c;以及如何使用Kafka来消费数据 topics操作 注意: 创建topic不指定分区数和副本数,默认都是1个 分区数可以后期通过alter增大,但是…...

在 Linux/Debian/Ubuntu 上使用 Brasero 刻录光盘

在 Ubuntu 系统中&#xff0c;Brasero 是一个非常方便的光盘刻录工具。无论是创建数据光盘、音频光盘还是刻录光盘镜像文件&#xff0c;Brasero 都能轻松胜任。本文将介绍如何在 Ubuntu 上安装和使用 Brasero 进行光盘刻录。 安装 Brasero 在大多数 Ubuntu 版本中&#xff0c…...

QT之嵌入外部第三方软件到本窗体中

一、前言 使用QT开发&#xff0c;有时需要调用一些外部程序&#xff0c;但是单独打开一个外部窗口有的场合很不合适&#xff0c;最好是嵌入到开发的QT程序界面中。还有就是自己开发的n个程序&#xff0c;一个主程序托n个子程序&#xff0c;为了方便管理将各个程序独立&#xf…...

解决GET请求中文乱码问题

解决GET请求中文乱码问题 1、乱码的根本原因2、解决方法方法一&#xff1a;修改Tomcat配置&#xff08;推荐&#xff09;方法二&#xff1a;使用URLEncoder和URLDecoder&#xff08;不推荐用于GET请求乱码&#xff09;方法三&#xff1a;String类编解码&#xff08;不直接解决乱…...

弥合人类与人工智能的知识差距:AlphaZero 中的概念发现和迁移(1)

文章目录 一、摘要二、简介三、相关工作3.1 基于概念的解释3.2 强化学习中生成解释3.3 国际象棋与人工智能 四、什么是概念&#xff1f;五、发掘概念5.1 挖掘概念向量5.1.1 静态概念的概念约束5.1.2 动态概念的概念约束 5.2 过滤概念 一、摘要 人工智能&#xff08;AI&#xff…...