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

设计一个算法,找出由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&#xff5e;(∠・ω< )⌒☆ ~ 今天&#xff0c;我将继续和大家一起学习C基础篇第五章下篇----string类的模拟实现 ~ 上篇&#xff1a;★ C基础篇 ★ string类-CSDN博客 C基础篇专栏&#xff1a;★ 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&#xff0c;时间还长 NO COMPRESS 1820 5924 0:5 R…...

创建一个Oracle版本的JDK的Docker镜像

背景说明 OpenJDK 和Oracle JDK 一般情况下我们选择OpenJDK&#xff0c;两者针对大部分场景都可以满足&#xff0c;有些地方例如反射技术获得某些包路径下的类对象等&#xff0c;有时候选择OpenJDK会导致空指针异常。 两者在底层实现方面有部分区别。 创建镜像 这里是Linux…...

Harmony OS DevEco Studio 如何导入第三方库(以lottie为例)?-- HarmonyOS自学2

在做鸿蒙开发时&#xff0c;离不开第三方库的引入 一.有哪些支持的Harmony OS的 第三方库&#xff1f; 第三方库下载地址&#xff1a; 1 tpc_resource: 三方组件资源汇总 2 OpenHarmony三方库中心仓 二. 如何加入到DevEco Studio工程 以 lottie为例 OpenHarmony-TPC/lot…...

JAVA数据导出为Excel

目录 一、导入依赖 二、使用的相关类 1、XSSFWorkbook 构造方法 创建表 操作表 保存表 样式和格式 日期处理 密码保护 其他 2、XSSFSheet 获取属性和信息 行操作 列操作 表的属性 合并单元格 保护表 页眉和页脚 注释 其它 3、XSSFRow 获取属性和信息 单…...

【数据结构与算法 | 灵神题单 | 快慢指针(链表)篇】力扣876, 2095, 234

1. 力扣876&#xff1a;链表的中间节点 1.1 题目&#xff1a; 给你单链表的头结点 head &#xff0c;请你找出并返回链表的中间结点。 如果有两个中间结点&#xff0c;则返回第二个中间结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[3,4,…...

第十五届蓝桥杯图形化省赛题目及解析

第十五届蓝桥杯图形化省赛题目及解析 一. 单选题 1. 运行以下程序&#xff0c;角色会说( )? A、29 B、31 C、33 D、35 正确答案&#xff1a;C 答案解析&#xff1a; 重复执行直到m>n不成立&#xff0c;即重复执行直到m<n。所有当m小于或者 等于n时&…...

linux下NTP服务器实战(chrony软件)

linux下NTP服务器实战(chrony软件) 记录linux下NTP服务器搭建及相关管理操作&#xff0c;使用chrony软件包安装部署。相比ntp服务&#xff0c;Chrony服务适用于更高精度、更高稳定性、自动化等场景。 1. 安装 chrony 在大多数Linux发行版上&#xff0c;chrony可以通过包管理…...

Java设计模式之命令模式介绍和案例示范

一、命令模式简介 命令模式&#xff08;Command Pattern&#xff09;是一种行为型设计模式&#xff0c;它将请求封装为一个对象&#xff0c;从而使你可以用不同的请求对客户端进行参数化、对请求排队或记录日志&#xff0c;以及支持可撤销的操作。命令模式的核心思想是将发出请…...

Leetcode面试经典150题-74.搜索二维矩阵

解法都在代码里&#xff0c;不懂就留言或者私信 二分查找&#xff0c;比较简单 class Solution {/**解题思路&#xff1a;每一行有序、每一列也有序&#xff0c;只是整体不是严格有序的&#xff0c;那我们需要找一个点&#xff0c;只能往两个方向走&#xff0c;往一个方向走是…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

13.10 LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析

LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析 LanguageMentor 对话式训练系统架构与实现 关键词:多轮对话系统设计、场景化提示工程、情感识别优化、LangGraph 状态管理、Ollama 私有化部署 1. 对话训练系统技术架构 采用四层架构实现高扩展性的对话训练…...

WEB3全栈开发——面试专业技能点P8DevOps / 区块链部署

一、Hardhat / Foundry 进行合约部署 概念介绍 Hardhat 和 Foundry 都是以太坊智能合约开发的工具套件&#xff0c;支持合约的编译、测试和部署。 它们允许开发者在本地或测试网络快速开发智能合约&#xff0c;并部署到链上&#xff08;测试网或主网&#xff09;。 部署过程…...

DriveGPT4: Interpretable End-to-end Autonomous Driving via Large Language Model

一、研究背景与创新点 (一)现有方法的局限性 当前智驾系统面临两大核心挑战:一是长尾问题,即系统在遇到新场景时可能失效,例如突发交通状况或非常规道路环境;二是可解释性问题,传统方法无法解释智驾系统的决策过程,用户难以理解车辆行为的依据。传统语言模型(如 BERT…...

Go 并发编程基础:select 多路复用

select 是 Go 并发编程中非常强大的语法结构&#xff0c;它允许程序同时等待多个通道操作的完成&#xff0c;从而实现多路复用机制&#xff0c;是协程调度、超时控制、通道竞争等场景的核心工具。 一、什么是 select select 类似于 switch 语句&#xff0c;但它用于监听多个通…...