顺序表、链表相关OJ题（2）

创作不易，友友们给个三连吧！！

一、旋转数组（力扣）

经典算法OJ题：旋转数组

思路1：每次挪动1位，右旋k次

时间复杂度：o(N^2)       

右旋最好情况：k是n的倍数，相当于不右旋，此时为o（1）

右旋最坏情况：k%n==n-1,此时为o（N^2）

空间复杂度:o(1)

void rotate(int* nums, int numsSize, int k) 
{
    k%=numsSize;
    while(k)
    {
        int temp=nums[numsSize-1];
        //从后往前挪 
        for(int i=numsSize-1;i>0;i--)
        {
             nums[i]=nums[i-1];//最后一个是nums[1]=num[0]
        }
        nums[0]=temp;
        k--;//旋转一次就减一次
    }
}

注：这是常规思路，但是由于空间复杂度太高，数组个数特别多的时候，在力扣运行的时候超出了时间限制！

思路2：创建一个和nums一样长度的新数组，将nums数组的后k个元素，先按顺序放进新数组里，然后剩下前面的n-k个元素，再按顺序放进新数组,最后再将新数组的数据拷贝到nums中

时间复杂度：o(N)

空间复杂度：o(N)

void rotate(int* nums, int numsSize, int k) 
{
   k%=numsSize;
   int arr[numsSize];//vs不支持变长数组，但是牛客支持，如果是vs只能使用动态数组。
   memcpy(arr,nums+numsSize-k,sizeof(int)*k);//nums的后k个按顺序拷贝到新数组的前面
   memcpy(arr+k,nums,sizeof(int)*(numsSize-k));//nums的前n-k个按顺序拷贝到新数组的后面
   memcpy(nums,arr,sizeof(int)*numsSize);//新数组完全拷贝到nums数组中
}

思路3：前n-k个元素逆置，后k个元素逆置，再整体逆置

时间复杂度：o(N)

空间复杂度：o(1)

void reverse (int *arr,int left,int right)//实现逆序函数
{
    int temp=0;
    while(left<right)
    {
        temp=arr[left];
        arr[left]=arr[right];
        arr[right]=temp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k) 
{
    k%=numsSize;
   reverse(nums,0,numsSize-k-1);//前n-k个元素逆序
   reverse(nums,numsSize-k,numsSize-1);//后k个逆序
   reverse(nums,0,numsSize-1);//完全逆序
}

二、消失的数字（力扣）

经典算法OJ题：消失的数字

思路1：先进行排序，如果后一个不等于前一个+1，就可以找到消失的数据，但是目前掌握的排序中，冒泡排序的时间复杂度是o（N^2），而qsort的时间复杂度是o（logN+N）,均不符合题意，这里不做考虑！

思路2：让0和0-numsSize的所有数都异或一遍，再和数组中的所有元素异或一边，最后得到的结果就是消失的数（利用了a^a=0，a^0=a的结论）

时间复杂度：o(N)

空间复杂度：o(1)

int missingNumber(int* nums, int numsSize)
{
int x=0;
for(int i=0;i<numsSize;i++)
{
    x^=i;
    x^=nums[i];
}
x^=numsSize;//还多了一个数
return x;
}

思路3：0-numsSize的所有数相加，然后减去数组中的所有元素之和，得到的就是消失的数字。

时间复杂度：o(N)

空间复杂度：o(1)

int missingNumber(int* nums, int numsSize)
{
    int sum=0;//记录
for(int i=0;i<numsSize;i++)
{
  sum+=i;
  sum-=nums[i];
}
sum+=numsSize;
return sum;
}

三、链表中倒数第k个结点（牛客）

经典算法OJ题：链表中倒数第k个结点

思路1：第一次循环计算结点的个数count，然后求倒数第k个就是正数的第count-k个结点

空间复杂度:o(N)

时间复杂度:o(1)

 typedef struct ListNode ListNode;
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
 {
ListNode* pcur= pListHead;
int count=0;//统计结点
while(pcur)
{
    pcur=pcur->next;
    count++;
}
if(count<k)
return NULL;//考虑链表为NULL，以及k大于链表结点数
pcur= pListHead;
for(int i=0;i<count-k;i++)
pcur=pcur->next;
return pcur;
}

思路2：（快慢指针）fast指针先走k步，然后fast和slow同时走，始终保持k的距离，当fast走到NULL的时候，slow对应的恰好就是倒数第k个结点

空间复杂度:o(N)

时间复杂度:o(1)

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
 {
struct ListNode*fast=pListHead,*slow=pListHead;
while(k)
{
    //考虑k大于结点数的情况，此时链表很早就为空了
    if(fast==NULL)
    return NULL;
    fast=fast->next;
    k--;
}
//同时走，直到fast为NULL，此时slow指向倒数第k个结点
while(fast)
{
    fast=fast->next;
    slow=slow->next;
}
//如果k<=0.那么第一个while循环不会进入，
//fast和slow同时走，最后都会指向空，所以不需要额外判断
return slow;
}

思路3：直接反转链表，然后直接找第k个结点

该方法直接改变了链表结构，使得phead变成了一个尾结点，与其他结点建立不起联系，所以该思路不行（尽量不要去改变原先链表的结构）在力扣中过不了。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
 {
//直接反转链表，然后找第k个结点
if(pListHead==NULL)
return NULL;
struct ListNode*p1=NULL;
struct ListNode*p2=pListHead;
struct ListNode*p3=pListHead->next;
int count=0;//用来数数
while(p2)
{
    p2->next=p1;
    p1=p2;
    p2=p3;
    if(p3)
    p3=p3->next;
    ++count;
}
//此时的p1就是新链表的头结点
if(k<=count||k>count)
return NULL;
while(--k)
{
p1=p1->next;
}
return p1;
}

四、相交链表（力扣）

经典算法OJ题：相交链表

思路1：A链表逐个结点与B链表比较，如果存在相等，则就是相交结点（注：要比较指针而不能比较值，因为值是可以重复的）

空间复杂度:o(N^2)

时间复杂度:o(1)

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
   ListNode* pcurA=headA;
   ListNode* pcurB=headB;
   while(pcurA)
   {
       while(pcurB)
       {
           if(pcurA==pcurB)
           return pcurA;
           pcurB=pcurB->next;
       }
       pcurB=headB;
       pcurA=pcurA->next;
   }
   return NULL;
}

思路2：长的链表往后走长度差，再同时走，直到相等就是相交点

空间复杂度:o(N)

时间复杂度:o(1)

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
   ListNode * Apcur=headA;//用来遍历A链表
    ListNode * Bpcur=headB;//用来遍历A链表
    int a=0;//数a长度
    int b=0;//数b长度
while(Apcur)
{
Apcur=Apcur->next;
a++;
}
while(Bpcur)
{
Bpcur=Bpcur->next;
b++;
}
//找最小数，写俩while循环，只要大的数才可以走，小的走不了
int m=a>b?b:a;
while(a-m)
{
    headA=headA->next;
    a--;
}
while(b-m)
{
    headB=headB->next;
    b--;
}
while(headA)
{
    if(headA==headB)
    return headA;
    headA=headA->next;
    headB=headB->next;
}
return NULL;
}

五、链表的回文结构（牛客）

经典算法OJ题：链表的回文结构

思路1：找到中间结点，然后逆置后半段,然后将后续半段和前半段的链表同时走，如果其中一个走到空了值依旧是相等的，那么就是回文结构！！

空间复杂度:o(N)

时间复杂度:o(1)

ListNode *middleNode(struct ListNode *phead)
{
struct ListNode *fast,*slow;
fast=slow=phead;
while(fast!=NULL&&fast->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
    //链表为空的时候
    if(head==NULL)
    return head;
    //链表不为空的时候，创建3个指针，分别指向前驱、当前、后继结点
struct ListNode*p1,*p2,*p3;
p1=NULL;//前驱
p2=head;//当前
p3=head->next;//后继
while(p2)
{
    //改变指向
p2->next=p1;
//向后挪动
p1=p2;
p2=p3;
//考虑p3为NULL的时候
if(p3)
p3=p3->next;
}
return p1;
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) 
    {
        struct ListNode *mid=middleNode(A);//找中间结点
           struct ListNode *rmid=reverseList(mid);//逆序后半段
           while(rmid)
           {
            if(A->val!=rmid->val)
            return false;
            A=A->next;
            rmid=rmid->next;
           }
           return true;
    }
};

六、随机链表的复制（力扣）

经典算法OJ题：随机链表的复制

思路1：1、插入拷贝结点到原结点的后面，2、控制拷贝结点的random，3、拷贝结点解下来，尾插到新链表上，同时恢复原链表

空间复杂度:o(N)

时间复杂度:o(N)

typedef struct Node Node;
Node* copyRandomList(Node* head) 
{
    if(head==NULL)
    return NULL;
	//将拷贝结点放在原结点的后面
      Node*pcur=head;
    while(pcur)
    {
       Node*copy=(Node*)malloc(sizeof(Node));//拷贝结点
       copy->val=pcur->val;
       //插入
       copy->next=pcur->next;
       pcur->next=copy;
       
       //迭代
       pcur=pcur->next->next;
    }
    //控制拷贝结点的random指针
    pcur=head;
    while(pcur)
    {
        //有可能random指向NULL
        Node* copy=pcur->next;
        if(pcur->random==NULL)
        copy->random=NULL;
        else
        //拷贝结点的random恰好在原结点的random后面
        copy->random=pcur->random->next;
        //迭代
        pcur=pcur->next->next;
    }
    //将拷贝结点解下来尾插到新链表上
    pcur=head;
    Node*newhead,*newtail,*temp;
    newhead=newtail=(struct Node*)malloc(sizeof(struct Node));
    temp=NULL;//用来记录遍历点
    while(pcur)
    {
        Node* copy=pcur->next;
        temp=copy->next;//记录遍历点
        newtail->next=copy;//尾插
        newtail=newtail->next;
     //修复原链表
     pcur->next=temp;
     //继续遍历
     pcur=pcur->next;
    }
    Node*ret=newhead->next;//销毁哨兵结点前记住头结点
    free(newhead);
    newhead=NULL;
    return ret;
}

思路2：暴力拷贝链表，然后看原结点的random是原链表的第几个结点，对应的就是拷贝链表的的第几个结点

空间复杂度:o(N^2)

时间复杂度:o(N)

typedef struct Node Node;
Node* copyRandomList(Node* head) 
{
    if(head==NULL)
    return NULL;
    Node*pcur=head;
    Node*newhead,*newtail;
    newhead=newtail=(Node*)malloc(sizeof(Node));//哨兵结点
   while(pcur)
   {
      Node*newnode=(Node*)malloc(sizeof(Node));
      newnode->val=pcur->val;
      newtail->next=newnode;
      newtail=newnode;
      //迭代
      pcur=pcur->next;
   }
   newtail->next=NULL;//要记住最后有个NULL；
   pcur=head;//回到链表头
   Node*newpcur=newhead->next;//用来遍历新链表头
   while(pcur)
   {
       int s=0;//记录节点与head的距离
       Node*flag=head,*temp=pcur->random;//temp记住random结点
       while(flag!=temp)
       {
           ++s;
           flag=flag->next;
       }
       flag=newhead->next;//回到新链表的头
       while(s--)
       flag=flag->next;
       //找到了，就接上
      newpcur->random=flag;
      pcur=pcur->next;
      newpcur=newpcur->next;
   }
   Node*ret=newhead->next;
   free(newhead);
   newhead=NULL;
   return ret;
}

七、带环链表的快慢指针追击问题（力扣）

7.1 判断链表中是否有环

经典算法OJ题：判断链表是否带环

思路：快慢指针追击

 typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head)
{
    ListNode*fast,*slow;
    fast=slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        return true;
    }
    return false;
}

7.2 返回链表开始入环的第一个结点

思路1：利用相遇点到入口点距离等于链表头到入口点距离的结论

 typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head)
{
    ListNode*fast,*slow;
    fast=slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        //相等，说明相遇了，链表带环
        if(slow==fast)
    {
        ListNode*meet=slow;
        while(meet!=head)
        {
            meet=meet->next;
            head=head->next;
        }
        return meet;
    }
  }  
  return NULL;
}

思路2:在相遇点将带环链表拆开，转化成求链表相交结点的问题

typedef struct ListNode ListNode;
 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
   ListNode * Apcur=headA;//用来遍历A链表
    ListNode * Bpcur=headB;//用来遍历A链表
    int a=0;//数a长度
    int b=0;//数b长度
while(Apcur)
{
Apcur=Apcur->next;
a++;
}
while(Bpcur)
{
Bpcur=Bpcur->next;
b++;
}
//找最小数，写俩while循环，只要大的数才可以走，小的走不了
int m=a>b?b:a;
while(a-m)
{
    headA=headA->next;
    a--;
}
while(b-m)
{
    headB=headB->next;
    b--;
}
while(headA)
{
    if(headA==headB)
    return headA;
    headA=headA->next;
    headB=headB->next;
}
return NULL;
}
struct ListNode *detectCycle(struct ListNode *head)
{
    ListNode*fast,*slow;
    fast=slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            //将带环链表的环拆开
        ListNode*newhead=slow->next;
        slow->next=NULL;
        return getIntersectionNode(newhead,head);
        }
    }
    return NULL;
}

7.3 追击问题扩展

根据前两题可以知道对于带环的链表，fast走2步，slow走1步

1、必然会相遇，不会错过

2、L=（n-1）*C+（C-x）   一个指针从相遇点走，一个指针从链表头走，最后会在入口点相遇

如果fast走3步，slow走1步，可以得到什么结论？？

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

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

相关文章

naiveui 上传图片遇到的坑 Upload

naiveui 上传图片遇到的坑 Upload

我在开发图片上传功能, 需要手动触发上传 但是我调用它内部自定义submit方法, 结果接口一直在报错400 我反反复复的测试了好就, 确定了就是我前端的问题,因为之前一直在做后端的错误排查, 以为是编译问题(因为之前也出现过这个问题) 好 , 我把其中一个参数类型改为String类型, …
阅读更多...
c++设计模式之装饰器模式

c++设计模式之装饰器模式

作用 为现有类增加功能 案例说明 class Car { public:virtual void show()0; };class Bmw:public Car { public:void show(){cout<<"宝马汽车>>"<<endl;} };class Audi:public Car { public:void show(){cout<<"奥迪汽车>>&q…
阅读更多...
Java玩转《啊哈算法》解密回文之栈

Java玩转《啊哈算法》解密回文之栈

菩萨清凉月&#xff0c;常游毕竟空&#xff0c;众生心垢净&#xff0c;菩提影现中。 这目录 这开头这代码地址栈案例代码优化建议类似扩展 这开头 各位女士们&#xff0c;先生们好&#xff01;本人最近在看《啊哈算法》&#xff0c;这本书写的确实还可以&#xff0c;很有趣味性…
阅读更多...
代码随想录算法训练营第28天 | 93.复原IP地址 ，78.子集 ，90.子集II

代码随想录算法训练营第28天 | 93.复原IP地址 ，78.子集 ，90.子集II

回溯章节理论基础&#xff1a; https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 93.复原IP地址 题目链接&#xff1a;https://leetcode.cn/problems/restore-ip-addresses/ 思路&#xff1a; 这是切割问题&am…
阅读更多...
2024年2月8日 十二生肖 今日运势

2024年2月8日 十二生肖 今日运势

小运播报&#xff1a;2024年2月8日&#xff0c;星期四&#xff0c;农历腊月廿九 &#xff08;甲辰年丙寅月壬寅日&#xff09;&#xff0c;法定工作日。 红榜生肖&#xff1a;马、猪、狗 需要注意&#xff1a;龙、蛇、猴 喜神方位&#xff1a;正南方 财神方位&#xff1a;正…
阅读更多...
基于swing和cf的推荐相似度SQL实现

基于swing和cf的推荐相似度SQL实现

对于cf和swing算法的介绍可以参考ItemCF的演进&#xff1a;狭义 VS 广义 基于cf的推荐相似度 这里介绍这样一个场景&#xff0c;我们有了大量的电商购买数据&#xff0c;希望通过cf算法计算不同的类目之间的相似度&#xff0c;以方便对用户购买进行兴趣探索。 使用SQL实现需要…
阅读更多...
10.0 Zookeeper 权限控制 ACL

10.0 Zookeeper 权限控制 ACL

zookeeper 的 ACL&#xff08;Access Control List&#xff0c;访问控制表&#xff09;权限在生产环境是特别重要的&#xff0c;所以本章节特别介绍一下。 ACL 权限可以针对节点设置相关读写等权限&#xff0c;保障数据安全性。 permissions 可以指定不同的权限范围及角色。 …
阅读更多...
【STL】：priority_queue介绍和模拟实现

【STL】：priority_queue介绍和模拟实现

朋友们、伙计们&#xff0c;我们又见面了&#xff0c;本期来给大家解读一下有关priority_queue的使用&#xff0c;如果看完之后对你有一定的启发&#xff0c;那么请留下你的三连&#xff0c;祝大家心想事成&#xff01; C 语 言 专 栏&#xff1a;C语言&#xff1a;从入门到精通…
阅读更多...
C# ONNX使用入门教程

C# ONNX使用入门教程

背景 有新入坑的老哥不太了解C# onnx 运行的机理&#xff0c;我这边详细介绍一下&#xff0c;之前直接放官方的样例有点草率了。 准备[python环境] 1、要使用onnx&#xff0c;首先我们就自己生成一个onnx文件&#xff0c;请大家准备一下以下需要的[python]环境 python 版本…
阅读更多...
探索设计模式的魅力：揭秘享元模式-轻松实现资源高效利用的秘密武器

探索设计模式的魅力：揭秘享元模式-轻松实现资源高效利用的秘密武器

设计模式专栏&#xff1a;http://t.csdnimg.cn/U54zu 目录 引言&#xff1a; 一、简介 二、实现资源的极致利用 公共自行车与享元模式的智慧共享 HOW 三、案例探讨 3.1 场景 3.2 不用模式实现&#xff1a;一坨坨代码实现 3.3 痛点 3.4 解决方案分析 注意 四、深入享…
阅读更多...
Qt多线程与SocketTCP的简单实现

Qt多线程与SocketTCP的简单实现

1.相关说明 多线程实现Qt的socket编程实现客户端发送文件&#xff0c;服务端接收文件&#xff0c;并且在客户端设置了心跳&#xff0c;用于监控服务端是否存活。因为Qt中socket套接字发送数据&#xff0c;会先把数据发送至缓冲区中&#xff0c;在发送数据过程中&#xff0c;soc…
阅读更多...
寒假学习第24天---PythonPoc基础编写（二）

寒假学习第24天---PythonPoc基础编写（二）

提示&#xff1a;所分享内容仅用于每一个爱好者之间的技术讨论及教育目的&#xff0c;所有渗透及工具的使用都需获取授权&#xff0c;禁止用于违法途径&#xff0c;否则需自行承担&#xff0c;本作者不承担相应的后果。 文章目录 前言一、 目标二、过程思路实践开始 总结完整代…
阅读更多...
Java基于微信小程序的驾校报名小程序，附源码

Java基于微信小程序的驾校报名小程序，附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…
阅读更多...
腾讯云游戏服务器购买入口，详细配置精准报价

腾讯云游戏服务器购买入口，详细配置精准报价

2024年更新腾讯云游戏联机服务器配置价格表&#xff0c;可用于搭建幻兽帕鲁、雾锁王国等游戏服务器&#xff0c;游戏服务器配置可选4核16G12M、8核32G22M、4核32G10M、16核64G35M、4核16G14M等配置&#xff0c;可以选择轻量应用服务器和云服务器CVM内存型MA3或标准型SA2实例&am…
阅读更多...
创建网站的具体步骤是什么？

创建网站的具体步骤是什么？

创建网站的具体步骤是什么 一.领取一个免费域名和SSL证书&#xff0c;和CDN 1.打开网站链接&#xff1a;https://www.rainyun.com/z22_ 2.在网站主页上&#xff0c;您会看到一个"登陆/注册"的选项。 3.点击"登陆/注册"&#xff0c;然后选择"微信登…
阅读更多...
假期刷题打卡--Day26

假期刷题打卡--Day26

1、MT1212乘法表 请编写一个简单程序&#xff0c;输出九九乘法表。输入n&#xff0c;就输出乘法表到n的地方。 格式 输入格式&#xff1a; 输入整型 输出格式&#xff1a; 输出整型。形式如&#xff1a;1*11 样例 1 输入&#xff1a; 5输出&#xff1a; 1*11 2*12 …
阅读更多...
格子表单GRID-FORM | 文档网站搭建（VitePress）与部署（Github Pages）

格子表单GRID-FORM | 文档网站搭建（VitePress）与部署（Github Pages）

格子表单/GRID-FORM已在Github 开源&#xff0c;如能帮到您麻烦给个星&#x1f91d; GRID-FORM 系列文章 基于 VUE3 可视化低代码表单设计器嵌套表单与自定义脚本交互文档网站搭建&#xff08;VitePress&#xff09;与部署&#xff08;Github Pages&#xff09; 效果预览 格…
阅读更多...
服装设计公司，如何用钉钉实现企业数字化成功转型？

服装设计公司，如何用钉钉实现企业数字化成功转型？

钉钉作为数字化工作平台&#xff0c;为某服装设计公司实现了组织管理的数字化转型&#xff0c;构建了一站式的工作平台。通过钉钉赋能&#xff0c;有利于企业推进组织架构、员工沟通、产品运营和客户服务等方面的数字化、智能化转型。 借助钉钉平台&#xff0c;该服设公司轻松实…
阅读更多...
【C++第二阶段】空指针访问成员函数常成员函数常成员属性

【C++第二阶段】空指针访问成员函数常成员函数常成员属性

你好你好&#xff01; 以下内容仅为当前认识&#xff0c;可能有不足之处&#xff0c;欢迎讨论&#xff01; 文章目录 空指针访问成员函数常成员函数&常成员属性 空指针访问成员函数 类对象类型的空指针可以访问成员函数&#xff0c;但是不能够访问带有成员属性的成员函数。…
阅读更多...
js-添加网页快捷方式

js-添加网页快捷方式

title: js-添加网页快捷方式 categories: Javascript tags: [p快捷方式] date: 2024-02-04 15:28:25 comments: false mathjax: true toc: true js-添加网页快捷方式 前篇 谷歌上包困难的情况, 只能通过投放落地页来缓解一下痛苦, web2app 那种形式有几个比较大的缺点就是需要…
阅读更多...
最新文章

Copyright @ 2022~2023