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

【左程云算法全讲2】链表、栈、队列、递归、哈希表和有序表

系列综述:
💞目的:本系列是个人整理为了秋招面试的,整理期间苛求每个知识点,平衡理解简易度与深入程度。
🥰来源:材料主要源于左程云算法课程进行的,每个知识点的修正和深入主要参考各平台大佬的文章,其中也可能含有少量的个人实验自证。
🤭结语:如果有帮到你的地方,就点个赞关注一下呗,谢谢🎈🎄🌷!!!
🌈【C++】秋招&实习面经汇总篇


文章目录

      • 面试技巧
      • 链表
      • 栈和队列
      • 递归
    • 参考博客


😊点此到文末惊喜↩︎

面试技巧

  1. 写算法时候也要阐述自己的思路,即使写不出来
  2. 面试的算法:必须找到最优的解

链表

  1. 单向链表数据结构
    // 单链表数据结构
    struct LinkNode {int val;struct LinkNode *next;LinkNode(int v): val(v), next(nullptr){}
    };
    // 反转单链表
    LinkNode *ReverseLinkList(LinkNode *head) {LinkNode *prev = nullptr;LinkNode *next = nullptr;while (head != nullptr) {	// head充当cur指针,表示每个操作的结点next = head->next;	// 记录值head->next = prev;prev = head;		// 两个指针的迭代head = next;}return prev;
    }
    
  2. 双向链表数据结构
    • 使用双链表作为底层实现栈和队列
    struct LinkNode {int val;struct LinkNode *prev;struct LinkNode *next;LinkNode(int v): val(v), prev(nullptr), next(nullptr){}
    };
    // 反转双向链表
    LinkNode *ReverseLinkList(LinkNode *head) {LinkNode *prev = nullptr;LinkNode *next = nullptr;while (head != nullptr) {	// head充当cur指针,表示每个操作的结点next = head->next;		// 记录值head->next = prev;		// key:当前双链表结点两个指针反转head->prev = next;prev = head;			// 两个指针的迭代head = next;}return prev;
    }// 删除指定结点
    ListNode *DeleteTarget(ListNode *head, int target) {ListNode *vhead = new ListNode(-1);vhead->next = head;ListNode *prev = vhead;ListNode *cur = head;while (cur != nullptr) {if (cur->val == target) {ListNode *p = cur;cur = cur->next;delete p;		// 释放结点,jvm会自动释放prev->next = cur;} else {prev = cur;cur = cur->next;}}return vhead->next;
    }
    设计一个模板双链表,可以进行头部和尾部的增删,以及改查操作,并进行优化
    

栈和队列

  1. 双链表实现栈和队列

  2. 数组实现栈和队列

    • 数组队列的实现应该是一个环状结构,使用
  3. 以O(1)时间获取当前栈的最小值

    • leetcode题目:最小栈
    • 思路1:最小栈同步记录对应的栈内最小值
    • 思路2:最小栈只记录栈内的最小值,只有当前栈和最小栈顶元素相等,最小栈栈顶才弹出
class MinStack {
public:/** initialize your data structure here. */MinStack() {min_st.push(INT_MAX);}void push(int x) {cur_st.push(x);int p = min_st.top();// 最小栈的栈顶一直记录栈内的最小值if (x <= p) {min_st.push(x);} else {min_st.push(p);}}void pop() {cur_st.pop();min_st.pop();}int top() {return cur_st.top();}int getMin() {return min_st.top();}
private:// 使用两个栈记录,一个记录当前栈,另一个栈顶一直为栈内最小元素stack<int> cur_st;	stack<int> min_st;
};
  1. 使用实现队列
    • 思路:两个栈,一个记录压入的元素,一个记录弹出的元素。
class MyQueue {
public:MyQueue() {}// 弹出栈为空则压入栈全部倒进弹出栈中void PushToPop(){if (pop_st.empty()) {while (!push_st.empty()) {pop_st.push(push_st.top());push_st.pop();}}}// 压入一个,则尝试倒栈void push(int x) {push_st.push(x);PushToPop();}// 先倒栈,在尝试弹出int pop() {PushToPop();int p = pop_st.top();pop_st.pop();return p;}int peek() {PushToPop();return pop_st.top();}bool empty() {return pop_st.empty() && push_st.empty();}
private:stack<int> push_st;stack<int> pop_st;
};
  1. 使用队列实现
    • 思路:将队列头部的元素按序重新添加到队列尾部,其中最后一个即栈顶元素
class MyStack {
public:queue<int> que;/** Initialize your data structure here. */MyStack() { }/** Push element x onto stack. */void push(int x) {que.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {int size = que.size();size--;while (size--) { // 将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部que.push(que.front());que.pop();}int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了que.pop();return result;}// 队列的末尾元素即为栈顶元素int top() {return que.back();}/** Returns whether the stack is empty. */bool empty() {return que.empty();}
};

递归

  1. 递归的固定参数可以使用全局或者引用,其中的可变参数作为参数
  2. 递归求数组的最大值
int process(vector<int> &vec, int L, int R) {if (L == R) return vec[L];int mid = L + ((R-L)>>1);int left_max = process(vec, L, mid);int right_max = process(vec, mid+1, R);return max(left_max, right_max);
}
  1. 任何递归都可以改成非递归,因为递归本质利用了系统栈
  2. 特殊复杂度 T ( N ) = a ∗ T ( N / b ) + O ( N c ) T(N) = a*T(N/b) + O(N^c) T(N)=aT(N/b)+O(Nc),其中a、b和c都是常数,a是递归次数,b为递归划分分数,c
    • 如果 l o g b a < d log_ba < d logba<d,复杂度为 O ( N d ) O(N^d) O(Nd)
    • 如果 l o g b a > d log_ba > d logba>d,复杂度为 O ( N l o g b a ) O(N^{log_ba}) O(Nlogba)
    • 如果 l o g b a = d log_ba = d logba=d,复杂度为 O ( N d ∗ l o g N ) O(N^d * logN) O(NdlogN)


少年,我观你骨骼清奇,颖悟绝伦,必成人中龙凤。
不如点赞·收藏·关注一波

🚩点此跳转到首行↩︎

参考博客

  1. 对数器
  2. 单调队列
  3. 快速链表quicklist
  4. 《深入理解计算机系统》
  5. 侯捷C++全系列视频
  6. 待定引用
  7. 待定引用
  8. 待定引用

相关文章:

【左程云算法全讲2】链表、栈、队列、递归、哈希表和有序表

系列综述&#xff1a; &#x1f49e;目的&#xff1a;本系列是个人整理为了秋招面试的&#xff0c;整理期间苛求每个知识点&#xff0c;平衡理解简易度与深入程度。 &#x1f970;来源&#xff1a;材料主要源于左程云算法课程进行的&#xff0c;每个知识点的修正和深入主要参考…...

SQL第三次上机作业

1.查询与王利就读同一专业学生的借书证号和姓名 SELECT Lno,Rname FROM Reader WHERE Dept(SELECT DeptFROM ReaderWHERE Rname王利)2.查询比希望出版社出版的所有图书价格都高的图书信息 SELECT * FROM Book WHERE Price>(SELECT MAX(Price)FROM BookWHERE Press希望出版…...

前端事件案例补充

目录 定时器示例 搜索框示例 省市联动 定时器示例 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title><meta name"viewport" content"widthdevice-width, init…...

3.8 Android eBPF HelloWorld调试(二)

写在前面 我们开发eBPF程序的初衷就是再不改动内核的情况下,将内核监控数据传递给到用户态;像应用进程开发一样开发内核监控程序。 Android开机的时候eBPF程序被加载器加载到内核中,但此时它并没有被附加到内核函数上去,也就是ebpf程序并不会执行,我们可以理解为,它仅仅被…...

xss如何快速提取cookies

<script>alert(111)</script> <img srcx onerroralert(document.cookie)>测试一下baidu的xss <script>alert(111)</script><img srcx οnerrοralert(document.cookie)>...

在 ASP.NET C# 中用Aspose.PDF将 PDF 页面转换为 JPG 图像

PDF 是一种通用格式&#xff0c;通常用于打印和共享文档。 &#xff08;一&#xff09;C# PDF to JPG Converter API - 免费下载 Aspose.PDF for .NET是一个强大的 PDF 操作 API&#xff0c;可让您在 .NET 应用程序中创建和处理 PDF 文件。此外&#xff0c;它还允许您将 PDF 文…...

Docker Compose安装milvus向量数据库单机版-milvus基本操作

目录 安装Ubuntu 22.04 LTS在power shell启动milvus容器安装docker desktop下载yaml文件启动milvus容器Milvus管理软件Attu python连接milvus配置下载wget示例导入必要的模块和类与Milvus数据库建立连接创建名为"hello_milvus"的Milvus数据表插入数据创建索引基于向量…...

极致性能优化:前端SSR渲染利器Qwik.js | 京东云技术团队

引言 前端性能已成为网站和应用成功的关键要素之一。用户期望快速加载的页面和流畅的交互&#xff0c;而前端框架的选择对于实现这些目标至关重要。然而&#xff0c;传统的前端框架在某些情况下可能面临性能挑战且存在技术壁垒。 在这个充满挑战的背景下&#xff0c;我们引入…...

ES6~ES13新特性(二)

文章目录 一、ES71.Array Includes2.指数exponentiation运算符 二、ES81.Object values2.Object entries3.String Padding4.Trailing Commas5.Object Descriptors 三、ES9四、ES101.flat flatMap2.Object fromEntries3.trimStart、trimEnd4.其他知识点 五、ES111.BigInt2.Nulli…...

soildwork2022怎么样添加螺纹孔?

1.退出草图模式&#xff0c;点击需要添加螺纹孔的物体面&#xff0c;选中“特征”中的“异形孔向导” 2.选中“孔类型”为“直螺纹孔”&#xff0c;“标准”&#xff0c;“类型”&#xff0c;“孔规格”终止条件等。 3.设置完之后选择“位置” 4.鼠标左键在物体面上点一下&…...

【t5 pytorch版源码学习】t5-pegasus-pytorch源码学习

0. 项目来源 中文生成式预训练模型&#xff0c;以mT5为基础架构和初始权重&#xff0c;通过类似PEGASUS的方式进行预训练。 bert4keras版&#xff1a;t5-pegasus pytorch版&#xff1a;t5-pegasus-pytorch 本次主要学习pytorch版的代码解读。 项目结构&#xff1a; train…...

【springboot】spring的Aop结合Redis实现对短信接口的限流

前言 场景: 为了限制短信验证码接口的访问次数&#xff0c;防止被刷&#xff0c;结合Aop和redis根据用户ip对用户限流 1.准备工作 首先我们创建一个 Spring Boot 工程&#xff0c;引入 Web 和 Redis 依赖&#xff0c;同时考虑到接口限流一般是通过注解来标记&#xff0c;而注解…...

【MedusaSTears】怎么禁用edge浏览器截图功能?

版本 Microsoft Edge 版本 119.0.2151.44 (正式版本) (64 位) Ctrl Shift S 竟然是浏览器的截屏? 特么的啥时候多了这么个快捷键? 然后还没办法禁用,真TMD傻哔 edge://settings/accessibility解决方式: 参考资料: 怎么禁用edge浏览器截图功能&#xff1f; 您好&#x…...

【计算机网络】(谢希仁第八版)第三章课后习题答案

第三章 1.数据链路(即逻辑链路)与链路(即物理链路)有何区别? “电路接通了”与”数据链路接通了”的区别何在? 答&#xff1a;数据链路与链路的区别在于数据链路出链路外&#xff0c;还必须有一些必要的规程来控制数据的传输&#xff0c;因此&#xff0c;数据链路比链路多了…...

批量异步任务处理

当我们在项目中遇到很多业务同时处理&#xff0c;如果是串行肯定是影响性能的&#xff0c;这时候就需要异步执行了&#xff0c;说道异步肯定就有很多方案了 方案一&#xff1a; 比如使用spring的异步注解&#xff0c;比如下面的代码,每个方法上面都是异步注解&#xff0c;当时…...

宜昌市公安局、点军区政府与中科升哲达成战略合作,共建视频图像联合创新实验室

11月3日&#xff0c;宜昌视频图像联合创新战略合作签约仪式在宜昌市公安局举行。 宜昌市副市长、市公安局党委书记、局长上官福令&#xff0c;市公安局党委副书记、副局长龚海波&#xff0c;宜昌市点军区委书记万红&#xff0c;点军区委副书记、区长黄文云&#xff0c;升哲科技…...

java版小程序商城免费搭建-直播商城平台规划及常见的营销模式有哪些?电商源码/小程序/三级分销

1. 涉及平台 平台管理、商家端&#xff08;PC端、手机端&#xff09;、买家平台&#xff08;H5/公众号、小程序、APP端&#xff08;IOS/Android&#xff09;、微服务平台&#xff08;业务服务&#xff09; 2. 核心架构 Spring Cloud、Spring Boot、Mybatis、Redis 3. 前端框架…...

Linux下yum源配置实战

一、Linux下软件包的管理 1、软件安装方式 ① RPM包管理&#xff08;需要单独解决依赖问题&#xff09; ② YUM包管理&#xff08;需要有网络及YUM仓库的支持&#xff0c;会自动从互联网下载软件&#xff0c;自动解决依赖&#xff09; ③ 源码安装&#xff08;安装过程比较…...

JSONP 跨域访问(2), JSONP劫持

JSONP 跨域访问(2), JSONP劫持 一, 利用 XSS 漏洞执行jsonp 1. 利用过程 发现有jsonp的请求: <script type"text/javascript" src"http://192.168.112.200/security/jsonp.php?callbackjsonpCallback"></script>向xss漏洞的位置注入代码…...

【java】实现自定义注解校验——方法一

自定义注解校验的实现步骤&#xff1a; 1.创建注解类&#xff0c;编写校验注解&#xff0c;即类似NotEmpty注解 2.编写自定义校验的逻辑实体类&#xff0c;编写具体的校验逻辑。(这个类可以实现ConstraintValidator这个接口&#xff0c;让注解用来校验) 3.开启使用自定义注解进…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...