回文链表(leetcode)
我自己第一个写的代码:
bool isPalindrome(struct ListNode* head){struct ListNode* tail = NULL;struct ListNode* pos = NULL;if( head->next == NULL){return true;}while( 1 ){if( head->next == NULL || (head->next->next == NULL && head->val==head->next->val) ){return true;}for( tail = head ; tail->next->next != NULL ; tail = tail->next);if( head->val != tail->next->val)return false;if( head->next == NULL || head->next->next == NULL ){return true;}pos = head;head = head->next;tail->next = NULL;pos->next = NULL;}
}
1 2 3 2 1
比较第一个数和最后一个数,注意不要把指针放在最后,因为要将最后的链点删除,则考虑倒数第二个链点,并且if条件判断要放在两处,为了防止对空指针解引用
但此时时间复杂度过高O(n) 循环内的代码均要执行一遍,导致超时
算法:首先将链表分成两节,将后一节的链表翻转,在一一比较
1 2 3 3 2 1
1 2 3 || 3 2 1
1 2 3 || 1 2 3
struct ListNode* rollback( struct ListNode* head )
{
struct ListNode* pos = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* p1 = head;
struct ListNode* p2 = head->next;
while( p2 != NULL )
{
p1->next = p2->next;
p2->next = pos->next;
pos->next = p2;
p2 = p1->next;
}
return pos->next;
}
struct ListNode* get_listnode(struct ListNode* head)
{
struct ListNode* fast = head->next;
struct ListNode* slow = head;
struct ListNode* arr = NULL;
while( fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
arr = slow->next;
slow->next = NULL;
return arr;
}
bool isPalindrome(struct ListNode* head){
struct ListNode* mid_listnode = NULL;
struct ListNode* tail = NULL;
if( head == NULL )
{
return true;
}
mid_listnode = get_listnode(head);
tail = rollback(mid_listnode);
while( tail != NULL )
{
if( head->val != tail->val )
{
return false;
}
tail = tail->next;
head = head->next;
} 这里的比较执行n/2次
return true;
}
时间复杂度分析:rollback函数内的语句执行n/2次
get_listnode函数内的语句执行n/2次
T = O(n)
空间复杂度:O(1)
相关文章:
回文链表(leetcode)
我自己第一个写的代码: bool isPalindrome(struct ListNode* head){struct ListNode* tail NULL;struct ListNode* pos NULL;if( head->next NULL){return true;}while( 1 ){if( head->next NULL || (head->next->next NULL && head->…...
大语言模型(LLM)技术名词表(一)
LLMs on a Phone:指在手机设备上运行的大型语言模型。 Scalable Personal AI:指用户可以在个人设备上对AI模型进行微调的技术。 Responsible Release:发布AI模型时考虑社会、法律和伦理影响的做法。 Multimodality:AI模型能处理…...
C++ 快速排序快速选择
目录 1、75. 颜色分类 2、912. 排序数组 3、 215. 数组中的第K个最大元素 4、LCR 159. 库存管理 III 1、75. 颜色分类 思路:利用快速排序思路,使用三指针分块进行优化。 [0,left]——小于key[left1,right-1]——等于key[right,nums.size()]——大于k…...
雅马哈伺服器TS-S系列说明具体详情内容可参看PDF目录内容
雅马哈伺服器TS-S系列说明具体详情内容可参看PDF目录内容...
SpringBoot底层原理
SpringBoot底层原理 一 配置优先级 1.配置方式 Springboot中支持三种配置方式,分别为: application.propertiesapplication.ymlapplication.yaml 2.配置优先级 当存在多份配置文件时,配置文件会按照它们的优先级生效。 优先级从高到底…...
【golang】25、图片操作
用 “github.com/fogleman/gg” 可以画线, 框 用 “github.com/disintegration/imaging” 可以变换颜色 一、渲染 1.1 框和字 import "github.com/fogleman/gg"func DrawRectangles(inPath string, cRects []ColorTextRect, fnImgNameChange FnImgNameChange) (st…...
kswapd0挖矿病毒攻击记录
文章目录 一、起因与病毒分析1、起因2、阿里云告警2.1 恶意脚本代码执行12.2 恶意脚本代码执行22.3恶意脚本代码执行32.4 恶意脚本代码执行4 3、病毒简单分析3.1 病毒的初始化3.2 病毒本体执行 4、总结 二、ubuntu自救指南1、病毒清理2、如何防御 一、起因与病毒分析 1、起因 …...
如何使用 takeUntil RxJS 操作符来声明性地管理订阅
简介 Angular 处理取消订阅可观察对象的操作,比如从 HTTP 服务返回的可观察对象或者使用 async 管道时。然而,对于其他情况,管理所有订阅并确保取消长期存在的订阅可能会变得困难。而且,取消大部分订阅的策略也会带来自己的问题。…...
在Centos中用Docker部署oracle-12c
一、介绍 Oracle 12c是Oracle 11g的后续版本。12c代表云计算(Cloud Computing),这是Oracle在该版本中强调的一个关键概念。它具有多租户架构、数据库内存、安全增强、大数据管理和自动化管理等功能。它被广泛应用于企业级应用程序和大型数据…...
JS进阶——高级技巧
版权声明 本文章来源于B站上的某马课程,由本人整理,仅供学习交流使用。如涉及侵权问题,请立即与本人联系,本人将积极配合删除相关内容。感谢理解和支持,本人致力于维护原创作品的权益,共同营造一个尊重知识…...
TG-ADMIN 权限管理系统
项目简介 该项目是一款基于 SpringBoot + Vue2 + Jwt + ElementUi的 RBAC模型管理系统。 主要以自定义拦截器和jwt结合进行权限验证 通过自定义指令实现按钮级别权限,使用经典的RBAC模型 什么是RBAC? 1、RBAC模型概述 RBAC模型(Role-Based Access Control:基于角色的…...
十五届蓝桥杯第三期模拟赛题单(C++、java、Python)
备战2024年蓝桥杯 省赛第三期模拟赛题单 备战Python大学A组 第一题 【问题描述】 请问 2023 有多少个约数?即有多少个正整数,使得 2023 是这个正整数的整数倍。 【问题描述】 这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果…...
嵌入式驱动学习第一周——git的使用
前言 本文主要介绍git的使用,包括介绍git,gitee,以及使用gitee创建仓库并托管代码 嵌入式驱动学习专栏将详细记录博主学习驱动的详细过程,未来预计四个月将高强度更新本专栏,喜欢的可以关注本博主并订阅本专栏…...
界面控件DevExpress .NET MAUI v23.2新版亮点 - 拥有全新的彩色主题
DevExpress拥有.NET开发需要的所有平台控件,包含600多个UI控件、报表平台、DevExpress Dashboard eXpressApp 框架、适用于 Visual Studio的CodeRush等一系列辅助工具。屡获大奖的软件开发平台DevExpress 今年第一个重要版本v23.1正式发布,该版本拥有众多…...
大语言模型LLM Pro+中Pro+(Prompting)的意义
—— Pro ,即Prompting,构造提示 1.LLM Pro中Pro(Prompting)的意义 Prompting不仅是大语言模型交互和调用的一种高效手段,而且已成为推动模型泛化能力和应用灵活性的关键技术路径,它不仅极大地拓展了模型功…...
React 中,children 属性
在 React 中,children 属性是一个特殊的属性,它允许你将组件作为其他组件的子元素传递。这意味着你可以在组件内部嵌套任何类型的子组件或元素,并且在父组件中通过 props.children 访问它们。这为组件的复用和组合提供了极大的灵活性。 以下…...
多行业万能预约门店小程序源码系统 支持多门店预约小程序 带完整的安装代码包以及搭建教程
随着消费者对于服务体验要求的不断提升,门店预约系统成为了许多行业提升服务质量、提高运营效率的重要工具。然而,市面上的预约系统往往功能单一,无法满足多行业、多场景的个性化需求。下面,小编集合了多年的行业经验和技术积累&a…...
Node.js 中 fs 模块文件操作的应用教程
Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行环境,它可以让 JavaScript 代码在服务器端运行。在 Node.js 中,fs 模块是用来处理文件系统操作的模块。通过 fs 模块,我们可以进行文件的读取、写入、删除等操作。本教程将介绍如何在 No…...
一些常用到的git命令
git stash -a //缓存所有文件 git checkout -b dev origin/dev //切换到dev分支上,接着跟远程的origin地址上的dev分支关联起来 //推送本地分支到远程仓库 git push origin localbranchname:remotebrancname git revert onefile //https://www.freecodecamp.org/news/git-re…...
spring boot3解决跨域的几种方式
⛰️个人主页: 蒾酒 🔥系列专栏:《spring boot实战》 🌊山高路远,行路漫漫,终有归途。 目录 1.前言 2.何为跨域 3.跨域问题出现特征 4.方式一:使用 CrossOrigin 注解 5.方式二:自定义…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
