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

每日一题(LeetCode)----链表--链表最大孪生和

每日一题(LeetCode)----链表–链表最大孪生和

1.题目(2130. 链表最大孪生和)

  • 在一个大小为 nn偶数 的链表中,对于 0 <= i <= (n / 2) - 1i ,第 i 个节点(下标从 0 开始)的孪生节点为第 (n-1-i) 个节点 。

    • 比方说,n = 4 那么节点 0 是节点 3 的孪生节点,节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。

    孪生和 定义为一个节点和它孪生节点两者值之和。

    给你一个长度为偶数的链表的头节点 head ,请你返回链表的 最大孪生和

    示例 1:

    img

    输入:head = [5,4,2,1]
    输出:6
    解释:
    节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。
    链表中没有其他孪生节点。
    所以,链表的最大孪生和是 6 。
    

    示例 2:

    img

    输入:head = [4,2,2,3]
    输出:7
    解释:
    链表中的孪生节点为:
    - 节点 0 是节点 3 的孪生节点,孪生和为 4 + 3 = 7 。
    - 节点 1 是节点 2 的孪生节点,孪生和为 2 + 2 = 4 。
    所以,最大孪生和为 max(7, 4) = 7 。
    

    示例 3:

    img

    输入:head = [1,100000]
    输出:100001
    解释:
    链表中只有一对孪生节点,孪生和为 1 + 100000 = 100001 。
    

    提示:

    • 链表的节点数目是 [2, 105] 中的 偶数
    • 1 <= Node.val <= 105

2.解题思路

思路一

将链表的后一半进行反转,然后将链表的前一半和后一半进行相加,通过比较得到结果
1.找到链表的后一半的起始节点

我们先计算出整个链表的长度,然后用一个指针指向链表表头,向后走整个链表的一半长度,得到链表后一半的表头

2.进行反转

通过头,拿,断这三个指针实现反转

3.定义一个存结果的变量,将反转后的后一半链表与原链表的前一半进行相加(这里思路一和思路二实现方式不一样,但是都差不多),然后每求出一个值,就和存结果的变量进行比较,如果大于,就把存结果的变量进行更新,如果不大于,就不进行更新

思路二:思路二和思路一一样就是实现的方法不同

1.找到链表的后一半的起始节点

我们使用快慢指针找出后一半部分的起始节点。我们用慢指针和快指针同时指向 头节点,然后,我们每次将慢指针向后移动一个节点,同时快指针向后移动两个节点。当 快指针指向空结点时,慢指针就刚好指向链表了后一半部分的首节点

2.进行反转

通过头,拿,断这三个指针实现反转

3.定义一个存结果的变量,将反转后的后一半链表与原链表的前一半进行相加(这里思路一和思路二实现方式不一样,但是都差不多),然后每求出一个值,就和存结果的变量进行比较,如果大于,就把存结果的变量进行更新,如果不大于,就不进行更新

3.写出代码

思路一的代码

class Solution {
public:int pairSum(ListNode* head) {int length1=0;ListNode* Temp=head;while(Temp){length1++;Temp=Temp->next;}int length2=length1/2;int t=length2;Temp=head;while(t--){Temp=Temp->next;}ListNode* head2=NULL;ListNode* na=Temp;ListNode* duan=Temp->next;while(duan){na->next=head2;head2=na;na=duan;duan=duan->next;}na->next=head2;head2=na;int res=-1;for(int i=0;i<length2;i++){res=max(head->val+head2->val,res);head=head->next;head2=head2->next;}return res;}
};

思路二的代码

class Solution {
public:int pairSum(ListNode* head) {ListNode* fast=head;ListNode* slow=head;while(fast){slow=slow->next;fast=fast->next->next;}ListNode* head2=NULL;ListNode* na=slow;ListNode* duan=slow->next;while(duan){na->next=head2;head2=na;na=duan;duan=duan->next;}na->next=head2;head2=na;int res=-1;while(head2){res=max(head->val+head2->val,res);head2=head2->next;head=head->next;}return res;}
};

相关文章:

每日一题(LeetCode)----链表--链表最大孪生和

每日一题(LeetCode)----链表–链表最大孪生和 1.题目&#xff08;2130. 链表最大孪生和&#xff09; 在一个大小为 n 且 n 为 偶数 的链表中&#xff0c;对于 0 < i < (n / 2) - 1 的 i &#xff0c;第 i 个节点&#xff08;下标从 0 开始&#xff09;的孪生节点为第 (n…...

腾讯云轻量服务器通过Docker搭建外网可访问连接的redis5.x集群

原创/朱季谦 最近买了一台4核16的腾讯云轻量应用服务器,花了我快四百的大洋&#xff0c;打算搭建一堆docker组件集群&#xff0c;最先开始是通过docker搭建redis集群&#xff0c;计划使用三个端口&#xff0c;分别是7001,7002,7003。 腾讯云服务器有防火墙限制&#xff0c;故…...

C++学习之路(十一)C++ 用Qt5实现一个工具箱(增加一个进制转换器功能)- 示例代码拆分讲解

上篇文章&#xff0c;我们用 Qt5 实现了在小工具箱中添加了《时间戳转换功能》功能。为了继续丰富我们的工具箱&#xff0c;今天我们就再增加一个平时经常用到的功能吧&#xff0c;就是「 进制转换 」功能。下面我们就来看看如何来规划开发一个这样的小功能并且添加到我们的工具…...

C语言每日一题(40)栈实现队列

力扣232 用栈实现队列 题目描述 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作&#xff08;push、pop、peek、empty&#xff09;&#xff1a; 实现 MyQueue 类&#xff1a; void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并…...

Vue.js 的生命周期

Vue.js 的生命周期钩子函数是一组在 Vue 实例生命周期中执行的函数&#xff0c;它们允许你在特定阶段执行自定义逻辑。以下是 Vue.js 的生命周期钩子函数以及它们在生命周期中的执行时机&#xff1a; 1、beforeCreate: 在实例初始化之后&#xff0c;数据观测 (data observer)…...

SeaTunnel引擎下的SQL Server CDC解决方案:构建高效数据管道

在快速发展的数据驱动时代&#xff0c;实时数据处理已经成为企业决策和运营的关键因素。特别是在处理来自各种数据源的信息时&#xff0c;如何确保数据的及时、准确和高效同步变得尤为重要。本文着重介绍了如何利用 SqlServer CDC 源连接器在 SeaTunnel 框架下实现 SQL Server …...

【攻防世界-misc】Encode

1.下载解压文件&#xff0c;打开这个内容有些疑似ROT13加密&#xff0c;利用在线工具解密&#xff1a;ROT13解码计算器 - 计算专家 得到了解密后的值 得到解码结果后&#xff0c;看到是由数字和字母组成&#xff0c;再根据题目描述为套娃&#xff0c;猜测为base编码&#xff08…...

visual c++ 2019 redistributable package

直接安装下面包只有24M Microsoft Visual C Redistributable 2019 x86: https://aka.ms/vs/16/release/VC_redist.x86.exe x64: https://aka.ms/vs/16/release/VC_redist.x64.exe ———————————————— 版权声明&#xff1a;本文为CSDN博主「kpacnB_Z」的原创文章…...

WPF中DataGrid解析

效果如图&#xff1a; 代码如下&#xff1a; <DataGrid Grid.Row"1" x:Name"dataGrid" ItemsSource"{Binding DataList}" AutoGenerateColumns"False"SelectedItem"{Binding SelectedItem,UpdateSourceTriggerPropertyChange…...

在数据库中进行表内容的修改(MYSQL)

根据表中内容&#xff0c;用命令语句创建数据库&#xff0c;表格&#xff0c;以及插入&#xff0c;修改&#xff0c;删除表格中的内容。 创建数据库&#xff1a;zrzy mysql> create database zrzy; 引用zrzy数据库&#xff1a; mysql> use zrzy; 创建student_info表&…...

Android中的多进程

在Android中也可以像pc一样开启多进程&#xff0c;这在android的编程中通常是比较少见的&#xff0c;以为在一个app基本上都是单进程工作就已经足够了&#xff0c;有一些特殊的场景&#xff0c;我们需要用多进程来做一些额外的工作&#xff0c;比如下载工作等。 在Android的An…...

Apache2.4 AliasMatch导致301重定向问题?

环境&#xff1a;ubuntu18.04-desktop apache2版本&#xff1a; rootubuntu:/etc/apache2# apache2ctl -v Server version: Apache/2.4.29 (Ubuntu) Server built: 2023-03-08T17:34:33apache配置&#xff1a; DocumentRoot /var/www/html # Alias就没事 # Alias "/my…...

广州华锐视点:基于VR元宇宙技术开展法律法规常识在线教学,打破地域和时间限制

随着科技的飞速发展&#xff0c;人类社会正逐渐迈向一个全新的时代——元宇宙。元宇宙是一个虚拟的、数字化的世界&#xff0c;它将现实世界与数字世界紧密相连&#xff0c;为人们提供了一个全新的交流、学习和娱乐平台。在这个充满无限可能的元宇宙中&#xff0c;法律知识同样…...

Maven——Maven使用基础

1、安装目录分析 1.1、环境变量MAVEN_HOME 环境变量指向Maven的安装目录&#xff0c;如下图所示&#xff1a; 下面看一下该目录的结构和内容&#xff1a; bin&#xff1a;该目录包含了mvn运行的脚本&#xff0c;这些脚本用来配置Java命令&#xff0c;准备好classpath和相关…...

U4_2:图论之MST/Prim/Kruskal

文章目录 一、最小生成树-MST生成MST策略一些定义 思路彩蛋 二、普里姆算法&#xff08;Prim算法&#xff09;思路算法流程数据存储分析 伪代码时间复杂度分析 三、克鲁斯卡尔算法&#xff08;Kruskal算法&#xff09;分析算法流程并查集-Find-set 伪代码时间复杂度分析 一、最…...

springboot 注解@JsonInclude

修饰 实体属性or实体类 //枚举值&#xff1a;ALWAYS,NON_NULL,NON_ABSENT,NON_EMPTY,NON_DEFAULT,CUSTOM,USE_DEFAULTS JsonInclude(Include.NON_EMPTY)//将该标记放在属性上&#xff0c;如果该属性为NULL则不参与序列化 //如果放在类上边,那对这个类的全部属性起作用 Inclu…...

Python 中文完整教程目录

Python 教程 Python 是一门易于学习、功能强大的编程语言。它提供了高效的高级数据结构&#xff0c;还能简单有效地面向对象编程。Python 优雅的语法和动态类型以及解释型语言的本质&#xff0c;使它成为多数平台上写脚本和快速开发应用的理想语言。 Python 官网&#xff08;…...

C/C++---------------LeetCode第35. 搜索插入位置

插入的位置 题目及要求二分查找在main内使用 题目及要求 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: …...

网络安全--基于Kali的网络扫描基础技术

文章目录 1. 标准ICMP扫描1.1使用Ping命令1.1.1格式1.1.2实战 1.2使用Nmap工具1.2.1格式1.2.2实战1.2.2.1主机在线1.2.2.2主机不在线 1.3使用Fping命令1.3.1格式1.3.2实战 2. 时间戳查询扫描2.1格式2.2实战 3. 地址掩码查询扫描3.1格式3.2实战 2. TCP扫描2.1TCP工作机制2.2TCP …...

C语言——求π的近似值

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h> #include<math.h> int main() {int s;double n,t,pi;t1;pi0;n1.0;s1;while (fabs(t)>1e-6){pipit; nn2; s-s; ts/n;}pipi*4;printf("pi%lf\n",pi);return 0; }这里是求小数点后6位——1e-6&#…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...