设计一个算法,找出由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 {/**解题思路:每一行有序、每一列也有序,只是整体不是严格有序的,那我们需要找一个点,只能往两个方向走,往一个方向走是…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
