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

镇海区建设工程安监站网站/sem竞价培训班

镇海区建设工程安监站网站,sem竞价培训班,深圳 b2c 网站建设,石家庄企业商城版网站建设文章目录前言分割链表回文链表写在最后前言 本章的OJ练习相对前面的难度加大了&#xff0c;但是换汤不换药&#xff0c;还是围绕单链表的性质来出题的。我相信&#xff0c;能够过了前面的OJ练习&#xff0c;本章的OJ也是轻轻松松。 对于OJ练习(3)&#xff1a;-> 传送门 <…

文章目录

  • 前言
  • 分割链表
  • 回文链表
  • 写在最后

前言

  • 本章的OJ练习相对前面的难度加大了,但是换汤不换药,还是围绕单链表的性质来出题的。我相信,能够过了前面的OJ练习,本章的OJ也是轻轻松松。

  • 对于OJ练习(3)-> 传送门 <- ,着重需要理解的是相交链表那道题的双指针思路,明白为什么可以这样,这样为什么可行。后面遇到类似的题目我还会做么?

  • 我们每做一道题目,都要深挖他的题目结构,明白为什么可以这样做。我相信如果你这样去做了,并且不断地练习,到后面,每遇到一个题目,你都会有所印象,并能够很快的指出解这道题的思路。

分割链表

  • 题目链接:-> 传送门 <-

  • 题目描述:现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。

  • 这里的不能改变原来的数据顺序,也就是比x小的节点放在其余节点之前时,这些节点的顺序应该与没有放之前是一样的。

  • 例如: 2 4 8 5 9 3 5 ,给定 x = 8,通过本题目的描述最终的答案应该为:2 4 5 3 5 8 9

图解描述:(给定x = 3
在这里插入图片描述

解题思路:

  • 根据题目的意思以及不能改变原来的数据顺序这一特性,我们可以以一种反归并的思想来想这道题。

  • 我们遍历原链表并创建两个新链表(这里的新链表表示的是在原链表基础上通过某一条件新连接的一串节点),第一个链表用来尾插小于x的节点,第二个链表用来尾插大于等于x的节点,最后再将第一个链表的尾与第二个链表的头相连接,再返回连接后的整个链表的头,便ok啦。整个解题思路大致是这样,后面,来谈谈其中的细节。

  • 对于创建的两个新链表,都需要哨兵位的头节点来维护,什么是哨兵位的头节点呢?我们可以把哨兵位的头节点当作真实头节点的前驱,它是一个不在答案范围内的节点,但它却可以有效的控制真实的链表。其里面的值可以是随机的,它的next初始指向NULL,直到有节点尾插,它的next就指向这个节点,而这个节点就是新连接的链表的真实的头。当最后连接完成时,我们想要返回这个链表,应该返回哨兵位的next,因为哨兵位的next才是有效的真实的头节点。

  • 如果说不用哨兵位的头节点来维护,也是可以的。不过这样会有很多不必要的处理。比如给的原链表是NULL,或者两个新链表连接完后其中有一个为空,这些都有可能造成解题出问题,因此需要额外的处理。所以,为了减少这些麻烦,用哨兵位的头节点来维护这两个新链表,上述的这些情况都能够有效避之(上手写代码就有深刻的体会)。

  • 有了上面的铺垫我们只需要按照题目要求依次在原链表取节点,然后在对应哨兵位节点指向的链表中尾插,最后将这两个链表连接即可。

在这里插入图片描述

下面是代码实现:

这里没学过c++也不用担心,代码纯都是C语言写的。

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// 创建两个哨兵位的头节点// nhead作为连接比x小的节点// rhead作为连接大于等于x的节点struct ListNode* nhead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* rhead = (struct ListNode*)malloc(sizeof(struct ListNode));// 操控连接的指针nhead->next = NULL, rhead->next = NULL;struct ListNode* cur = pHead, * cur1 = nhead, * cur2 = rhead;// 遍历原链表while (cur){// 如果小于x就尾插到nheadif (cur->val < x) {cur1->next = cur;cur1 = cur1->next;}else   // 如果 >= x 就尾插到rhead{cur2->next = cur;cur2 = cur2->next;}cur = cur->next;}// 两个带哨兵位头节点的链表的连接// 第一个的尾连接第二个的头cur1->next = rhead->next;// 将第二个的尾置为NULLcur2->next = NULL;// 保存连接好的整个链表的头节点(哨兵位头节点的下一个)struct ListNode* newhead = nhead->next;// 分别释放创建的两个哨兵位头节点free(nhead);free(rhead);// 返回新链表的头return newhead;}
};

回文链表

  • 题目链接:-> 传送门 <-

  • 题目描述:给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。

  • 回文结构,相信大家已不陌生,类似于123211233216789876这样的数字,都可称之为回文数。而回文链表也是一样,它每个节点的值组成的数就是一个回文数,例如下面这些链表:

在这里插入图片描述

在这里插入图片描述

  • 那么我们该如何判断一个链表是否为回文链表呢?

解题思路一:

  • 我们可以在不破坏原链表的情况下另外创建一个链表,通过遍历原链表依次将原链表上的节点复制尾插到新链表。

  • 然后两个链表从头开始比较,如果有一个节点的值不相等就返回false。两个链表都遍历结束并且最后遍历的指针都同时指向NULL,此时返回true

下面是代码实现:

bool isPalindrome(struct ListNode* head){struct ListNode* rhead = NULL;struct ListNode* cur = head;// 尾插到新链表while (cur){if (rhead == NULL){rhead = (struct ListNode*)malloc(sizeof(struct ListNode));rhead->val = cur->val;rhead->next = NULL;}else {struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));newnode->val = cur->val;newnode->next = rhead;rhead = newnode;}cur = cur->next;}struct ListNode* cur1 = head, * cur2 = rhead;while (cur1 && cur2){// 有不同直接返回falseif (cur1->val != cur2->val) return false;cur1 = cur1->next;cur2 = cur2->next;}// 如果结束且同时指向NULL,说明回文if (cur1 == NULL && cur2 == NULL) return true;else return false;
}

该思路可以说是暴力解法,效率相对较低,并且开了额外的空间,如果限制不能开额外的空间呢?

解题思路二:

  • 上一个思路创建了额外的空间,而本思路将不创建新的空间。

  • 首先,找到链表的中间节点,然后从这个中间节点开始,将后面的节点逆转,最后从链表的头节点和逆转后返回的节点分别开始遍历判断。

  • 如下图解析:

在这里插入图片描述

在这里插入图片描述

  • 可以看到,整个判断过程是一个循环,如果rhead指向空就结束循环,说明是回文链表;如果在循环期间,发现有不一样的值的节点,就直接返回false

  • 对于 -> 找中间节点 <--> 反转链表 <- ,在前面已经讲解过了,在这里,我们直接 ctrl + c , ctrl + v 就好。

下面是代码实现:

// 寻找中间节点函数
struct ListNode* middleNode(struct ListNode* head){struct ListNode* fast = head, * slow = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;
}// 反转链表函数
struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur = head;struct ListNode* prev =  NULL;while (cur){struct ListNode* tmp = cur->next;cur->next = prev;prev = cur;cur = tmp;}return prev;
}bool isPalindrome(struct ListNode* head){// 找中间节点struct ListNode* mid = middleNode(head);// 从中间节点开始反转链表struct ListNode* rlist = reverseList(mid);// 判断while (rlist){if (head->val != rlist->val) return false;rlist = rlist->next;head = head->next;}       return true;
}

写在最后

对于单链表的题目练习,最重要的是思路,我们在数据结构阶段要养成画图的习惯,因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。

感谢阅读本小白的博客,错误的地方请严厉指出噢!

相关文章:

【基础算法】单链表的OJ练习(4) # 分割链表 # 回文链表 #

文章目录前言分割链表回文链表写在最后前言 本章的OJ练习相对前面的难度加大了&#xff0c;但是换汤不换药&#xff0c;还是围绕单链表的性质来出题的。我相信&#xff0c;能够过了前面的OJ练习&#xff0c;本章的OJ也是轻轻松松。 对于OJ练习(3)&#xff1a;-> 传送门 <…...

SpringBoot整合定时任务和邮件发送(邮箱 信息轰炸 整蛊)

SpringBoot整合定时任务和邮件发送&#xff08;邮箱 信息轰炸 整蛊&#xff09; 目录SpringBoot整合定时任务和邮件发送&#xff08;邮箱 信息轰炸 整蛊&#xff09;1.概述2.最佳实践2.1创建项目引入依赖(mail)2.2 修改yml配置文件2.3 启动类添加EnableScheduling注解2.4 执行的…...

Arduino添加ESP32开发板

【2023年3月4日】 最近要在新电脑上安装Arduino&#xff0c;需要进行一些配置&#xff0c;正好记录一下&#xff01; Arduino2.0.1 下的开发板添加操作。 ESP32开发板GitHub链接&#xff1a; GitHub - espressif/arduino-esp32: Arduino core for the ESP32Arduino core for…...

Mysql通配符的使用

LIKE操作符 通配符&#xff1a;用来匹配值的一部分的特殊字符。 搜索模式&#xff1a;由字面值&#xff0c;通配符或两者组合构成的搜索条件。 百分号(%)通配符 搜索模式使用例如下 SELECT prod_id, prod_name FROM products WHERE prod_name Like jet%; 这条子句表示&…...

RocketMQ-02

1. 案例介绍 1.1 业务分析 模拟电商网站购物场景中的【下单】和【支付】业务 ###1&#xff09;下单 用户请求订单系统下单订单系统通过RPC调用订单服务下单订单服务调用优惠券服务&#xff0c;扣减优惠券订单服务调用调用库存服务&#xff0c;校验并扣减库存订单服务调用用户…...

深度学习卷积神经网络CNN之 VGGNet模型主vgg16和vgg19网络模型详解说明(理论篇)

1.VGG背景 2. VGGNet模型结构 3. 特点&#xff08;创新、优缺点及新知识点&#xff09; 一、VGG背景 VGGNet是2014年ILSVRC&#xff08;ImageNet Large Scale Visual Recognition Challenge大规模视觉识别挑战赛&#xff09;竞赛的第二名&#xff0c;解决ImageNet中的1000类图…...

三:BLE协议架构简介

低功耗蓝牙体系整体架构说明1. PHY(物理层)2. LL(链路层)3. HCI(主机与控制器通信接口)4. L2CAP(逻辑链路控制及适配协议)5. ATT(属性协议)6. GATT(通用属性规范)7. GAP(通用访问规范)8. SM(安全管理)整体架构说明 架构层说明PHY1. 物理层2. 控制射频的发送和接收LL1. 链路层2.…...

小型双轮差速底盘双灰度循迹功能的实现

1. 功能说明 在机器人车体上安装2个 灰度传感器 &#xff0c;实现机器人按照下图所指定的路线进行导航运动&#xff0c;来模拟仓库物流机器人按指定路线行进的工作过程。 2. 使用样机 本实验使用的样机为R023e样机。 3. 功能实现 3.1 电子硬件 在这个示例中&#xff0c;我们采…...

电子签名?玩具罢了!

需要的前置知识&#xff1a;简单的canvas绘制线路过程 let canvas document.getElementById(id); //id为canvas标签元素的id&#xff0c;或通过其它方法获取标签 let ctx canvas.getContext(2d); //规定为2d绘制图片&#xff0c;即确定为2d画笔 ctx.strokeStyle "whit…...

【Spring Boot读取配置文件的方式】

Spring Boot 支持多种读取配置文件的方式&#xff0c;常用的方式有以下三种&#xff1a; application.properties&#xff1a; Spring Boot 默认会读取该文件作为应用的配置文件。可以在 src/main/resources 目录下创建该文件&#xff0c;并在其中配置应用的属性。 applicat…...

java学习路线规划

java学习路线规划 一、写在前面 兄弟&#xff0c;我整理了一下关于自己之前学习java的一些方向&#xff0c;给你归纳在这里&#xff0c;有空就来看看&#xff0c;希望对你有帮助。 二、java基础篇 1、认识java ​ 了解java历史&#xff0c;大概看看发展史&#xff0c;安装…...

格密码学习笔记(二):连续极小、覆盖半径和平滑参数

文章目录最短距离和连续极小值距离函数和覆盖半径格的平滑参数致谢最短距离和连续极小值 除了行列式&#xff0c;格的另一个基本量是格上最短非零向量的长度&#xff0c;即格中最短距离&#xff0c;其定义为 λ1min⁡x,y∈L,x≠y∥x−y∥min⁡z∈L,z≠0∥z∥.\begin{aligned} …...

ios 通过搜索设备MAC地址绑定

最近做了一个物联网项目,涉及到了设备绑定配网这块,需要了解一下iOS BLE与设备绑定的相关知识点,第一次接触蓝牙相关的项目,所以开始熟悉蓝牙的相关信息。没有去深入研究BabyTooth库&#xff0c;只是感觉CoreBluetooth已经让我更好的理解整个流程这个物联网项目的设备绑定流程是…...

Python实现人脸识别,进行视频跟踪打码,羞羞的画面统统打上马赛克

哈喽兄弟们&#xff0c;我是轻松~ 今天我们来实现用Python自动对视频打马赛克前言准备工作代码实战效果展示最后前言 事情是这样的&#xff0c;昨天去表弟家&#xff0c;用了下他的电脑&#xff0c;不小心点到了他硬盘里隐藏的秘密&#xff0c;本来我只需要用几分钟电脑的&…...

vcf bed起始位置是0还是1

VCF 起始位置为1, POS - position: The reference position, with the 1st base having position 1. Positions are sorted numerically, in increasing order, within each reference sequence CHROM. It is permitted to have multiple records with the same POS. Telome…...

Hexo+live2d | 如何把live2d老婆放进自己的博客

参考&#xff1a;Hexo添加Live2D看板娘最新教程live2d-widgetlive2d-widget-models网页/博客Hexo添加live2d游戏角色看板娘,简易添加&#xff0c;碧蓝航线等live2d新型游戏角色模型&#xff08;moc3&#xff09;live2d-moc3jsdelivr方法1可以直接去看参考文章的第一部分的第一篇…...

【微信小程序】-- 页面导航 -- 导航传参(二十四)

&#x1f48c; 所属专栏&#xff1a;【微信小程序开发教程】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &…...

Pytorch学习笔记#2: 搭建神经网络训练MNIST手写数字数据集

学习自https://pytorch.org/tutorials/beginner/basics/quickstart_tutorial.html 导入并预处理数据集 pytorch中数据导入和预处理主要用torch.utils.data.DataLoader 和 torch.utils.data.Dataset Dataset 存储样本及其相应的标签&#xff0c;DataLoader在数据上生成一个可迭…...

C语言 猜名次、猜凶手、杨辉三角题目详解

猜名次题目&#xff1a;5位运动员参加了10米台跳水比赛&#xff0c;有人让他们预测比赛结果&#xff1a;A选手说&#xff1a;B第二&#xff0c;我第三&#xff1b;B选手说&#xff1a;我第二&#xff0c;E第四&#xff1b;C选手说&#xff1a;我第一&#xff0c;D第二&#xff…...

蚁群算法负荷预测

%% 清空环境变量 clc clear close all format compact %% 网络结构建立 %% 清空环境变量 clc clear close all format compact %% 网络结构建立 %读取数据 dataxlsread(天气_电量_数据.xlsx,C12:J70);%前7列为每个时刻的发电量 最后列为天气 for i1:58 input(i,:)[data…...

ubuntu添加系统服务实现开机root权限运行

需求 开机自动运行程序(或脚本)&#xff0c;需要以root权限运行但不输入密码&#xff0c;也不能将密码写入文件。 环境 Ubuntu 20.04 解决方案 添加系统服务&#xff0c;然后通过systemctl控制。 操作步骤 假设目标程序为/home/xxx/test 1、创建service配置文件 [Unit…...

【阅读笔记】你不知道的Javascript--类与类型委托3

目录类一些常见原理混入行为委托委托理论类与对象更妙的设计与语法类型冷门关键词typeof 防范机制值原生函数访问内部属性类 一些常见原理 在继承或者实例化时&#xff0c;JavaScript 的对象机制并不会自动执行复制行为&#xff1b; 多态&#xff1a;JS 中的多态&#xff0c…...

文件服务设计

一、需求背景 文件的上传、下载功能是软件系统常见的功能&#xff0c;包括上传文件、下载文件、查看文件等。例如&#xff1a;电商系统中需要上传商品的图片、广告视频&#xff0c;办公系统中上传附件&#xff0c;社交类系统中上传用户头像等等。文件上传下载大致流程为&#…...

【批处理脚本】-1.22-字符串界定符号 ““

"><--点击返回「批处理BAT从入门到精通」总目录--> 共3页精讲(列举了所有字符串界定符号 ""的用法,图文并茂,通俗易懂) 在从事“嵌入式软件开发”和“Autosar工具开发软件”过程中,经常会在其集成开发环境IDE(CodeWarrior,S32K DS,Davinci,…...

【Flutter·学习实践·UI篇】基础且重要的UI知识

前言 参考学习官网&#xff1a;《Flutter实战第二版》 学习前先记住&#xff1a;Flutter 中万物皆为Widget&#xff0c;心中默念3次以上铭记于心。 这一点和开发语言Dart的变量一切皆是对象的概念&#xff0c;相互对应。 Widget 在前面的介绍中&#xff0c;我们知道在Flutt…...

【OpenCV】车牌自动识别算法的设计与实现

写目录一. &#x1f981; 设计任务说明1.1 主要设计内容1.1.1 设计并实现车牌自动识别算法&#xff0c;基本功能要求1.1.2 参考资料1.1.3 参考界面布局1.2 开发该系统软件环境及使用的技术说明1.3 开发计划二. &#x1f981; 系统设计2.1 功能分析2.1.1 车辆图像获取2.1.2 车牌…...

SpringBoot发送邮件

目录1. 获取授权码2. jar包引入3. 配置application4. 代码实现1. 获取授权码 以126邮箱为例&#xff0c;点开设置&#xff0c;选择POP3/SMTP/IMAP 开启POP3/SMTP服务&#xff0c;新增授权密码 扫码二维码&#xff0c;发送要求的短信内容到指定的号码即可&#xff0c;然后会返回…...

BigInteger类和BigDecimal类的简单介绍

文章目录&#x1f4d6;前言&#xff1a;&#x1f380;BigInteger类和BigDecimal类的由来&#x1f380;BigDecimal类的优点&#x1f380;BigDecimal类容易引发的错误&#x1f3c5;处理方法&#x1f4d6;前言&#xff1a; 本篇博客主要介绍BigInteger类和BigDecimal类的用途及常…...

mysql五种索引类型---实操版本

背景 最近学习了Mysql的索引&#xff0c;索引对于Mysql的高效运行是非常重要的&#xff0c;正确的使用索引可以大大的提高MySql的检索速度。通过索引可以大大的提升查询的速度。不过也会带来一些问题。比如会降低更新表的速度&#xff08;因为不但要把保存数据还要保存一下索引…...

【微信小程序】-- 页面导航 -- 编程式导航(二十三)

&#x1f48c; 所属专栏&#xff1a;【微信小程序开发教程】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &…...