算法刷题第五天(跑路人笔记)<双指针>

简介: 算法刷题第五天(跑路人笔记)<双指针>

第五天

链表的中间节点

image.png

876. 链表的中间结点 - 力扣(LeetCode)

使用快慢指针,fast指针一次走两个节点slow一次走一个节点.当fast或fast->next 走到NULL时我们的slow也就到了中间节点位置

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head)
{
    if(head == NULL)
    {
        return NULL;
    }
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast != NULL&&fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

删除链表的倒数第N个节点

19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)

image.png

思路一(自己写法)

先遍历一遍数组得到数组长度然后通过数组长度和n(倒数第几的值)值相减的循环来得到使我们得到倒数第几的地址并我们先记录他上一个节点的地址最后处理特殊情况即可.

struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    if(head == NULL)
        return NULL;
    struct ListNode* cur = head;
    int len = 0;
    while(cur != NULL)
    {
        cur = cur->next;
        len++;
    }
    cur = head;
    struct ListNode* prev = head;
    for(int i = 0;i < len-n;i++)
    {
        prev = cur;//记录上一个节点
        cur = cur->next;
    }
    if(len == n)//解决删头节点问题
    {
        struct ListNode* tmp = head;
        head = head->next;
        free(tmp);
        return head;
    }
    if(prev == cur)//解决只有一个节点问题
    {
        free(cur);
        return NULL;
    }
    //正常情况
    prev->next = cur->next;
    return head;
}

官方解法可以避免if语句去处理特殊情况不过有一点点难理解.但是整体思路相同.


思路二(双指针)

双指针的思路其实也很简单通过两个指针先让快指针先走n个节点再让慢节点和快捷点一起走最终当快指针走到空时结束(注:我写的是fast->next==NULL时退出是为了让慢指针指向要删除的前一个节点方便我们后面的删除).

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    //头结点本身就为空
    if(head ==NULL)
    {
        return NULL;
    }
    //只有一个节点
    if(head->next == NULL)
    {
        free(head);
        return NULL;
    }
    for(int i =0;i<n;i++)//fast先走n步 
    {
        fast = fast->next;
    }
    while(fast != NULL&&fast->next != NULL)//fast!=NULL是为了防止删头结点.
    {
        slow = slow->next;
        fast = fast->next;
    }
    //fast为空只能是删头结点的时候
    if(fast == NULL)
    {
        struct ListNode* cur = head;
        head = head->next;
        free(cur);
        return head;
    }
    struct ListNode* tmp = slow->next;
    slow->next = tmp->next;
    free(tmp);
    return head;
}
相关文章
|
18天前
|
算法 API 计算机视觉
人脸识别笔记(一):通过yuface调包(参数量54K更快更小更准的算法) 来实现人脸识别
本文介绍了YuNet系列人脸检测算法的优化和使用,包括YuNet-s和YuNet-n,以及通过yuface库和onnx在不同场景下实现人脸检测的方法。
27 1
|
18天前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
30 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
18天前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
10 0
|
19天前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
28 0
|
8天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
26天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于MSER和HOG特征提取的SVM交通标志检测和识别算法matlab仿真
### 算法简介 1. **算法运行效果图预览**:展示算法效果,完整程序运行后无水印。 2. **算法运行软件版本**:Matlab 2017b。 3. **部分核心程序**:完整版代码包含中文注释及操作步骤视频。 4. **算法理论概述**: - **MSER**:用于检测显著区域,提取图像中稳定区域,适用于光照变化下的交通标志检测。 - **HOG特征提取**:通过计算图像小区域的梯度直方图捕捉局部纹理信息,用于物体检测。 - **SVM**:寻找最大化间隔的超平面以分类样本。 整个算法流程图见下图。
|
5天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。
|
6天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于贝叶斯优化CNN-LSTM网络的数据分类识别算法matlab仿真
本项目展示了基于贝叶斯优化(BO)的CNN-LSTM网络在数据分类中的应用。通过MATLAB 2022a实现,优化前后效果对比明显。核心代码附带中文注释和操作视频,涵盖BO、CNN、LSTM理论,特别是BO优化CNN-LSTM网络的batchsize和学习率,显著提升模型性能。
|
11天前
|
存储
基于遗传算法的智能天线最佳阵列因子计算matlab仿真
本课题探讨基于遗传算法优化智能天线阵列因子,以提升无线通信系统性能,包括信号质量、干扰抑制及定位精度。通过MATLAB2022a实现的核心程序,展示了遗传算法在寻找最优阵列因子上的应用,显著改善了天线接收功率。
|
13天前
|
监控 算法 数据安全/隐私保护
基于三帧差算法的运动目标检测系统FPGA实现,包含testbench和MATLAB辅助验证程序
本项目展示了基于FPGA与MATLAB实现的三帧差算法运动目标检测。使用Vivado 2019.2和MATLAB 2022a开发环境,通过对比连续三帧图像的像素值变化,有效识别运动区域。项目包括完整无水印的运行效果预览、详细中文注释的代码及操作步骤视频,适合学习和研究。