设计一个算法,找出由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 {/**解题思路:每一行有序、每一列也有序,只是整体不是严格有序的,那我们需要找一个点,只能往两个方向走,往一个方向走是…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
