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

王道数据结构编程题 查找

二叉树定义

以下为本文解题代码的二叉树定义。

struct TreeNode {int val;TreeNode* left, *right;TreeNode(int val = 0, TreeNode* left = nullptr, TreeNode* right = nullptr): val(val), left(left), right(right) {}
};

递归二分查找

题目描述

写出二分查找的递归算法。初始调用时,left 为1,right 为 n.

解题代码

bool recurBS(vector<int>& nums, int target, int left, int right) {if (left > right) return false;int mid = (left + right) / 2;if (nums[mid] == target) return true;else if (nums[mid] > target) {return recurBS(nums, target, left, mid - 1);}else {return recurBS(nums, target, mid + 1, right);}
}

优化顺序查找

题目描述

线性表中各结点的检索概率不等时,可用如下策略提高顺序检索的效率:若找到指定的结点,则将该结点和其前驱节点(若存在)交换,使得经常被检索的结点尽量位于表的前端。试设计在顺序结构和链式结构的线性表上实现上述策略的顺序检索算法。

解题代码

顺序表

bool optimisedSS(vector<int>& nums, int target) {for (int i = 0; i < nums.size(); ++i) {if (nums[i] == target) {if (i > 0) {swap(nums[i - 1], nums[i]);}return true;}}return false;
}

链表

bool optimisedSS(ListNode* head, int target) {if (head == nullptr) return false;ListNode* dummy = new ListNode(-1, head); // 哨兵结点if (dummy->next->val == target) return true;while (dummy->next->next != nullptr) {if (dummy->next->next->val == target) {ListNode* pre = dummy;ListNode* node1 = dummy->next;ListNode* node2 = dummy->next->next;pre->next = node2;node1->next = node2->next;node2->next = node1;return true;}dummy = dummy->next;}return false;
}

判定二叉搜索树

题目描述

试编写一个算法,判断给定的二叉树是否是二叉搜索树。

解题代码

bool dfs(TreeNode* root, int preVal) {if (root == nullptr) return true;if (!dfs(root->left, preVal) || root->val <= preVal) {return false;}preVal = root->val;return dfs(root->right, preVal);
}bool isBST(TreeNode* root) {int lastVal = INT32_MIN;return dfs(root, lastVal);
}

计算某结点层次

题目描述

设计一个算法,求出指定结点在给定二叉排序树中的层次。

解题代码

int dfs(TreeNode* root, TreeNode* node, int depth) {if (root == nullptr) return 0;if (root->val == node->val) {return depth;}else if (root->val < node->val) {return dfs(root->right, node, depth + 1);}else {return dfs(root->left, node, depth + 1);}
}int calNodeDepth(TreeNode* root, TreeNode* node) {return dfs(root, node, 1);
}

判定平衡二叉树

题目描述

利用二叉树遍历的遍历的思想,编写一个判断二叉树是否是平衡二叉树的算法。

解题代码

O(n^2)

int calDepth(TreeNode* root) {if (root == nullptr) return 0;return 1 + max(calDepth(root->left), calDepth(root->right));
}bool isBalanced(TreeNode* root) {if (root == nullptr) return true;int lDepth = calDepth(root->left);int rDepth = calDepth(root->right);return abs(lDepth - rDepth) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}

在每次递归判断左右子树是否平衡时,需要重新计算其高度,因此引入了大量不必要的计算。而如果某棵树的子树之一已经是非平衡树,那么这棵树一定是非平衡树,根据该性质,可将对平衡的判断改为自底向上进行。以下为自底向上判断平衡的方式,可将时间复杂度优化至 O(n).

O(n)

int calDepth(TreeNode* root) {if (root == nullptr) return 0;int lDepth = calDepth(root->left);int rDepth = calDepth(root->right);if (lDepth == -1 || rDepth == -1 || abs(lDepth - rDepth) >= 2) {return -1;}return 1 + max(lDepth, rDepth);
}bool isBalanced(TreeNode* root) {return calDepth(root) >= 0;
}

二叉搜索树最大和最小结点

题目描述

设计一个算法,求出给定二叉搜索树中最小和最大的关键字。

解题代码

int calMaxVal(TreeNode* root) {if (root->right == nullptr) return root->val;return calMaxVal(root->right);
}int calMinVal(TreeNode* root) {if (root->left == nullptr) return root->val;return calMinVal(root->left);
}pair<int, int> calMaxMin(TreeNode* root) {int minVal = root->left == nullptr ? root->val : calMinVal(root->left);int maxVal = root->right == nullptr ? root->val : calMaxVal(root->right);return make_pair(minVal, maxVal);
}

二叉搜索树值不小于 k 的元素

题目描述

设计一个算法,从大到小输出二叉搜索树中所有值不小于 k 的元素。

解题代码

void printNotSmallerK(TreeNode* root, int k) {if (root == nullptr) return;printNotSmallerK(root->right, k);if (root->val >= k) {cout << root->val << " ";}else return;printNotSmallerK(root->left, k);
}

查找第k小的元素

题目描述

编写一个递归算法,在一棵有 n 个结点的,随机建立起来的二叉搜索树上查找第 k (1 <= k <= n)小的元素,并返回指向该结点的指针,要求算法的平均时间复杂度为 O(logn)。二叉搜索树中的每个结点除 data, lchild, rchild 等数据成员外,增加一个 count 成员,保存以该结点为根的子树上的结点个数。

解题代码

TreeNode* findKthNode(TreeNode* root, int& k) {if (root == nullptr) return nullptr;TreeNode* left = findKthNode(root->left, k);if (left != nullptr) return left;if (--k == 0) return root;return findKthNode(root->right, k);
}

相关文章:

王道数据结构编程题 查找

二叉树定义 以下为本文解题代码的二叉树定义。 struct TreeNode {int val;TreeNode* left, *right;TreeNode(int val 0, TreeNode* left nullptr, TreeNode* right nullptr): val(val), left(left), right(right) {} };递归二分查找 题目描述 写出二分查找的递归算法。初…...

vue 部分知识点总结

计算属性和方法有什么区别&#xff0c;怎么选择&#xff1f; 在编程中&#xff0c;计算属性和方法都是用于处理数据的工具&#xff0c;但它们有一些区别。以下是它们的区别和如何选择的几个因素&#xff1a; 执行方式&#xff1a;计算属性是基于依赖的响应式系统&#xff0c;在…...

谷粒商城----ES篇

一、product-es准备 P128 ES在内存中&#xff0c;所以在检索中优于mysql。ES也支持集群&#xff0c;数据分片存储。 需求&#xff1a; 上架的商品才可以在网站展示。上架的商品需要可以被检索。 分析sku在es中如何存储 商品mapping 分析&#xff1a;商品上架在es中是存s…...

Redis3.2.1如何设置远程连接?允许局域网访问

背景&#xff1a; 电脑A的redis需要开放给电脑B使用&#xff0c;二者处于同一局域网 【后面会补充更详细的踩坑历程&#xff0c;先发出来作为记录】 过程&#xff1a; 在你查了很多方法后&#xff0c;如果还是没有解决&#xff0c; 尝试考虑一下你的redis配置文件是不是修…...

网络原理(二)TCP的可靠传输

网络原理&#xff08;一&#xff09;目录 网络原理应用层传输层先说UDP&#xff08;不可靠传输&#xff09;重点说明&#xff34;&#xff23;&#xff30;&#xff08;可靠传输&#xff09;一、确认应答二、超时重传三、链接管理建立连接断开链接 四、滑动窗口五、流量控制&am…...

Chat GPT 使用教学,文字创作、学习

目录 文章长篇文章学习任何东西文章 大纲、目录、标题、内容 写出10个即将被AI取代的工作的文章标题 当然,以下是一些可能会被AI取代的工作的文章标题:"未来十年,AI将如何改变传统制造业的就业格局?" "智能客服崛起:人工智能如何重塑客户服务行业?"…...

Android之 Canvas绘制

一 Canvas介绍 1.1 Canvas 是绘制图形的重要类之一&#xff0c;它可以在 View 或 SurfaceView 上绘制各种图形和文本. 1.2 要创建 Canvas&#xff0c;首先需要有一个 View 或 SurfaceView 对象&#xff0c;在 View 或 SurfaceView 的绘制方法中&#xff0c;可以通过 Canvas 的…...

Vue + Element UI 前端篇(十五):嵌套外部网页

Vue Element UI 实现权限管理系统 前端篇&#xff08;十五&#xff09;&#xff1a;嵌套外部网页 嵌套外部网页 在有些时候&#xff0c;我们需要在我们的内容栏主区域显示外部网页。如查看服务端提供的SQL监控页面&#xff0c;接口文档页面等。 这个时候就要求我们的导航菜…...

Jabbi的Rust学习日记(二)

特征&#xff1a; 就目前我学习到的rust知识来看&#xff0c;我认为rust有以下几个特征&#xff1a; 链式调用表达式强类型 use 使用use导入包&#xff0c;我觉得rust的导包和python的很像 main main函数是rust可执行程序最先执行的代码&#xff0c;可以说是程序的入口&…...

【杂】环形时钟配色笔记

配色网站笔记 coolorsflatuicolorscolordrophttps://www.webdesignrankings.com/resources/lolcolors/ 配色2...

会话跟踪技术学习笔记(Cookie+Session)+ HTTP学习笔记

一、核心知识点&#xff08;重点&#xff09;&#xff1a; 1.1 Cookie 1. Cookie&#xff1a;是一种客户端会话技术&#xff0c;数据会被保存在客户端&#xff0c;Cookie会携带数据访问服务器&#xff0c;用以完成一次会话内多次请求间的数据共享 2. 过程&#xff1a;浏览器…...

分类预测 | MATLAB实现PCA-BiLSTM(主成分双向长短期记忆神经网络)分类预测

分类预测 | MATLAB实现PCA-BiLSTM(主成分双向长短期记忆神经网络)分类预测 目录 分类预测 | MATLAB实现PCA-BiLSTM(主成分双向长短期记忆神经网络)分类预测预测效果基本介绍程序设计参考资料致谢 预测效果 基本介绍 分类预测 | MATLAB实现PCA-BiLSTM(主成分双向长短期记忆神经网…...

Yarn 和 npm 的区别

Yarn 和 npm 都是 JavaScript 的包管理工具&#xff0c;它们的主要区别在于以下几个方面&#xff1a; 性能&#xff1a;Yarn 的安装速度和包的下载速度通常比 npm 更快&#xff0c;这是因为 Yarn 使用本地缓存和并行下载等技术来提高性能。 可靠性&#xff1a;Yarn 具有更好的…...

第20章 原子操作实验(iTOP-RK3568开发板驱动开发指南 )

在上一章节的实验中&#xff0c;对并发与竞争进行了实验&#xff0c;两个app应用程序之间对共享资源的竞争访问引起了数据传输错误&#xff0c;而在Linux内核中&#xff0c;提供了四种处理并发与竞争的常见方法&#xff0c;分别是原子操作、自旋锁、信号量、互斥体&#xff0c;…...

Android 开机自启动

APP需要开机自启动&#xff0c;要通过开机广播实现。 1&#xff0c;在AndroidManifest.xml中增加权限 <!-- .接收启动完成的广播权限 --><uses-permission android:name"android.permission.RECEIVE_BOOT_COMPLETED" /> 2&#xff0c;在AndroidManifes…...

01_前端css编写的三种方式

前言 CSS的引入方式共有三种&#xff1a;行内样式、内部样式表、外部样式表 一、内联式引入 用法&#xff1a; 在元素上直接通过style属性进行设置css样式设置 示例&#xff1a; <h1 style"color:red;">style属性的应用</h1> <p style"font-si…...

07-垃圾收集算法详解

上一篇&#xff1a;06-JVM对象内存回收机制深度剖析 1.分代收集理论 当前虚拟机的垃圾收集都采用分代收集算法&#xff0c;这种算法没有什么新的思想&#xff0c;只是根据对象存活周期的不同将内存分为几块。一般将java堆分为新生代和老年代&#xff0c;这样我们就可以根据各…...

Redis高并发分布式锁实战

高并发场景秒杀抢购超卖bug实战重现 秒杀抢购场景下实战JVM级别锁与分布式锁 大厂分布式锁Resisson框架实战 Lua脚本语言快速入门与使用注意事项 Redisson分布式锁源码剖析 Redis主从架构锁失效问题解析 从CAP角度剖析Redis与Zookeeper分布式锁区别 Redlock分布式锁原理与…...

MybatisPlus分页插件使用

一. 效果展示 二. 代码编写 2.1 pom <dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-boot-starter</artifactId><version>3.4.2</version> </dependency>2.2 添加配置类 Configuration MapperScan(…...

Linux指令二【进程,权限,文件】

进程是一个具有一定独立功能的程序在一个数据集上的一次动态执行的过程&#xff0c;是操作系统进行 资源分配和调度的一个独立单位&#xff0c;是应用程序运行的载体。 一、进程基本指令 1.ps&#xff1a;当前的用户进程 ps 只显示隶属于自己的进程状态ps -aux 显示所有进程…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...