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

算法 | 刷题日记

1.递归通常是用栈来实现的

递归在其本质上是通过函数调用栈(Call Stack)来实现的,而不是队列(Queue)。当你调用一个函数时,该函数的局部变量、参数和返回地址会被压入(push)到一个由系统维护的调用栈中。当函数执行完毕后,这些数据会被从栈中弹出(pop),并且控制权会返回给调用者。

递归函数调用也遵循同样的模式:当一个函数(假设我们称其为A)内部调用了它自己或者另一个函数(假设我们称其为B,而B又调用了A,形成了递归),每次函数调用都会将其状态压入调用栈。当递归到达基线条件(Base Case)并开始返回时,每个函数的状态会从栈中弹出,直到最初的调用者得到结果。

队列通常用于实现迭代算法,如广度优先搜索(BFS)等。在BFS中,队列用于存储待处理的节点,并按照它们被添加到队列中的顺序进行处理。这与递归的深度优先搜索(DFS)形成对比,DFS使用栈(或隐式的函数调用栈)来按照后进先出(LIFO)的顺序处理节点。

虽然技术上可以使用队列和显式栈来模拟递归行为(例如,通过迭代实现递归算法),但这样做通常会使代码更复杂,并可能牺牲递归提供的清晰性和简洁性。然而,在某些情况下,例如处理深度非常大的递归树或需要避免栈溢出的场景,使用迭代和显式栈可能是有益的。

2.优先队列用堆来实现

优先队列(Priority Queue)的实现通常选择堆(Heap)作为其底层数据结构,而不是普通队列(Queue)。以下是几个关键原因:

  1. 数据结构和操作特性
    • 普通队列(Queue)遵循先进先出(FIFO)的原则,即最先进入队列的元素将最先被移除。
    • 优先队列(Priority Queue)则允许元素具有优先级,优先级最高的元素将最先被移除,这体现了最高级先出(first in, largest out 或 first in, smallest out,取决于优先级的定义)的行为特征。
  2. 堆的性质
    • 堆是一种特殊的树形数据结构,它可以被看作是完全二叉树或近似完全二叉树。
    • 堆总是满足堆属性:父节点的值总是大于或等于(最大堆)或小于或等于(最小堆)其子节点的值。
    • 堆提供了快速访问最大或最小元素(即堆顶元素)的能力,并且可以在对数时间内完成插入和删除操作。
  3. 实现优先队列
    • 由于堆提供了高效的插入和删除最大/最小元素的操作,因此它非常适合用于实现优先队列。
    • 当有新元素需要插入到优先队列中时,可以直接将其插入到堆中,并重新调整堆以保持堆属性。
    • 当需要从优先队列中移除最高优先级的元素时,可以直接移除堆顶元素,并重新调整堆。
  4. 代码示例和设置
    • 在C++的STL(Standard Template Library)中,priority_queue容器就是一个典型的优先队列实现,其底层就是使用堆。
    • 通过设置priority_queue的第三个模板参数(比较类),可以定义队列中元素的优先级。例如,使用greater<int>可以使队列成为小根堆,这样数字小的元素优先级更高;而默认是大根堆,数字大的元素优先级更高。

综上所述,优先队列通常使用堆作为其底层数据结构,以提供高效的插入和删除最高/最低优先级元素的操作。

3.当上下限表达式相等时,我们使用下列哪种表示法来描述算法代价? 

Θ表示法(Theta notation)用于描述算法的紧确界限,即它同时表示了算法的上限和下限复杂度。当算法的上下限复杂度相同时,Θ表示法是最合适的。 

相关文章:

算法 | 刷题日记

1.递归通常是用栈来实现的 递归在其本质上是通过函数调用栈&#xff08;Call Stack&#xff09;来实现的&#xff0c;而不是队列&#xff08;Queue&#xff09;。当你调用一个函数时&#xff0c;该函数的局部变量、参数和返回地址会被压入&#xff08;push&#xff09;到一个由…...

微信小程序登录接口

微信小程序登录&#xff0c;实现思路分析&#xff1a; 用户触发登录操作&#xff1a;用户在微信小程序中点击“登录”按钮&#xff0c;触发登录流程。调用微信登录接口&#xff1a;小程序端调用微信提供的登录接口&#xff08;如wx.login&#xff09;&#xff0c;获取临时登录…...

VBA实战(Excel)(5):介绍一种排列组合算法

1. 需求场景 有多个条件&#xff0c;条件个数不定&#xff0c;每个条件有若干种情况&#xff0c;情况个数不定&#xff0c;输出所有条件可能的情况的排列组合。 2.举例 假设第一次有5个情况要填&#xff0c;第一个条件20种情况&#xff0c;第二个5种&#xff0c;第三个40种&…...

迭代器的使用

参考&#xff1a; 生成器迭代器next函数 迭代器的使用 说到迭代器就必须先要提一下可迭代对象&#xff08;iterable&#xff09;&#xff0c;可迭代对象是能够逐一返回其成员项的对象。可迭代对象包括序列类型&#xff08;如list、str、tuple&#xff09;和非序列类型&#…...

安卓手机APP开发___广播概述

安卓手机APP开发___广播概述 目录 概述 关于系统广播 系统广播所发生的更改 接收广播 清单声明的接收器 上下文注册的接收器 对进程状态的影响 发送广播 通过权限限制广播 带权限的发送 带权限的接收 安全注意事项和最佳做法 概述 Android 应用可以通过 Android …...

【封装】Unity切换场景不销毁物体

在切换场景时&#xff0c;如果物体不需要销毁&#xff0c;可以直接使用下方脚本 代码 public class DontDestroyLoader : MonoBehaviour{ //所有不销毁的物体预制体[SerializeField] private GameObject[] dontDestroyPrefabs;//实例化预制体public void Load(){foreach (var …...

基于学习的决策树

基于学习的决策树概述 决策树是一种监督学习方法&#xff0c;广泛应用于分类和回归任务中。基于学习的决策树模型通过学习数据中的特征来构建树状结构&#xff0c;帮助做出决策。以下是对基于学习的决策树的详细介绍&#xff0c;包括其基本概念、工作流程、构建算法、优势和挑…...

godot.bk2

1.$node_name 其实 就是 get_node 的语法糖 2.场景内部用get_node&#xff0c;场景外部用信号 这是自定义信号的绑定&#xff0c;如果是内置信号&#xff0c;直接右键点击链接到一个函数即可 3.场景切换和摄像头一直居中 4.class_name命名一个类&#xff0c;extends继承&…...

STM32 IIC 使用 HAL 库操作eeprom

在STM32上通过I2C接口&#xff08;注意&#xff1a;在标准STM32库中&#xff0c;I2C接口通常被写为"I2C"而不是"IIC"&#xff09;与EEPROM芯片通信时&#xff0c;你需要遵循I2C通信协议&#xff0c;并使用STM32的HAL库或标准外设库&#xff08;如果适用&am…...

YOLOv8+PyQt5海洋船只检测(可以重新训练,yolov8模型,从图像、视频和摄像头三种路径识别检测)

1.效果视频&#xff1a;海洋船只检测yoloV8检测&#xff08;https://mbd.pub/o/bread/mbd-ZpaYk55r&#xff09;_哔哩哔哩_bilibili资源包含可视化的海洋船只检测系统&#xff0c;可对于高空拍摄到的海洋图片进行轮船检测&#xff0c;基于最新的YOLOv8训练的海洋船只检测模型&a…...

PCL 高阶多项式曲线回归拟合(二维)

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 高阶多项式曲线回归(Polynomial Regression)是一种线性回归模型的扩展,它允许数据拟合一个非线性的曲线。虽然多项式本身是非线性的,但我们可以通过引入新的变量(例如,原始变量的平方、立方等)来将问题转化为…...

深入理解 Python3 函数:从基础语法到高级应用

Python3 函数是构建模块化代码的基本单位&#xff0c;允许我们将代码组织成独立的、可重用的块。本文将详细介绍 Python3 函数的基本语法、常用命令、示例、应用场景、注意事项&#xff0c;并进行总结。 基本语法 在 Python 中&#xff0c;函数的定义使用 def 关键字&#xf…...

03_初识Spring Cloud Gateway

文章目录 一、网关简介1.1 网关提出的背景1.2 网关在微服务中的位置1.3 网关的技术选型1.4 补充 二、Spring Cloud Gateway的简介2.1 核心概念&#xff1a;路由&#xff08;Route&#xff09;2.2 核心概念&#xff1a;断言&#xff08;Predicate&#xff09;2.3 核心概念&#…...

python数据分析——线性模型

参考资料&#xff1a;活用pandas库 1、简单线性回归 线性回归的目标是描述响应变量&#xff08;或“因变量”&#xff09;和预测变量&#xff08;也称“特征”、“协变量”、“自变量”&#xff09;之间的直线关系。本例中将讨论tips数据集中的total_bill对tip的影响。 # 导入…...

网络原理——HTTP/HTTPS ---- HTTPS

T04BF &#x1f44b;专栏: 算法|JAVA|MySQL|C语言 &#x1faf5; 今天你敲代码了吗 目录 HTTPS加密与解密HTTPS的工作流程使用对称密钥来加密使用非对称密钥 来对 对称密钥进行加密第三方公证总结 HTTPS https本质上就是在http的基础之上 增加了加密层,抛开加密层之后,剩下的部…...

网络协议二

一、套接字Socket 基于 TCP UDP 协议的 Socket 编程&#xff0c;在讲 TCP 和 UDP 协议的时候&#xff0c;我们分客户端和服务端&#xff0c;在写程序的时候&#xff0c;我们也同样这样分。 在网络层&#xff0c;Socket 函数需要指定到底是 IPv4 还是 IPv6&#xff0c;分别对应设…...

内存映射mmap技术详解

一、mmap基础概念 mmap 即 memory map&#xff0c;也就是内存映射。mmap 是一种内存映射文件的方法&#xff0c;即将一个文件或者其它对象映射到进程的地址空间&#xff0c;实现文件磁盘地址和进程虚拟地址空间中一段虚拟地址的一一对映关系。实现这样的映射关系后&#xff0c;…...

react 合成事件

React合成事件-CSDN博客 当然&#xff0c;很高兴为你解释React中的合成事件概念&#xff0c;非常适合React初学者理解。 想象一下&#xff0c;你正在组织一场派对&#xff0c;为了让派对顺利进行&#xff0c;你需要管理各种活动&#xff0c;比如游戏、音乐和食物分配。但是&a…...

springboot配置集成RedisTemplate和Redisson,使用分布式锁案例

文章要点 自定义配置属性类集成配置RedisTemplate集成配置分布式锁Redisson使用分布式锁简单实现超卖方案 1. 项目结构 2. 集成RedisTemplate和Redisson 添加依赖 依赖的版本与继承的spring-boot-starter-parent工程相对应&#xff0c;可写可不写 <!--spring data redis…...

随机数相关

产生随机数对象 固定写法&#xff1a; Random 随机数变量名 new Random();Random r new Random();生成随机数 int i r.Next(); //生成一个非负数的随机数 Console.WriteLine(i);i r.Next(100); // 生成一个 0~99的随机数 左边始终是0 左包含 右边是100 右不包含 Consol…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...