当前位置: 首页 > 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 …...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...