设计一个算法,找出由str1和str2所指向两个链表共同后缀的起始位置
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,’loading’和’being’的存储映像如下图所示。

设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为 datanext ,请设计一个时间上尽可能高效的算法,找出由str1和str2所指向两个链表共同后缀的起始位置(如图中字符i所在的结点位置p)。
方法一:暴力
思想:外层循环遍历str1,内存循环遍历str2,遍历过程中比较是否相等。
代码:
typedf char ElemType;
typedf struct LNode {ElemType data;struct LNode *next;
}LNode,*LinkList;
LinkList getsameNode(LinkList L1,LinkList L2){L1=L1->next;while(L1!=NULL){//外层循环L1 LNode *p=L2->next;while(p!=NULL){//内存循环L2 if(L1==p){return L1;}p=p->next;}L1=L1->next;}//没找到 return NULL;
}
时间复杂度O(len1+len2);空间复杂度O(1)
方法二:让较长的链表先移动,直到两个链表长度一样时,进行同时移动。
思想:分别求两个链表长度。然后对较长的那个链表先进行遍历,直到两个链表相同时,进行同时遍历,直到找到公共结点为止。
代码:
int length(LinkList L){//计算链表长度 int len=0;L=L->next;while(L!=NULL){len++;L=L->next;}return len;
}
LinkList getsameNode(LinkList L1,LinkList L2){//计算链表长度int len1=length(L1);int len2=length(L2);for(p=L1;len1>len2;len1--){//链表1更长时 p=p->next;}for(q=L2;len2>len1;len2--){//链表2更长时 q=q->next;}while(p->next!=NULL && p->next!=q->next){//此时两个链表一样长,进行差查第一个公共节点 p=p->next;q=q->next;}return p->next;//返回查找到的结点
}
时间复杂度O(len1+len2),空间复杂度O(1)
相关文章:
设计一个算法,找出由str1和str2所指向两个链表共同后缀的起始位置
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,’loading’和’being’的存储映像如下图所示。 设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为 data…...
Python中如何判断一个变量是否为None
在Python中,判断一个变量是否为None是一个常见的需求,特别是在处理可选值、默认值或者是在函数返回结果可能不存在时。虽然这个操作本身相对简单,但围绕它的讨论可以扩展到Python的哲学、类型系统、以及如何在不同场景下优雅地处理None值。 …...
表观遗传系列1:DNA 甲基化以及组蛋白修饰
1. 表观遗传 表观遗传信息很多为化学修饰,包括 DNA 甲基化以及组蛋白修饰,即DNA或蛋白可以通过化学修饰添加附加信息。 DNA位于染色质(可视为微环境)中,并不是裸露的,因此DNA分子研究需要跟所处环境结合起…...
Android 跳转至各大应用商店应用详情页
测试通过机型品牌: 华为、小米、红米、OPPO、一加、Realme、VIVO、IQOO、荣耀、魅族、三星 import android.content.ActivityNotFoundException; import android.content.Context; import android.content.Intent; import android.content.pm.PackageInfo; import …...
Pywinauto鼠标操作指南
Pywinauto是一个强大的Python库,用于自动化Windows桌面应用程序的测试。它提供了一系列工具和API来模拟用户输入,包括键盘、鼠标事件,以及与各种窗口控件交互的能力。本文将详细介绍如何使用Pywinauto来执行鼠标操作,并通过一些示…...
VRAY云渲染动画怎么都是图片?
动画实际上是由一系列连续的静态图像(帧)组成的,当这些帧快速连续播放时,就形成了动画效果。每一帧都是一个单独的图片,需要单独渲染。 云渲染农场的工作方式: 1、用户将3D场景文件和动画设置上传到云渲染…...
共享内存(C语言)
目录 一、引言 二、共享内存概述 1.什么是共享内存 2.共享内存的优势 三、共享内存的实现 1.创建共享内存 2.关联共享内存 3.访问共享内存 4.解除共享内存关联 5.删除共享内存 四、共享内存应用实例 五、总结 本文将深入探讨C语言中的共享内存技术,介绍其原理、…...
《JavaEE进阶》----16.<Mybatis简介、操作步骤、相关配置>
本篇博客讲记录: 1.回顾MySQL的JDBC操作 2..Mybatis简介、Mybatis操作数据库的步骤 3.Mybatis 相关日志的配置(日志的配置、驼峰自动转换的配置) 前言 之前学习应用分层时我们知道Web应用程序一般分为三层,Controller、Service、D…...
HuggingFists算子能力扩展-PythonScript
HuggingFists作为一个低代码平台,很多朋友会关心如何扩展平台算子能力。扩展平台尚不支持的算子功能。本文就介绍一种通过脚本算子扩展算子能力的解决方案。 HuggingFists支持Python和Javascript两种脚语言的算子。两种语言的使用方式相同,使用者可以任选…...
WInform记录的添加和显示
1、程序 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Windows.Forms;namespace ComboBoxApp {public part…...
★ C++基础篇 ★ string类的实现
Ciallo~(∠・ω< )⌒☆ ~ 今天,我将继续和大家一起学习C基础篇第五章下篇----string类的模拟实现 ~ 上篇:★ C基础篇 ★ string类-CSDN博客 C基础篇专栏:★ C基础篇 ★_椎名澄嵐的博客-CSDN博客 目录 一 基础结构 二 迭代器 …...
rman compress
级别 初始 备完 耗时 low 1804 3572 0:10 High 1812 3176 2:00 MEDIUM 1820 3288 0:13 BASIC 1828 3444 0:56 ---不如MEDIUM,时间还长 NO COMPRESS 1820 5924 0:5 R…...
创建一个Oracle版本的JDK的Docker镜像
背景说明 OpenJDK 和Oracle JDK 一般情况下我们选择OpenJDK,两者针对大部分场景都可以满足,有些地方例如反射技术获得某些包路径下的类对象等,有时候选择OpenJDK会导致空指针异常。 两者在底层实现方面有部分区别。 创建镜像 这里是Linux…...
Harmony OS DevEco Studio 如何导入第三方库(以lottie为例)?-- HarmonyOS自学2
在做鸿蒙开发时,离不开第三方库的引入 一.有哪些支持的Harmony OS的 第三方库? 第三方库下载地址: 1 tpc_resource: 三方组件资源汇总 2 OpenHarmony三方库中心仓 二. 如何加入到DevEco Studio工程 以 lottie为例 OpenHarmony-TPC/lot…...
JAVA数据导出为Excel
目录 一、导入依赖 二、使用的相关类 1、XSSFWorkbook 构造方法 创建表 操作表 保存表 样式和格式 日期处理 密码保护 其他 2、XSSFSheet 获取属性和信息 行操作 列操作 表的属性 合并单元格 保护表 页眉和页脚 注释 其它 3、XSSFRow 获取属性和信息 单…...
【数据结构与算法 | 灵神题单 | 快慢指针(链表)篇】力扣876, 2095, 234
1. 力扣876:链表的中间节点 1.1 题目: 给你单链表的头结点 head ,请你找出并返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 示例 1: 输入:head [1,2,3,4,5] 输出:[3,4,…...
第十五届蓝桥杯图形化省赛题目及解析
第十五届蓝桥杯图形化省赛题目及解析 一. 单选题 1. 运行以下程序,角色会说( )? A、29 B、31 C、33 D、35 正确答案:C 答案解析: 重复执行直到m>n不成立,即重复执行直到m<n。所有当m小于或者 等于n时&…...
linux下NTP服务器实战(chrony软件)
linux下NTP服务器实战(chrony软件) 记录linux下NTP服务器搭建及相关管理操作,使用chrony软件包安装部署。相比ntp服务,Chrony服务适用于更高精度、更高稳定性、自动化等场景。 1. 安装 chrony 在大多数Linux发行版上,chrony可以通过包管理…...
Java设计模式之命令模式介绍和案例示范
一、命令模式简介 命令模式(Command Pattern)是一种行为型设计模式,它将请求封装为一个对象,从而使你可以用不同的请求对客户端进行参数化、对请求排队或记录日志,以及支持可撤销的操作。命令模式的核心思想是将发出请…...
Leetcode面试经典150题-74.搜索二维矩阵
解法都在代码里,不懂就留言或者私信 二分查找,比较简单 class Solution {/**解题思路:每一行有序、每一列也有序,只是整体不是严格有序的,那我们需要找一个点,只能往两个方向走,往一个方向走是…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程
鸿蒙电脑版操作系统来了,很多小伙伴想体验鸿蒙电脑版操作系统,可惜,鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机,来体验大家心心念念的鸿蒙系统啦!注意:虚拟…...
WEB3全栈开发——面试专业技能点P4数据库
一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库,基于 mysql 库改进而来,具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点: 支持 Promise / async-await…...
