【数据结构与算法】【腾讯阿里链表面试题】算法题--链表易懂版讲解
🎉🎉欢迎光临🎉🎉
🏅我是苏泽,一位对技术充满热情的探索者和分享者。🚀🚀
🌟特别推荐给大家我的最新专栏《Spring 狂野之旅:底层原理高级进阶》 🚀《数据结构与算法:初学者入门指南》📘📘《Spring 狂野之旅:底层原理高级进阶》 🚀
本专栏纯属为爱发电永久免费!!!
这是苏泽的个人主页可以看到我其他的内容哦👇👇
努力的苏泽
http://suzee.blog.csdn.net/
前景回顾:我们用 环形链表的方法巧妙解决了约瑟夫问题 可是链表就到处为止了吗?当然不是 下面带给大家两道我刷过较为经典的算法题 两道面试的真题 一道是tx 一道阿里的
目录
腾讯面试题:复制随机节点
题目说明:
输入示例:
输出示例:
时间复杂度:O(n)
空间复杂度:O(n)
解析
题目分析:
解题过程:
阿里巴巴面试题:合并K个排序链表
题目说明:
输出示例:
时间复杂度:O(N*log(k))
空间复杂度:O(k)
解析
题目分析:
解题过程:
腾讯面试题:复制随机节点
题目说明:
给定一个链表,每个节点包含一个指向任意节点的随机指针,同时每个节点有一个指向同一链表中节点的指针,输出这个链表的深拷贝。
输入示例:
输入:
Node* p = new Node(p1);
p1 = new Node(p2);
p2 = new Node(p3);
p3 = new Node(null);
// 随机连接
p->random = p2;
p1->random = null;
p2->random = p3;Node* clone = cloneRandomNode(p);
输出示例:
返回与原链表相同结构的复制链表,并正确设置每个节点的随机指针。
时间复杂度:O(n)
- 其中 n 是链表的长度,我们需要遍历整个链表一次来创建复制品。
空间复杂度:O(n)
- 存储复制的节点需要额外的空间。
解析
题目分析:
这个问题要求我们复制一个链表,其中每个节点包含一个指向任意节点的随机指针。我们需要返回这个链表的深拷贝,并正确设置每个节点的随机指针。
解题过程:
-
首先,我们遍历原始链表,对于每个节点,创建一个新节点,并将其插入到原节点的后面。这样我们就可以同时访问原始节点和新节点。例如,原始链表为
1 -> 2 -> 3
,复制后变为1 -> 1' -> 2 -> 2' -> 3 -> 3'
。原始链表: 1 -> 2 -> 3 复制后的链表: 1' -> 2' -> 3'
-
然后,我们再次遍历链表,这次是为了设置每个新节点的随机指针。我们根据原节点的随机指针找到对应的新节点,并将其设置为新节点的随机指针。例如,如果原节点
2
的随机指针指向3
,那么新节点2'
的随机指针应该指向3'
。原始链表: 1 -> 2 -> 3 复制后的链表: 1' -> 2' -> 3' 随机指针: N -> 2 -> N 复制后的随机指针: N -> 2' -> N
-
最后,我们将新旧节点分离,并返回复制链表的头节点。例如,将
1 -> 1' -> 2 -> 2' -> 3 -> 3'
分离成1 -> 2 -> 3
和1' -> 2' -> 3'
,然后返回1'
作为复制链表的头节点。
原始链表: 1 -> 2 -> 3
复制后的链表: 1' -> 2' -> 3'
分离后的链表: 1 -> 2 -> 3
分离后的复制链表: 1' -> 2' -> 3'
返回头节点: 1'
class Node:def __init__(self, val=0, next=None, random=None):self.val = valself.next = nextself.random = randomdef cloneRandomNode(head):if not head:return None# 第一步:复制每个节点,并将新节点插入原节点后面curr = headwhile curr:new_node = Node(curr.val)new_node.next = curr.nextcurr.next = new_nodecurr = new_node.next# 第二步:设置每个新节点的随机指针curr = headwhile curr:curr.next.random = curr.random.next if curr.random else Nonecurr = curr.next.next# 第三步:分离新旧节点,返回复制链表的头节点curr = headnew_head = head.nextwhile curr:next_old = curr.nextnext_new = curr.next.nextcurr.next = next_newif next_new:curr.next.next = next_oldcurr = next_oldreturn new_head
阿里巴巴面试题:合并K个排序链表
题目说明:
给你一个链表数组,每个链表都已经按升序排列,请你将所有的链表合并到一个升序链表中,返回合并后的链表。
复制代码
输入:
lists = [[1,4,5],[1,3,4],[2,6]]
输出示例:
输出:[1,1,2,3,4,4,5,6]
时间复杂度:O(N*log(k))
- 其中 N 是所有链表中元素的总数,k 是链表的个数。假设使用最小堆处理每个链表的头部元素。
空间复杂度:O(k)
- 存储 k 个链表头部节点所需的空间。
解析
题目分析:
这个问题要求我们合并 k 个已排序的链表,并返回一个新的升序链表。我们可以使用分治法来解决这个问题。
解题过程:
-
我们使用最小堆来存储每个链表的头部节点。这样可以快速地找到当前最小的节点。例如,如果有三个链表分别为
1 -> 4 -> 5
、1 -> 3 -> 4
和2 -> 6
,则最小堆中的元素为(1, node1)
、(1, node2)
和(2, node3)
。链表1: 1 -> 4 -> 5 链表2: 1 -> 3 -> 4 链表3: 2 -> 6 最小堆: (1, node1), (1, node2), (2, node3)
-
我们创建一个虚拟头节点
dummy
,用于连接所有合并后的节点。 -
我们不断从最小堆中取出最小的节点,将其连接到结果链表中,并将该节点的下一个节点加入堆中,直到堆为空。例如,我们从最小堆中取出
(1, node1)
,将其连接到结果链表中,然后将node1.next
(即值为4
的节点)加入堆中。结果链表: dummy -> 1 最小堆: (1, node2), (4, node4), (6, node6)
-
最后,我们返回合并后链表的头节点。例如,最终的结果链表为
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
,返回dummy.next
。
结果链表: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
返回头节点: 1
import heapq
from typing import List, Optionalclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:if not lists:return None# 使用最小堆来存储每个链表的头部节点min_heap = []for node in lists:if node:heapq.heappush(min_heap, (node.val, node))dummy = ListNode()current = dummy# 每次从堆中取出最小的节点,将其连接到结果链表中,并将该节点的下一个节点加入堆中while min_heap:val, node = heapq.heappop(min_heap)current.next = ListNode(val)current = current.nextif node.next:heapq.heappush(min_heap, (node.next.val, node.next))return dummy.next
相关文章:

【数据结构与算法】【腾讯阿里链表面试题】算法题--链表易懂版讲解
🎉🎉欢迎光临🎉🎉 🏅我是苏泽,一位对技术充满热情的探索者和分享者。🚀🚀 🌟特别推荐给大家我的最新专栏《Spring 狂野之旅:底层原理高级进阶》 🚀…...

3d渲染100农场如何使用?渲染100邀请码1a12
3d渲染农场通常用于电影、动画或视觉效果的渲染,本文以广受好评的渲染100农场为例,来讲解它的使用方法。 1、注册账号 前往渲染100官网(http://www.xuanran100.com/?ycode1a12)注册账号, 新用户注册记得填邀请码1a12,有30元大礼…...

【数据结构和算法】--- 基于c语言排序算法的实现(2)
目录 一、交换排序1.1 冒泡排序1.2 快速排序1.2.1 hoare法1.2.2 挖坑法1.2.3 前后指针法 1.3 快速排序优化1.3.1 三数取中法选key1.3.2 递归到小的子区间使用插入排序 1.4 快排非递归版 二、归并排序2.1 归并排序2.1.1 递归版2.1.2 非递归版 一、交换排序 基本思想:…...
ORACLE的 软 软 软 解析!
在海鲨数据库架构师精英群里,有位朋友说ORACLE 有 软软软解析. 就是把执行计划缓存在客户端里,从而避免去服务端找执行计划. 他给了个设置方法, Weblogic console->datasource->connectionPool Statement Cache Type >LRU Statement Cache Size100 CURSOR_NUMBER …...
【模板】k 短路 / [SDOI2010] 魔法猪学院
题目背景 注:对于 k k k 短路问题,A* 算法的最坏时间复杂度是 O ( n k log n ) O(nk \log n) O(nklogn) 的。虽然 A* 算法可以通过本题原版数据,但可以构造数据,使得 A* 算法在原题的数据范围内无法通过。事实上,…...
【Make编译控制 08】CMake动静态库
目录 一、编译动静态库 二、链接静态库 三、链接动态库 前情提示:【Make编译控制 07】CMake常用命令-CSDN博客 有些时候我们编写的源代码并不需要将他们编译生成可执行程序,而是生成一些静态库或动态库提供给第三方使用,所以我们需要用到…...

05 06 Verilog基础语法与应用讲解
05. 1. 位操作 计数器实验升级,设计8个LED灯以每个0.5s的速率循环闪烁(跑马灯) 1.1 方法1:使用移位操作符<<来控制led灯的循环亮灭 设计代码 Verilog中,判断操作的时候不加位宽限定是可以的,比如i…...

css2复合选择器
一.后代(包含)选择器(一样的标签可以用class命名以分别) 空格表示 全部后代 应用 二.子类选择器 >表示 只要子不要孙 应用 三.并集选择器 ,表示 代表和 一般竖着写 应用 四.伪类选择器(包括伪链接…...

新版MQL语言程序设计:键盘快捷键交易的设计与实现
文章目录 一、什么是快捷键交易二、使用快捷键交易的好处三、键盘快捷键交易程序设计思路四、键盘快捷键交易程序具体实现1.界面设计2.键盘交易事件机制的代码实现 一、什么是快捷键交易 操盘中按快捷键交易是指在股票或期货交易中,通过使用快捷键来进行交易操作的…...
数据结构之基数排序
基数排序的思想是按组成关键字的各个数位的值进行排序,它是分配排序的一种。在该排序方法中把一个关键字 Ki看成一个 d 元组,即 K1i,K2i,,Kdi 其中,0≤ Kji<r,i1~ n,j1~d。这里的r 称为基数。若关键字是…...

区间dp 笔记
区间dp一般是先枚举区间长度,再枚举左端点,再枚举分界点,时间复杂度为 环形石子合并 将 n 堆石子绕圆形操场排放,现要将石子有序地合并成一堆。 规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记做该…...

MySQL-SQL优化
文章目录 1. SQL性能分析1.1 SQL执行频率1.2 慢查询日志1.3 profile详情1.4 explain 2. SQL优化2.1 Insert 优化2.2 Group By 优化2.3 Order By 优化2.4 Limit 优化2.5 Count() 优化2.6 Update 优化 3. 拓展3.1 请你说一下MySQL中的性能调优的方法?3.2 执行 SQL 响应…...

详细了解ref和reactive.
这几天看到好多文章标题都是类似于: 不用 ref 的 xx 个理由不用 reactive 的 xx 个理由历数 ref 的 xx 宗罪 我就很不解,到底是什么原因导致有这两批人: 抵触 ref 的人抵触 reactive 的人 看了这些文章,我可以总结出他们的想法…...

使用Linux docker方式快速安装Plik并结合内网穿透实现公网访问
文章目录 1. Docker部署Plik2. 本地访问Plik3. Linux安装Cpolar4. 配置Plik公网地址5. 远程访问Plik6. 固定Plik公网地址7. 固定地址访问Plik 本文介绍如何使用Linux docker方式快速安装Plik并且结合Cpolar内网穿透工具实现远程访问,实现随时随地在任意设备上传或者…...

Redis Centos7 安装到启动
文章目录 安装Redis启动redis查看redis状况连接redis服务端 安装Redis 1.下载scl源 yum install centos-release-scl-rh2.下载redis yum install rh-redis5-redis 3. 创建软连接 1.cd /usr/bin 2. In -s /opt/rh/rh-redis5/root/usr/bin/redis-server ./redis-server 3. …...

「数据结构」二叉搜索树1:实现BST
🎇个人主页:Ice_Sugar_7 🎇所属专栏:Java数据结构 🎇欢迎点赞收藏加关注哦! 实现BST 🍉二叉搜索树的性质🍉实现二叉搜索树🍌插入🍌查找🍌删除 &am…...

可达鸭二月月赛——基础赛第六场(周五)题解,这次四个题的题解都在这一篇文章内,满满干货,含有位运算的详细用法介绍。
姓名 王胤皓 T1 题解 T1 题面 T1 思路 样例输入就是骗人的,其实直接输出就可以了,输出 Hello 2024,注意,中间有一个空格! T1 代码 #include<bits/stdc.h> using namespace std; #define ll long long int …...

ELFK日志采 - QuickStart
文章目录 架构选型ELKEFLK ElasticsearchES集群搭建常用命令 Filebeat功能介绍安装步骤Filebeat配置详解filebeat常用命令 Logstash功能介绍安装步骤Input插件Filter插件Grok Filter 插件Mutate Filter 插件常见的插件配置选项:Mutate Filter配置案例: O…...

微信小程序的图片色彩分析,窃取网络图片的主色调
1、安装 Mini App Color Thief 包 包括下载包,简单使用都有,之前写了,这里就不写了 网址:微信小程序的图片色彩分析,窃取主色调,调色板-CSDN博客 2、 问题和解决方案 问题:由于我们的窃取图片的…...
Leetcode 121 买卖股票的最佳时机
题意理解: 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交…...

【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...

【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...

论文阅读:Matting by Generation
今天介绍一篇关于 matting 抠图的文章,抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法,已经有很多的工作和这个任务相关。这两年 diffusion 模型很火,大家又开始用 diffusion 模型做各种 CV 任务了&am…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例
目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码:冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...
32单片机——基本定时器
STM32F103有众多的定时器,其中包括2个基本定时器(TIM6和TIM7)、4个通用定时器(TIM2~TIM5)、2个高级控制定时器(TIM1和TIM8),这些定时器彼此完全独立,不共享任何资源 1、定…...