空间复杂度与链表刷题

"一切的一切都是你自己在感应."

本文索引

  • 空间复杂度
    • 复杂度实例
      • 实例1
      • 实例2
      • 实例3
  • 链表题目
    • 1. 返回倒数第K个节点
    • 2. 链表的回文结构
    • 3. 相交链表
    • 4. 随机链表的复制
    • 5. 环形链表
  • 总结:

前言:
本文主要探究空间复杂度与链表题目讲解
更多文章点击主页: 酷酷学!!!
如果此文对您有帮助, 您的点赞与关注是我最大的动力 !

正文开始

空间复杂度

空间复杂度也是一个数学表达式, 是对一个算法在运行时临时占用存储空间大小的量度.
空间复杂度不是程序占用了多少bytes的空间, 因为这个也没太大意义, 所以空间复杂度算的是变量的个数. 空间复杂度计算规则基本跟时间复杂度类似, 也使用大O渐进表示法.
注意: 函数运行时所需要的栈空间(存储参数,局部变量,一些寄存器信息等)在编译期间已经确定好了, 因此空间复杂度主要通过函数在运行时候显示申请的额外空间来确定.

复杂度实例

实例1

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }

        if (exchange == 0)
            break;
    }
}

解析:

首先解决这个问题我们需要计算额外的空间, 这里一共创建了三个变量, end, exchange, i ,使用了常数个额外空间，所以空间复杂度为 O(1)

实例2

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
    if (n == 0)
        return NULL;

    long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
    }

    return fibArray;
}

解析:
在这里插入图片描述
这里,一共开辟了N个函数栈帧, 动态开辟了N个空间，空间复杂度为 O(N),而时间复杂度为O(2^N).

实例3

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
    if (N == 0)
        return 1;

    return Fac(N - 1) * N;
}

解析:

在这里插入图片描述

递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)

链表题目

1. 返回倒数第K个节点

题目链接: 返回倒数第K个节点

题目描述:

在这里插入图片描述
题目分析:
       本题的解法有很多种, 例如创建数组, 或者将链表反转等等, 这里我们采用一种比较经典的双指针法, 只需要变量一遍链表, 并且空间复杂度为O(1),时间复杂度为O(N), 首先采用数理思想, 定义快慢指针, 快指针先走K个节点,然后在同时走, 因为中间的差距一直为K,所以当快指针走到NULL的时候, 此时慢指针即为倒数第K个节点.因为题目要求K值是有效的, 所以我们也无需判断K值是否有效.

画图演示:

在这里插入图片描述

代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

//时间复杂度为O(1)
int kthToLast(struct ListNode* head, int k){

    struct ListNode* fast = head;
    struct ListNode* slow = head;

    while(k--)
    {
        fast = fast->next;
    }
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;
}

2. 链表的回文结构

题目链接: 链表的回文结构

题目描述:

在这里插入图片描述
题目分析:

       本题可以说是一个综合题, 结合前面对链表的掌握, 理解了思路就变得比较简单, 首先回文结构并不陌生, 数组题目中我们已经见过, 例如12321, 或者1221就是回文结构, 如果是数组, 我们可以采用双指针法, 一个在头, 一个在尾, 两两比较, 分别向中间前进, 但是此时是个链表, 该如何比较呢.

       单链表链表的结构不能直接从后向前遍历, 首先第一步, 寻找中间节点, 然后将中间节点之后的链表进行反转, 然后从头结点开始与中间节点之后的链表的值进行比较, 当然我们需要讨论链表为奇数或者偶数的情况, 但是不难发现, 如下图所示, 不管是奇数还是偶数, 都不影响, 我们只需要判断其中一个链表是否走到NULL.

画图演示:

在这里插入图片描述

代码如下:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cstddef>
class PalindromeList {
public:
        
    //1. 寻找中间节点
    struct ListNode * midNode(ListNode* A)
    {
        struct ListNode * fast = A;
        struct ListNode * slow = A;
        while(fast&&fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
    //2.反转后半段链表
    struct ListNode *reverseNode(ListNode* mid)
    {
        if(mid == NULL)
        {
            return mid;
        }
        struct ListNode * l1 = NULL;
        struct ListNode * l2 = mid;
        struct ListNode * l3 = mid->next;
        while(l2)
        {
            l2->next = l1;
            l1 = l2;
            l2 = l3;
            if(l3)
            {
                l3 = l3->next;
            }
        }
        return l1;
    }

    bool chkPalindrome(ListNode* A) {
        struct ListNode * mid = midNode(A);
        struct ListNode * B = reverseNode(mid);
        while(A&&B)
        {
            if(A->val != B->val)
            {
                return false;
            }
            A = A->next;
            B = B->next;
        }
        return true;
        // write code here
    }
};

3. 相交链表

题目链接: 相交链表

题目描述:

在这里插入图片描述

题目分析:

       判断链表相交, 如果说一个一个比较的话, 链表A的节点依次和链表B的节点一次进行比较这样太麻烦了, 而且时间复杂度为O(N^2), 那么, 判断链表相交 ,我们可以遍历链表, 如果两个链表最后一个节点相等的话, 那么就一定相交, 但是如何返回第一个相交节点呢, 通过分别比较吗, 大可不必, 在我们遍历链表的时候, 我们可以顺便计算出链表的相对差值, 然后让长的链表走差值的距离, 在同时走, 那么只要两个节点相遇, 就是第一个相交节点.

画图演示:

在这里插入图片描述

代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* cur1 = headA;
    struct ListNode* cur2 = headB;
    int long1 = 0,long2 = 0;
    while(cur1->next)
    {
        long1++;
        cur1 = cur1->next;
    }
    while(cur2->next)
    {
        long2++;
        cur2 = cur2->next;
    }
    if(cur1 != cur2)
    {
        return NULL;
    }
    struct ListNode* LongList = headA;
    struct ListNode* ShortList = headB;
    if(long2>long1)
    {
        LongList = headB;
        ShortList = headA;
    }
    int dig = abs(long1-long2);
    while(dig--)
    {
        LongList = LongList->next;
    }
    while(LongList!=ShortList)
    {
        LongList = LongList->next;
        ShortList = ShortList ->next;
    }
    return LongList;
}

4. 随机链表的复制

在这里插入图片描述
在这里插入图片描述
题目分析:
       深拷贝就是复制出来一个一模一样的链表, 如果我们直接创建一个新的节点, 但是对random的处理比较麻烦, 我们需要计算出相对位置, 以确保random的指向正确. 这里我们换一种思路, 如下图所示, 我们在每个节点之后插入一个新的节点, 此时处理random就比较简单了,拷贝节点的 random的指向就是cur->random->next. 最后再将拷贝节点拿下来尾插, 成为一个新的链表.虽然破坏了原链表的结构, 我们也可以进行恢复, 但是题目没有要求 ,所以, 我们也可以不用恢复.

画图演示:

在这里插入图片描述

代码如下:

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur = head;
	while(cur)
    {
        struct Node* copyNode = (struct Node*)malloc(sizeof(struct Node));
        copyNode->val = cur->val;
        copyNode->next = cur->next;
        cur->next = copyNode;
        cur = copyNode->next;
    }
    cur = head;
    while(cur)
    {   
        struct Node* copy = cur->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }
    cur = head;
    struct Node* copyHead = NULL;
    struct Node* copyTail = NULL;
    while(cur)
    {
        struct Node* copy = cur->next;
        //Node* next = copy->next;
        if(copyTail == NULL)
        {
            copyHead = copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }
        cur = copy->next;
        //cur = next;恢复原链表
    }
    return copyHead;
}

5. 环形链表

题目链接:环形链表2

题目描述:

在这里插入图片描述

代码如下:

这里我们采用双指针法, 快指针一次走两步 , 慢指针一次走一步, 因为有相对速度, 所以当慢指针进入环时,快指针开始追击, 当快指针追击上满指针则带环, 若追击不上,则不带环.
面试时可能会问到:

  1. 为什么一定会相遇,有没有可能会错过, 永远追不上? 请证明
  2. slow一次走一步, fast走3步 4步 5步 一定能追上吗? 请证明

首先证明问题1, 一次走一步, 假设slow进环时, fast和slow的距离是N, 那么fast追击slow过程中变化距离如下, 每次追击一次, 距离就缩小1, 距离为0就追上了.
在这里插入图片描述

证明问题2:

这里我们假设fast一次走3步, 当slow进环时, fast开始追击, 每次的距离变化如下, 如果N是偶数的情况下,那么就一定可以追上, 当为奇数时,就进入到第二次的追击, 假设环的长度为C, 那么下一次追击的距离就为C-1, 那如果C-1为偶数的话那么就可以追上, 但是如果C-1又为奇数那么就永远追不上, 此时我们就需要证明会不会永远追不上, 也就是证明当N为奇数的情况下, C-1为奇数, 即C为偶数吗, 通过fast走的距离和slow走的距离, 我们可以知道3slow = fast .

fast走的距离为:L + xC +C-N, (L为未进环时的长度, C为环的长度, x为走的圈数, N为slow进环时和fast的距离)
slow走的距离为: L
由此可得3L = L+XC+C-N
化简可以得到, 2L = (X+1)C - N
此时只需证明N为奇数, C能否为偶数, 是偶数就永远追不上
根据等式 2L一定为偶数, 而N假设为奇数, 那么C如果为偶数的话,
即 偶数 = (X+1)*偶数 - 奇数 等式不成立,
因为只有奇数-奇数才能等于偶数, 所以C 一定为奇数,故不可能追不上
其余证明思想类似

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

接下来, 我们判断出了是带环链表, 那我们如何找到入环时的第一个节点呢?

先来分析一波
假设相遇的时的节点为meet, 那么slow走的路程为L+N, fast走的路程为L+X * C +N ,根据2slow = fast,我们又可以得到
2(L+N) = L+X*C + N
化简得到
L+N = X *C
L = X *C-N
L = (X-1)C +C -N
(X-1)C可以想象成走了多少圈但是还是会回到meet那个位置, 所以L的到第一个入环节点的距离等于C-N
那么我们只需要随便找两个指针, 一个从head开始走, 一个从meet开始走, 只要他们两个相遇, 那么就是第一个入环节点.

在这里插入图片描述
在这里插入图片描述

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

    }
    return NULL;
}

总结:

空间复杂度表示算法在运行过程中需要使用的额外的空间资源。空间复杂度的计算通常是以算法需要的额外空间大小来衡量的。链表是一种常见的数据结构，用于存储和操作一系列具有关联关系的数据元素。
链表的面试题常见的有：
反转链表: 将一个链表反转，即将链表中的节点逆序排列。
链表中倒数第k个节点: 找到链表中倒数第k个节点的值。
链表是否有环: 判断一个链表是否存在环。
合并两个有序链表: 将两个有序链表合并为一个有序链表。
删除链表中的重复元素: 删除链表中重复的元素，使得每个元素只出现一次。
在解决链表面试题时，常用的方法有：
递归法: 使用递归的方式处理链表的问题，递归可以简化问题的处理过程。
快慢指针法: 使用快慢指针来寻找链表中的某个位置，如链表中的中间节点、倒数第k个节点等。
翻转链表法: 使用指针来改变链表节点的指向，实现链表的翻转。
在面试过程中，对于链表问题，需要注意空指针的处理，以及边界条件的判断。同时，对于链表的基本操作，如插入、删除等，也要熟练掌握。

最后感谢关注点赞, 如果错误欢迎指正.

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/613835.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Python自动化测试面试题 —— Selenium篇！

Python自动化测试面试题 —— Selenium篇！

Selenium中有几种等待 隐形等待/智能等待 dr.implicitly_wait() 显性等待 WebDriverWait 强制等待 time.sleep() Selenium中有哪些定位方式 8种 tag 三大基本属性 id/name/class_name 链接 link text/partial link text 高级 css selector/xpath 弹框怎么处理 4种弹…
阅读更多...
Mac电脑安装打开APP显示问题已损坏 问题解决

Mac电脑安装打开APP显示问题已损坏 问题解决

当MAC电脑安装完软件打开时&#xff0c;显示文件已损坏&#xff0c;无法打开。搜了很多教程终于找到解决方案&#xff0c;记录下方便以后再用。 我的mac电脑是intel芯片的&#xff0c;如果你遇到这个问题&#xff0c;可以参考我的这个方案。 1.首先当打开软件后出现 “xx软件已…
阅读更多...
云效 Pipeline as Code 来了！这些场景，用好它效率翻倍！

云效 Pipeline as Code 来了！这些场景，用好它效率翻倍！

从可视化编排到支持 YAML 编排 云效流水线 Flow 是开箱即用的企业级持续集成和持续交付工具&#xff0c;支持丰富的代码源、构建、自动化测试工具、多种部署类型和部署方式&#xff0c;与阿里云深度集成&#xff0c;还提供多种企业级特性&#xff0c;助力企业高效完成从开发到…
阅读更多...
【Pip】pip 安装第三方包异常:[SSL:CERTIFICATE_VERIFY_FAILED]解决方案

【Pip】pip 安装第三方包异常:[SSL:CERTIFICATE_VERIFY_FAILED]解决方案

pip 安装第三方包异常:[SSL:CERTIFICATE_VERIFY_FAILED] 大家好 我是寸铁&#x1f44a; 总结了一篇pip 安装第三方包异常:[SSL:CERTIFICATE_VERIFY_FAILED]✨ 喜欢的小伙伴可以点点关注 &#x1f49d; 报错 今天在安装第三方包时报错如下: 解决方案 本质上是需要指定信任的镜像…
阅读更多...
SpringBoot+Vue实现图片滑块和文字点击验证码

SpringBoot+Vue实现图片滑块和文字点击验证码

一、背景 1.1 概述 传统字符型验证码展示-填写字符-比对答案的流程&#xff0c;目前已可被机器暴力破解&#xff0c;应用程序容易被自动化脚本和机器人攻击。 摒弃传统字符型验证码&#xff0c;采用行为验证码采用嵌入式集成方式&#xff0c;接入方便&#xff0c;安全&#…
阅读更多...
train_gpt2_fp32.cu

train_gpt2_fp32.cu

源程序 llm.c/test_gpt2_fp32.cu at master karpathy/llm.c (github.com) #include <stdio.h> #include <stdlib.h> #include <math.h> #include <time.h> #include <assert.h> #include <float.h> #include <string.h> #include…
阅读更多...
国内十大免费图床推荐

国内十大免费图床推荐

国内十大免费图床推荐 近期&#xff0c;莫卡乐AI导航站汇总了国内一些出色的图床网站&#xff0c;既有知名大站&#xff0c;也有小众网站&#xff0c;用户的使用体验都非常好&#xff01; 1.路过图床 地址&#xff1a;https://imgse.com/ 我们是国内知名的图床之一&#xf…
阅读更多...
Windows只能安装在GPT磁盘上

Windows只能安装在GPT磁盘上

转换磁盘分区形式 步骤1. 先按照正常流程使用Windows系统安装光盘或系统U盘引导计算机。 步骤2. 在Windows安装程序中点击“开始安装”&#xff0c;然后按ShiftF10打开命令提示符。 步骤3. 依次输入以下命令&#xff0c;并在每一行命令后按一次Enter键执行。 步骤4. 等待转换…
阅读更多...
条件平差——以水准网平差为例 (python详细过程版)

条件平差——以水准网平差为例 (python详细过程版)

目录 一、原理概述二、案例分析三、代码实现四、结果展示本文由CSDN点云侠原创，原文链接。如果你不是在点云侠的博客中看到该文章，那么此处便是不要脸的爬虫与GPT。 一、原理概述 条件平差的函数模型和随机模型为： A V + W = 0
阅读更多...
Dbeaver network unavailable due to certificate issue

Dbeaver network unavailable due to certificate issue

场景&#xff1a;出现在DBeaver连接数据库下载驱动的时候 解决&#xff1a; 别勾选就可以了
阅读更多...
制冰机的分类介绍

制冰机的分类介绍

制冰机分别有哪些类型&#xff1f;制冰机顾思义就是制作冰块的机器&#xff0c;但是冰块分片冰、块冰、管冰、颗粒冰等。根据制冰机制出冰块的形状&#xff0c;可以分为&#xff1a;片冰机、块冰机、管冰机、颗粒冰机、雪花机、板冰机、以及最新研制的球冰机等。 制冰机是采用制…
阅读更多...
linux 安装 mangodb 并设置服务开机自启

linux 安装 mangodb 并设置服务开机自启

1、下载 wget http://mosquitto.org/files/source/mosquitto-1.6.8.tar.gz 2、解压 tar -zxvf mosquitto-1.6.8.tar.gz 3、编译安装cd mosquitto-1.6.8 make sudo make install4、在当前目录。进入mosquitto服务文件存放的文件夹 cd service/systemd可以看到3个文件 点击read…
阅读更多...
2024年旅游行业薪酬报告

2024年旅游行业薪酬报告

来源&#xff1a;薪智 近期历史回顾&#xff1a; 2024年中国健康家电消费洞察及趋势研究报告.pdf 2024巴菲特股东大会5万字完整版.pdf 2024年全国大学生新媒体直播大赛.pdf 2024北京市高级别自动驾驶示范区数据安全治理白皮书.pdf 2024年第一季度开发者健康调查报告.pdf 2024年…
阅读更多...
商务分析方法与工具（八）：Python的趣味快捷-年少不知numpy好，再见才觉很简单

商务分析方法与工具（八）：Python的趣味快捷-年少不知numpy好，再见才觉很简单

Tips&#xff1a;"分享是快乐的源泉&#x1f4a7;&#xff0c;在我的博客里&#xff0c;不仅有知识的海洋&#x1f30a;&#xff0c;还有满满的正能量加持&#x1f4aa;&#xff0c;快来和我一起分享这份快乐吧&#x1f60a;&#xff01; 喜欢我的博客的话&#xff0c;记得…
阅读更多...
CentOS 磁盘扩容与创建分区

CentOS 磁盘扩容与创建分区

文章目录 未分配空间创建新分区重启服务器添加物理卷扩展逻辑卷 操作前确认已给服务器增加硬盘或虚拟机已修改硬盘大小&#xff08;必须重启服务才会生效&#xff09;。 未分配空间 示例说明&#xff1a;原服务器只有40G&#xff0c;修改虚拟机硬盘大小再增加20G后硬盘变为60G。…
阅读更多...
OpenID Connect 是什么？和 OAuth 有哪些异同？

OpenID Connect 是什么？和 OAuth 有哪些异同？

因为工作关系&#xff0c;我需要给一个业务网站配置一个 SSO&#xff0c;我一看&#xff0c;这个业务网站只支持 SAML 和 OpenID Connect&#xff0c;也即 OIDC。其实早就听说过这个词&#xff0c;但是没有仔细了解过。所以&#xff0c;特来学习一下到底什么是 OIDC。 一、 什…
阅读更多...
【计算机网络】计算机网络的性能指标

【计算机网络】计算机网络的性能指标

&#x1f6a9;本文已收录至专栏&#xff1a;计算机网络学习之旅 计算机网络的性能指标被用来从不同方面度量计算机网络的性能。常用的八个计算机网络性能指标&#xff1a;速率、带宽、吞吐量、时延、时延带宽积、往返时间、利用率、丢包率。 一.速率 (1) 数据量 比特&#…
阅读更多...
【论文笔记】DualBEV: CNN is All You Need in View Transformation

【论文笔记】DualBEV: CNN is All You Need in View Transformation

原文链接&#xff1a;https://arxiv.org/abs/2403.05402 1. 引言 有效的BEV目标检测需要PV到BEV的视图变换&#xff08;VT&#xff09;。目前的VT分为2D到3D和3D到2D两类&#xff0c;前者通过预测深度概率提升2D特征&#xff0c;但存在深度不确定性&#xff1b;后者则使用3D查…
阅读更多...
动态规划解决回文子串问题

动态规划解决回文子串问题

前言&#xff1a; 回文串相关问题在我们的算法题中算是老生常谈&#xff0c;本文主要介绍如何使用动态规划的思路去解决回文串系列问题。 总体思路&#xff1a; 能够将所有的子串是否是回文的信息&#xff0c;存储在二维dp表中。有了这个dp表&#xff0c;就可以将hard难度转…
阅读更多...
信息系统安全与对抗-网络侦查技术与网络扫描技术（期末复习简答题）

信息系统安全与对抗-网络侦查技术与网络扫描技术（期末复习简答题）

1、网络拓扑结构在网络攻击中的作用 查明目标网络的拓扑结构&#xff0c;有利于找到目标网络的关键节点&#xff0c;从而提高攻击效率&#xff0c;达到最大攻击效果。 2、网络侦查在网络攻击中的作用 识别潜在目标系统&#xff0c;确认目标系统适合哪种类型的攻击。 3、百度…
阅读更多...
最新文章

Copyright @ 2022~2023