【测试开发八股文】算法

1、栈和队列

1)栈:先进后出;队列:先进先出
2)如何用栈实现队列?
分析:两个栈,栈1负责入队,栈2负责出队
改进点:出队时,栈2出队后,可不把数据重新压回栈1
3)如何用队列实现栈?
进栈:把元素push进非空的队列,如果两者都是空的,则随意
出栈:把非空队列里面的前n-1个元素push到空队列里面,再把最后一个元素拿出来即可
循环以上步骤,即可得到实现目的
加分项:
空队列:对头front和队尾rear指针指向同一个位置
满队列:队列长度为数组长度减1,(rear + 1) % queueSize == front
队列长度:(rear - front + queueSize)% queueSize
对头 < 队尾:rear - front
对头 > 队尾:空闲长度 front - rear,因此队列长度 rear - front + queueSize
入队:先判是否满队列,后入队,队尾指针:rear = (rear + 1) % queueSize
出队:先判是否为空队列,后出队,对头指针:front = (front + 1) % queueSize
1)循环队列:队列使用顺序存储结构进行储存,即使用数组储存队列元素

2、链表

一系列节点组成的链,每一个节点保存了数据以及指向下一个节点的指针

1)如何反转一个单链表?
While cur->next != null:
Next = Cur->next
Cur->next = pre
Pre = cur
Cur = Next
递归:递归思想,从头结点递归遍历到最后一个结点,递归返回最后一个结点并修改指针,使指针指向前一个结点
移动指针(加分项):定义当前结点指针cur,前一个结点指针pre,循环迭代,计算下一个结点指针next,每次将当前结点指针反转指向前一个结点
2)如何判断一个链表中是否有环?
设置两个指针互相追逐。一个指针每次前进一步,第二个指针每次前进两步,如果有相遇,则说明有环,其中空间和时间复杂度分别O(n)和O(1)
3)返回链表倒数中第N个元素?
遍历:遍历一遍单链表,将其中的元素压栈,然后再将元素一一出栈。那么, 第n个出栈
加分项:维护两个指针, 它们之间的距离为n。然后,将这两个指针同步地在这个单链表上移动,保持它们的距离 为n不变。那么,当第二个指针指到空时,第一个指针即为所求
4)约瑟夫环问题(加分项):

3、树

1)概念:
假设按从上至下、从左至右对完全二叉树的节点进行编号(编号从1开始),则当一个节点编号为 i 时,则其左孩子节点的编号为 2i,右孩子编号为 2i + 1
满二叉树:所有叶子节点均在最后一层,且其它分支节点的度数均为2
完全二叉树:扣除最大层次一层后为满二叉树,且最后一层的所有节点均向左靠齐
平衡二叉查找树(AVL):任何节点的两个子树的高度最大差别为1
2)二叉树性质:
非空二叉树第i层上至多有 2^(i-1)个节点(i>=1)
深度为h的二叉树至多有 2^h - 1 个节点(h>1)
任一二叉树,若终端节点数为 n0,度为2的节点数是n2,则 n0 = n2 + 1 (n0 + n1 + n2 = 2n2 + n1)
具有n个节点的完全二叉树的深度为 k = [log(2)n] + 1 (2^(k-1) <= n < 2^k)
3)树的遍历方式
先序遍历:
递归:先根节点,再左子树,最后右子树
非递归栈(加分项)

设R为当前访问的结点

1)若 R != NULL,访问输出R并入栈,调用 R = R->lchild

2)若 R == NULL,重新设 R = 栈顶元素,栈顶元素出栈,R = R->rchild,返回1)

反复执行1)2),直到当前结点R==NULL && 栈空

莫里斯遍历
中序遍历:
递归:先左子树,再根节点,最后右子树
非递归栈(加分项)
莫里斯遍历
后序遍历:
递归:先左子树,再右子树,最后根节点
非递归栈(加分项):
层序遍历:每一层从左到右访问每一个节点
4)二叉树重构:
前序序列和中序序列
中序序列和后续序列
5)镜像二叉树:不断交换左右子数,直到结点的左右子树均未 null 时返回
6)AVL数:在AVL树中进行插入或删除节点后,可能导致AVL树失去平衡
LL:根节点k2右旋,k1变成根节点,k2变成k1的右子树,“k1的右子树"变成"k2的左子树”
在这里插入图片描述
RR:根节点k1右旋,k2变成根节点,k1变成k2的左子树,“k2的左子树"变成"k2的右子树”
在这里插入图片描述
RL:先左旋后右旋,即第一次旋转是围绕"k3"进行的"LL旋转",第二次是围绕"k1"进行的"RR旋转"
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/343601.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

python基础——线程

线程的使用 from threading import Thread import time def func(i):print("start{}".format(i))time.sleep(1)print("end{}".format(i)) for i in range(10):Thread(targetfunc,args(i,)).start() 守护线程的使用 主进程结束时&#xff0c;守护线程不会…

常用芯片学习——HC244芯片

HC573 三态输出八路缓冲器|线路驱动器 使用说明 SNx4HC244 八路缓冲器和线路驱动器专门设计用于提高三态存储器地址驱动器、时钟驱动器以及总线导向接收器和发送器的性能和密度。SNx4HC244 器件配备两个具有独立输出使能 (OE) 输入的 4 位缓冲器和驱动器。当 OE 为低电平时&a…

1. Matplotlib的Figure基础概念

1. Matplotlib的Figure基础概念 一 **角色和作用**二 **类比&#xff1a;**三 **基本使用示例** Matplotlib是一个用于绘制二维图形的Python库&#xff0c;广泛应用于数据可视化领域。其灵活性和强大的功能使得用户能够轻松创建各种类型的图表&#xff0c;包括折线图、散点图、…

node 第二十二天 mongoDB最新版7.x安装教程

学习服务端其实就是学习数据库, 就web这一条线而言, 客户端的学习就是学习浏览器, 而服务端的学习就是学习数据库(当然还有服务器) 为什么学习mongoDB mongoDB是非关系型数据库(not only sql) 基本上补全了mysql的缺陷, 当然也缺失了部分mysql的优势. 当然, 非大型应用的业务场…

linux中文件锁定--flock命令

在Linux操作系统中&#xff0c;flock是一个用于文件锁定的命令。文件锁定是一种机制&#xff0c;用于在多任务和多用户环境中管理对共享资源&#xff08;如文件&#xff09;的访问。flock允许你在代码中设置锁&#xff0c;以确保在任何给定时刻只有一个进程可以访问被锁定的文件…

leetcode—— 腐烂的橘子

腐烂的橘子 在给定的 m x n 网格 grid 中&#xff0c;每个单元格可以有以下三个值之一&#xff1a; 值 0 代表空单元格&#xff1b;值 1 代表新鲜橘子&#xff1b;值 2 代表腐烂的橘子。 每分钟&#xff0c;腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到…

Leetcode刷题(二十八)

找出字符串中第一个匹配项的下标&#xff08;Easy&#xff09; 给你两个字符串 haystack 和 needle &#xff0c;请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标&#xff08;下标从 0 开始&#xff09;。如果 needle 不是 haystack 的一部分&#xff0c;则返…

数据链路层流量控制与传输层流量控制对比

目录 一.数据链路层 1.停止等待协议 无差错情况&#xff1a; 有差错情况&#xff1a; 2.滑动窗口协议 &#xff08;1&#xff09;后退N帧协议&#xff08;GBN&#xff09; &#xff08;2&#xff09;选择重传协议&#xff08;SR&#xff09; 二.传输层 1.传输层的可靠…

Github2024-01-23 开源项目日报 Top9

根据Github Trendings的统计&#xff0c;今日(2024-01-23统计)共有9个项目上榜。根据开发语言中项目的数量&#xff0c;汇总情况如下&#xff1a; 开发语言项目数量Python项目3Go项目2TypeScript项目2Dart项目1Jupyter Notebook项目1 gpt4free 语言模型集合改进计划 创建周期…

基于 LangChain 框架,向量数据库如何创建、读取、更新、删除(CRUD)

RAG是目前大语言模型从工具走向生产力实践的最热门的方式&#xff0c;它可以实现从海量的文本数据中检索相关的信息&#xff0c;并用于生成高质量的文本输出。 而聊到RAG&#xff0c;我们就很难避开使用RAG的基础设施-向量数据库 今天我将带领大家&#xff0c;以最为基础的CRU…

安装miniconda、tensorflow、libcudnn

目录 安装miniconda 安装tensorflow 安装 libcudnn 安装miniconda wget https://repo.anaconda.com/miniconda/Miniconda3-latest-Linux-x86_64.sh && bash Miniconda3-latest-Linux-x86_64.sh 安装tensorflow tensorflow官网&#xff0c;查看版本对应 https:…

Linux——进程程序替换

进程程序替换 文章目录 进程程序替换1. 进程程序替换的基本概念2. exec系列函数2.1 是否带p2.1.1 execl()2.1.2 execlp() 2.2 是否带e2.2.1 execle() 2.3 l或v2.3.1 execvp() 2.4 返回值 3. 注意点 本章思维导图&#xff1a; 注&#xff1a;本章思维导图对应的 .xmind和 .png…

万界星空科技注塑行业MES解决方案

注塑行业是一个具有发展潜力的行业&#xff0c;随着人们对物质生活的质量要求越来越高&#xff0c;日用品、医疗保健、汽车工业以及建筑等行业对注塑制品的需求量日益增长。注塑企业提供的多种多样的塑料产品已深入到经济生活的各个领域&#xff0c;为国家经济的各个部门包括轻…

yolov8 opencv dnn部署自己的模型

源码地址 本人使用的opencv c github代码,代码作者非本人 使用github源码结合自己导出的onnx模型推理自己的视频 推理条件 windows 10 Visual Studio 2019 Nvidia GeForce GTX 1070 opencv4.7.0 (opencv4.5.5在别的地方看到不支持yolov8的推理&#xff0c;所以只使用opencv…

四、Flask学习之JavaScript

四、Flask学习之JavaScript JavaScript&#xff0c;作为一种前端脚本语言&#xff0c;赋予网页生动的交互性和动态性。通过它&#xff0c;开发者能够操作DOM&#xff08;文档对象模型&#xff09;实现页面元素的动态改变、响应用户事件&#xff0c;并借助AJAX技术实现异步数据…

【极数系列】Flink项目入门搭建(03)

【极数系列】Flink项目入门搭建&#xff08;03&#xff09; 引言 gitee地址&#xff1a;https://gitee.com/shawsongyue/aurora.git 源码直接下载可运行&#xff0c;模块&#xff1a;aurora_flink Flink 版本&#xff1a;1.18.0 Jdk 版本&#xff1a;11 1.创建mavenx项目 2.…

基于taro搭建小程序多项目框架

前言 为什么需要这样一个框架&#xff0c;以及这个框架带来的好处是什么&#xff1f; 从字面意思上理解&#xff1a;该框架可以用来同时管理多个小程序&#xff0c;并且可以抽离公用组件或业务逻辑供各个小程序使用。当你工作中面临这种同时维护多个小程序的业务场景时&#xf…

Unity中UGUI在Mask剪裁粒子特效的实现

在Unity使用Mask是剪裁不了粒子特效的&#xff0c;之前有想过RenderTexture来实现&#xff0c;不过使用RenderTexture不适合用于很多个特效&#xff0c;因为RenderTexture依赖Camera的照射&#xff0c;如果在背包中每种道具都有不同的特效&#xff0c;那使用RenderTexture则需要…

对接钉钉机器人发送钉钉通知

实现效果 话不多说 直接上代码 static void sendMsg(String msg) {new Thread(()->{try {String content "{\"msgtype\": \"text\",\"text\": {\"content\": \"" msg "\"}}";HttpUtil.simplePos…

Unity 桥接模式(实例详解)

文章目录 示例1&#xff1a;角色与装备系统示例2&#xff1a;UI控件库示例3&#xff1a;渲染引擎模块示例4&#xff1a;AI决策树算法示例5&#xff1a;物理模拟引擎 在Unity游戏开发中&#xff0c;桥接模式&#xff08;Bridge Pattern&#xff09;是一种设计模式&#xff0c;它…