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

【每日一题】2012考研数据结构 - 求字符串链表公共后缀

本篇文章将为大家讲解一道关于链表的经典题目——求两个链表的共同后缀节点。该问题在实际开发中同样具有很大的应用价值,是每一位数据结构学习者不可错过的重要题目。

问题描述

假设我们有一个带头结点的单链表来保存单词,每个节点包含一个字符和指向下一个节点的指针。若两个单词的后缀相同,它们可以共享相同的后缀存储空间。例如:

  • 单词loadingbeing 有相同的后缀 ing,可以共享存储。

题目要求

str1str2 分别指向两个单词所在链表的头节点,请设计一个尽可能高效的算法,找出两个链表共同后缀的起始位置。

要求:

  1. 给出算法的设计思想。
  2. 使用 C++ 代码实现算法,并在关键部分给出注释。
  3. 分析算法的时间复杂度。

设计思路

1. 暴力匹配法

最直接的思路是将链表 str1 的每一个节点依次与链表 str2 的节点进行匹配,如果匹配到相同的节点,则继续向后比较,直到找到第一个完全相同的后缀位置。

实现步骤

  1. 从链表 str1 开始的每个节点,分别与 str2 中的节点开始逐一匹配。
  2. 若匹配的节点数据相同,继续匹配下一个节点;若不相同则跳到下一个节点。
  3. 当匹配到第一个后缀起始点时,返回该节点位置。
#include "bits/stdc++.h"using namespace std;struct Node{int value;Node* next;
};bool check(Node* first, Node* second) {Node* l = first;Node* r = second;while(l != nullptr && r != nullptr) {if(l -> value != r ->value) return false;l = l -> next;r = r -> next;}return l  == nullptr &&  r  == nullptr;
}Node* search(Node* first, Node* second) {Node* x = first;while(x != nullptr ) {Node*  y = second;while(y != nullptr) {if(x -> value == y -> value && check(x, y)) {return x;}y = y -> next;}x = x -> next;}return nullptr;
}int main() {Node* common = new Node{'i', new Node{'n', new Node{'g', nullptr}}};// 创建两个测试链表Node* str1 = new Node{ 'l', nullptr };str1->next = new Node{ 'o', nullptr };str1->next->next = new Node{ 'a', nullptr };str1->next->next->next = new Node{ 'd', nullptr };str1->next->next->next->next = common;Node* str2 = new Node{ 'b', nullptr };str2->next = new Node{ 'e', nullptr };str2->next->next = common; // 共享后缀部分// 查找共同后缀的起始位置Node* result = search(str1, str2);if (result != nullptr) {cout << "共同后缀的起始位置: " << (char)result->value << endl;} else {cout << "没有共同后缀" << endl;}return 0;
}
代码结构分析
  1. search 函数:这是主函数,它通过双层循环在链表 firstsecond 中查找共同后缀的起始位置。

    • 外层循环:遍历链表 first 的每个节点 x
    • 内层循环:对于每个节点 x,遍历链表 second 的每个节点 y
  2. check 函数search 函数在 if(x -> value == y -> value && check(x, y)) 中调用 check 函数,用于比较链表 first 从节点 x 开始的后缀和链表 second 从节点 y 开始的后缀。

    • check 函数的时间复杂度为 (O(n)),因为它从两个节点开始逐一比较剩下的所有节点。
时间复杂度计算
  • 外层循环遍历链表 first 的每个节点,时间复杂度为 (O(m))(m 是链表 first 的长度)。
  • 内层循环遍历链表 second 的每个节点,时间复杂度为 (O(n))(n 是链表 second 的长度)。
  • check 函数的复杂度为 (O(k)),其中 kxy 之后的节点数量,最多接近 O(max(m, n))

因此,整体时间复杂度为: O ( m × n × k ) ≈ O ( n 3 ) O(m \times n \times k) \approx O(n^3) O(m×n×k)O(n3)

2. 双指针法

考虑一种更为高效的 双指针法

思路

我们先遍历两个链表,得到它们的长度差 d。然后让较长的链表先走 d 步,这样两个链表剩下的节点数相等。之后同时遍历两个链表,直到找到第一个相同的节点,即为共同后缀的起始位置。

实现步骤
  1. 计算两个链表的长度 len1len2,求得它们的长度差 d
  2. 将较长的链表向前移动 d 步。
  3. 同时遍历两个链表,直到找到第一个相同的节点。

优点:通过两次遍历(计算长度 + 查找共同节点),时间复杂度降低到 O(m + n)

C++ 实现代码

以下是使用 C++ 实现的双指针法代码:

#include "bits/stdc++.h"
using namespace std;struct Node{int value;Node* next;
}; // 计算链表长度
int getLength(Node* node) {int length = 0;while(node != nullptr) {length++;node = node -> next;}return length;
}// 查找共同后缀起始节点
Node* search(Node* n, Node* m) {int len1 = getLength(n);int len2 = getLength(m);// 长链表先走 |len1 - len2| 步while(len1 > len2) {len1--;n = n -> next;}while(len2 > len1) {len2--;m = m -> next;}// 双指针同时遍历寻找共同节点while(n != nullptr && m != nullptr) {if(n == m ) return n;n = n -> next;m = m -> next;}return nullptr;
}int main() {Node* common = new Node{'i', new Node{'n', new Node{'g', nullptr}}};Node* str1 = new Node{ 'l', nullptr };str1->next = new Node{ 'o', nullptr };str1->next->next = new Node{ 'a', nullptr };str1->next->next->next = new Node{ 'd', nullptr };str1->next->next->next->next = common;Node* str2 = new Node{ 'b', nullptr };str2->next = new Node{ 'e', nullptr };str2->next->next = common;Node* result = search(str1, str2);if (result != nullptr) {cout << "共同后缀的起始位置: " << (char)result->value << endl;} else {cout << "没有共同后缀" << endl;}return 0;
}

这段代码的核心思想是通过调整两个链表的起始位置,使得它们在同一个位置开始比较,以便找到第一个相同的节点作为共同后缀的起始点。以下是逐步的代码讲解,特别是对为什么较长的链表需要先移动几步的解释。

代码分解与讲解

#include "bits/stdc++.h"
using namespace std;struct Node{int value;Node* next;
}; 
  • 这里定义了链表节点的结构体 Node,包含一个整型数据 value 和一个指向下一个节点的指针 next
int getLength(Node* node) {int length = 0;while(node != nullptr) {length++;node = node -> next;}return length;
}
  • getLength 函数用于计算链表的长度。它遍历链表并计数,直到链表末尾。时间复杂度为 (O(n)),其中 (n) 是链表的长度。
Node* search(Node* n, Node* m) {int x = getLength(n);int y = getLength(m);
  • search 函数是主函数,用来找到两个链表的共同后缀。首先调用 getLength 获取链表 nm 的长度,分别记为 xy
为什么较长的链表要先移动?

假设链表 n 比链表 m 长。如果直接从头开始同时遍历两个链表,由于长度不相等,较长链表的指针会先到达结尾,而我们需要两个链表在“对齐的起始位置”进行比较。

因此,为了让两个链表末尾部分对齐:

  1. 让较长的链表先移动 |x - y| 步。这样移动后,两个链表的剩余部分长度相等。
  2. 从这个新位置开始,两个链表的指针将同步向后遍历,确保同时到达链表的末尾。
    while(x > y) {x--;n = n -> next;} while(y > x) {y--;m = m -> next;}
  • 在这里,较长的链表会先移动 |x - y| 步,以确保后续同步遍历时,两链表末尾部分的节点数相同。
    while(n != nullptr && m != nullptr) {if(n == m) return n;n = n -> next;m = m -> next;}return nullptr;
}
  • 现在,两个链表 nm 同时从新的位置开始遍历。
  • 如果发现 nm 指向同一个节点(即它们有相同的地址),则该节点即为第一个公共节点,返回该节点。
  • 如果遍历结束未找到公共节点,则返回 nullptr,表示没有共同后缀。

算法时间复杂度分析

  1. 计算长度

    • 函数 getLength 分别计算链表 nm 的长度,耗时为 (O(m)) 和 (O(n))。
  2. 对齐链表长度

    • 假设 str1str2 长。为了让两个链表的尾端对齐,较长的链表 str1 向前移动 |m - n| 步。无论如何,对齐过程的时间复杂度是 (O(|m - n|)),这可以简化为 (O(m + n))。
  3. 寻找共同后缀

    • 接下来,两个链表同时从对齐位置向后遍历,寻找第一个相同的节点。这部分的时间复杂度为 O ( m i n ( m , n ) ) O(min(m, n)) O(min(m,n)),但可以包含在 O ( m i n ( m , n ) ) O(min(m, n)) O(min(m,n))的上界内。

因此,整个算法的时间复杂度为 O ( m i n ( m , n ) ) O(min(m, n)) O(min(m,n)),这涵盖了所有操作的最坏情况时间复杂度。这种算法之所以更高效,是因为它只需要遍历每个链表最多两次。

结语

双指针法通过巧妙地同步遍历来提高效率,非常适合此类链表问题。在链表题目中,理解如何通过双指针控制遍历过程,可以显著提升算法的效率。希望这篇文章能够帮助大家更好地理解链表的双指针技巧。

相关文章:

【每日一题】2012考研数据结构 - 求字符串链表公共后缀

本篇文章将为大家讲解一道关于链表的经典题目——求两个链表的共同后缀节点。该问题在实际开发中同样具有很大的应用价值&#xff0c;是每一位数据结构学习者不可错过的重要题目。 问题描述 假设我们有一个带头结点的单链表来保存单词&#xff0c;每个节点包含一个字符和指向…...

数据结构和算法-贪心算法01- 认识贪心

贪心算法 什么是贪心算法 一个贪心算法总是做出当前最好的选择&#xff0c;也就是说&#xff0c;它期望通过局部最优选择从而得到全局最优的解决方案。 ​ ----《算法导论》 贪心算法(Greedy Method): 所谓贪心算法就是重复地(或贪婪地)根据一个法则挑选解的一部分。当挑选完毕…...

Bash Shell - 获取日期、时间

1. 使用date获取日期 以下代码将date的执行结果存储在today变量中。date 是获取日期和时间的命令。 选择使用 quotes()或$ #!/bin/bashtodaydate echo $todaytoday$(date) echo $today 2. 使用 Format 输出所需日期和时间 date FORMAT 2.1 "MM-DD-YY" 形式输出…...

runnable和callable区别和底层原理

确实&#xff0c;Runnable 可以直接通过 Thread 类来运行&#xff0c;而 Callable 不能直接用于创建和运行线程。Callable 和 Runnable 都是 Java 中用于定义异步任务的接口&#xff0c;但它们的用法和目的有所不同。 ### Runnable 和 Thread Runnable 是接口&#xff0c;它不返…...

Springboot 整合 Java DL4J 打造自然语言处理之语音识别系统

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/literature?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;…...

虚幻引擎5(UE5)学习教程

虚幻引擎5&#xff08;UE5&#xff09;学习教程 引言 虚幻引擎5&#xff08;Unreal Engine 5&#xff0c;简称UE5&#xff09;是Epic Games开发的一款强大的游戏引擎&#xff0c;广泛应用于游戏开发、影视制作、建筑可视化等多个领域。UE5引入了许多先进的技术&#xff0c;如…...

从0开始深度学习(26)——汇聚层/池化层

池化层通过减少特征图的尺寸来降低计算量和参数数量&#xff0c;同时增加模型的平移不变性和鲁棒性。汇聚层的主要优点之一是减轻卷积层对位置的过度敏感。 1 最大汇聚层、平均汇聚层 汇聚层和卷积核一样&#xff0c;是在输入图片上进行滑动计算&#xff0c;但是不同于卷积层的…...

兼职发薪系统:高效、便捷的劳务发薪解决方案

在快速发展的数字化时代&#xff0c;企业对于高效、便捷的薪酬发放和管理解决方案的需求日益增长。特别是对于兼职人员众多的企业&#xff0c;如何实现快速、准确的发薪&#xff0c;同时确保员工信息的安全与保密&#xff0c;成为了一个亟待解决的问题。今天&#xff0c;我们将…...

MySQL数据库单表查询习题

目录 数据内容介绍习题题目答案 数据内容介绍 数据库中有两个表 ​​​​ 内容如下&#xff1a; 习题 题目 查询出部门编号为D2019060011的所有员工所有财务总监的姓名、编号和部门编号。找出奖金高于工资的员工。找出奖金高于工资40%的员工。找出部门编号为D2019090011中所有…...

多模态PaliGemma——Google推出的基于SigLIP和Gemma的视觉语言模型

前言 本文怎么来的呢&#xff1f;其实很简单&#xff0c;源于上一篇文章《π0——用于通用机器人控制的流匹配VLA模型&#xff1a;一套框架控制7种机械臂(改造了PaliGemma和ACT的3B模型)》中的π0用到了PaliGemma 故本文便来解读下这个PaliGemma 第一部分 PaliGemma 1.1 Pal…...

电路原理:电阻桥。

电路的基础是电阻电路。电阻电路有两种基本接线方法&#xff08;串连和并连&#xff0c;二者有不同的解算与用法&#xff1a;串连分压、并连分流&#xff09;。电阻电路就是使用基本接线方法的组合方案&#xff0c;其解算方法主要内容是判断好整体布局以及各个局部的串并连关系…...

实践出真知:MVEL表达式中for循环的坑

目录标题 背景MVEL脚本(有问题的)MVEL脚本(正确的)结论分析 背景 需要从一个URL的拼接参数中解析出id的值并输出 比如&#xff1a; 存在URLhttps://xxxxxxxxxx?id999999&type123&name345 然后需要输出id999999 MVEL脚本(有问题的) 入参&#xff1a;parseThisUrlhttp…...

Flutter运行App时出现“Running Gradle task ‘assembleDebug“问题解决

在参考了众多解决办法中最有用并且最快的方法 Gradle Distributions 在这个地方下载对应你这个文件中的gradle版本 然后将 最后一行本来不是这样的,我们把下载好的zip包保存到本地,然后用这个代替网址,最后成功运行...

基于SSM(Spring + Spring MVC + MyBatis)框架的咖啡馆管理系统

基于SSM&#xff08;Spring Spring MVC MyBatis&#xff09;框架的咖啡馆管理系统是一个综合性的Web应用程序&#xff0c;用于管理和优化咖啡馆的运营。下面我将提供一个详细的案例程序概述&#xff0c;包括主要的功能模块和技术栈介绍。 项目概述 功能需求 用户管理&…...

【SpringBoot】18 上传文件到数据库(Thymeleaf + MySQL)

Git仓库 https://gitee.com/Lin_DH/system 介绍 使用 Thymeleaf 写的页面&#xff0c;将&#xff08;txt、jpg、png&#xff09;格式文件上传到 MySQL 数据库中。 依赖 pom.xml <!-- https://mvnrepository.com/artifact/com.mysql/mysql-connector-j --><depende…...

计算机体系结构之系统吞吐量(三)

前面章节《计算机体系结构之多级缓存、缓存miss及缓存hit&#xff08;二&#xff09;》讲了关于系统多级缓存的相关内容&#xff0c;其中提及了系统吞吐量一词。在此章将对其进行讲解。 系统吞吐量是计算机体系结构的一个重要指标&#xff0c;其衡量的是系统在单位时间内处理工…...

高级 HarmonyOS主题课—— 帮助快速构建各种文本识别应用的课后习题

天地不仁&#xff0c;以万物为刍狗&#xff1b; 圣人不仁&#xff0c;以百姓为刍狗。 天地之间&#xff0c;其犹橐龠乎&#xff1f; 虚而不屈&#xff0c;动而俞出。 多闻数穷&#xff0c;不若守于中。 本文内容主要来自 <HarmonyOS主题课>帮助快速构建各种文本识别应用 …...

windows C#-异常和异常处理概述

C# 语言的异常处理功能有助于处理在程序运行期间发生的任何意外或异常情况。 异常处理功能使用 try、catch 和 finally 关键字来尝试执行可能失败的操作、在你确定合理的情况下处理故障&#xff0c;以及在事后清除资源。 公共语言运行时 (CLR)、.NET/第三方库或应用程序代码都可…...

每日一题——第一百二十四题

题目&#xff1a;进制转换 #pragma once#include<stdio.h> #include<ctype.h> #include<string.h>/// <summary> /// //将字符串表示的任意进制数转为十进制 /// </summary> /// <param name"str">字符串</param> /// &l…...

在 CentOS 7 上设置 OpenResty 开机启动

在 CentOS 7 上设置 OpenResty 开机启动&#xff0c;可以按照以下步骤进行操作&#xff1a; 创建 Systemd 服务文件&#xff1a; 首先&#xff0c;您需要为 OpenResty 创建一个 Systemd 服务文件。使用文本编辑器&#xff08;如 vi 或 nano&#xff09;创建一个新的服务文件。 …...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...