网站文章在哪发布做seo,客户网站建设,上海高端it网站建设,图文设计与制作创作不易#xff0c;友友们给个三连吧#xff01;#xff01;
一、旋转数组#xff08;力扣#xff09;
经典算法OJ题#xff1a;旋转数组 思路1#xff1a;每次挪动1位#xff0c;右旋k次
时间复杂度#xff1a;o(N^2)
右旋最好情况#xff1a;k是n的倍数… 创作不易友友们给个三连吧
一、旋转数组力扣
经典算法OJ题旋转数组 思路1每次挪动1位右旋k次
时间复杂度o(N^2)
右旋最好情况k是n的倍数相当于不右旋此时为o1
右旋最坏情况k%nn-1,此时为oN^2
空间复杂度:o(1)
void rotate(int* nums, int numsSize, int k)
{k%numsSize;while(k){int tempnums[numsSize-1];//从后往前挪 for(int inumsSize-1;i0;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,numsnumsSize-k,sizeof(int)*k);//nums的后k个按顺序拷贝到新数组的前面memcpy(arrk,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 temp0;while(leftright){temparr[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就可以找到消失的数据但是目前掌握的排序中冒泡排序的时间复杂度是oN^2而qsort的时间复杂度是ologNN,均不符合题意这里不做考虑
思路2让0和0-numsSize的所有数都异或一遍再和数组中的所有元素异或一边最后得到的结果就是消失的数利用了a^a0a^0a的结论
时间复杂度o(N)
空间复杂度o(1)
int missingNumber(int* nums, int numsSize)
{
int x0;
for(int i0;inumsSize;i)
{x^i;x^nums[i];
}
x^numsSize;//还多了一个数
return x;
}
思路30-numsSize的所有数相加然后减去数组中的所有元素之和得到的就是消失的数字。
时间复杂度o(N)
空间复杂度o(1)
int missingNumber(int* nums, int numsSize)
{int sum0;//记录
for(int i0;inumsSize;i)
{sumi;sum-nums[i];
}
sumnumsSize;
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 count0;//统计结点
while(pcur)
{pcurpcur-next;count;
}
if(countk)
return NULL;//考虑链表为NULL以及k大于链表结点数
pcur pListHead;
for(int i0;icount-k;i)
pcurpcur-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*fastpListHead,*slowpListHead;
while(k)
{//考虑k大于结点数的情况此时链表很早就为空了if(fastNULL)return NULL;fastfast-next;k--;
}
//同时走直到fast为NULL此时slow指向倒数第k个结点
while(fast)
{fastfast-next;slowslow-next;
}
//如果k0.那么第一个while循环不会进入
//fast和slow同时走最后都会指向空所以不需要额外判断
return slow;
}
思路3直接反转链表然后直接找第k个结点
该方法直接改变了链表结构使得phead变成了一个尾结点与其他结点建立不起联系所以该思路不行尽量不要去改变原先链表的结构在力扣中过不了。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ){
//直接反转链表然后找第k个结点
if(pListHeadNULL)
return NULL;
struct ListNode*p1NULL;
struct ListNode*p2pListHead;
struct ListNode*p3pListHead-next;
int count0;//用来数数
while(p2)
{p2-nextp1;p1p2;p2p3;if(p3)p3p3-next;count;
}
//此时的p1就是新链表的头结点
if(kcount||kcount)
return NULL;
while(--k)
{
p1p1-next;
}
return p1;
} 四、相交链表力扣
经典算法OJ题相交链表 思路1A链表逐个结点与B链表比较如果存在相等则就是相交结点注要比较指针而不能比较值因为值是可以重复的
空间复杂度:o(N^2)
时间复杂度:o(1)
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{ListNode* pcurAheadA;ListNode* pcurBheadB;while(pcurA){while(pcurB){if(pcurApcurB)return pcurA;pcurBpcurB-next;}pcurBheadB;pcurApcurA-next;}return NULL;
}
思路2长的链表往后走长度差再同时走直到相等就是相交点 空间复杂度:o(N)
时间复杂度:o(1)
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{ListNode * ApcurheadA;//用来遍历A链表ListNode * BpcurheadB;//用来遍历A链表int a0;//数a长度int b0;//数b长度
while(Apcur)
{
ApcurApcur-next;
a;
}
while(Bpcur)
{
BpcurBpcur-next;
b;
}
//找最小数写俩while循环只要大的数才可以走小的走不了
int mab?b:a;
while(a-m)
{headAheadA-next;a--;
}
while(b-m)
{headBheadB-next;b--;
}
while(headA)
{if(headAheadB)return headA;headAheadA-next;headBheadB-next;
}
return NULL;
}
五、链表的回文结构牛客
经典算法OJ题链表的回文结构 思路1找到中间结点然后逆置后半段,然后将后续半段和前半段的链表同时走如果其中一个走到空了值依旧是相等的那么就是回文结构
空间复杂度:o(N)
时间复杂度:o(1)
ListNode *middleNode(struct ListNode *phead)
{
struct ListNode *fast,*slow;
fastslowphead;
while(fast!NULLfast-next!NULL)
{
fastfast-next-next;
slowslow-next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{//链表为空的时候if(headNULL)return head;//链表不为空的时候创建3个指针分别指向前驱、当前、后继结点
struct ListNode*p1,*p2,*p3;
p1NULL;//前驱
p2head;//当前
p3head-next;//后继
while(p2)
{//改变指向
p2-nextp1;
//向后挪动
p1p2;
p2p3;
//考虑p3为NULL的时候
if(p3)
p3p3-next;
}
return p1;
}
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {struct ListNode *midmiddleNode(A);//找中间结点struct ListNode *rmidreverseList(mid);//逆序后半段while(rmid){if(A-val!rmid-val)return false;AA-next;rmidrmid-next;}return true;}
};
六、随机链表的复制力扣
经典算法OJ题随机链表的复制 思路11、插入拷贝结点到原结点的后面2、控制拷贝结点的random3、拷贝结点解下来尾插到新链表上同时恢复原链表
空间复杂度:o(N)
时间复杂度:o(N)
typedef struct Node Node;
Node* copyRandomList(Node* head)
{if(headNULL)return NULL;//将拷贝结点放在原结点的后面Node*pcurhead;while(pcur){Node*copy(Node*)malloc(sizeof(Node));//拷贝结点copy-valpcur-val;//插入copy-nextpcur-next;pcur-nextcopy;//迭代pcurpcur-next-next;}//控制拷贝结点的random指针pcurhead;while(pcur){//有可能random指向NULLNode* copypcur-next;if(pcur-randomNULL)copy-randomNULL;else//拷贝结点的random恰好在原结点的random后面copy-randompcur-random-next;//迭代pcurpcur-next-next;}//将拷贝结点解下来尾插到新链表上pcurhead;Node*newhead,*newtail,*temp;newheadnewtail(struct Node*)malloc(sizeof(struct Node));tempNULL;//用来记录遍历点while(pcur){Node* copypcur-next;tempcopy-next;//记录遍历点newtail-nextcopy;//尾插newtailnewtail-next;//修复原链表pcur-nexttemp;//继续遍历pcurpcur-next;}Node*retnewhead-next;//销毁哨兵结点前记住头结点free(newhead);newheadNULL;return ret;
}
思路2暴力拷贝链表然后看原结点的random是原链表的第几个结点对应的就是拷贝链表的的第几个结点 空间复杂度:o(N^2)
时间复杂度:o(N)
typedef struct Node Node;
Node* copyRandomList(Node* head)
{if(headNULL)return NULL;Node*pcurhead;Node*newhead,*newtail;newheadnewtail(Node*)malloc(sizeof(Node));//哨兵结点while(pcur){Node*newnode(Node*)malloc(sizeof(Node));newnode-valpcur-val;newtail-nextnewnode;newtailnewnode;//迭代pcurpcur-next;}newtail-nextNULL;//要记住最后有个NULLpcurhead;//回到链表头Node*newpcurnewhead-next;//用来遍历新链表头while(pcur){int s0;//记录节点与head的距离Node*flaghead,*temppcur-random;//temp记住random结点while(flag!temp){s;flagflag-next;}flagnewhead-next;//回到新链表的头while(s--)flagflag-next;//找到了就接上newpcur-randomflag;pcurpcur-next;newpcurnewpcur-next;}Node*retnewhead-next;free(newhead);newheadNULL;return ret;
}
七、带环链表的快慢指针追击问题力扣
7.1 判断链表中是否有环
经典算法OJ题判断链表是否带环 思路快慢指针追击 typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head)
{ListNode*fast,*slow;fastslowhead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast)return true;}return false;
}
7.2 返回链表开始入环的第一个结点
思路1利用相遇点到入口点距离等于链表头到入口点距离的结论 typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head)
{ListNode*fast,*slow;fastslowhead;while(fastfast-next){slowslow-next;fastfast-next-next;//相等说明相遇了链表带环if(slowfast){ListNode*meetslow;while(meet!head){meetmeet-next;headhead-next;}return meet;}} return NULL;
}
思路2:在相遇点将带环链表拆开转化成求链表相交结点的问题
typedef struct ListNode ListNode;struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{ListNode * ApcurheadA;//用来遍历A链表ListNode * BpcurheadB;//用来遍历A链表int a0;//数a长度int b0;//数b长度
while(Apcur)
{
ApcurApcur-next;
a;
}
while(Bpcur)
{
BpcurBpcur-next;
b;
}
//找最小数写俩while循环只要大的数才可以走小的走不了
int mab?b:a;
while(a-m)
{headAheadA-next;a--;
}
while(b-m)
{headBheadB-next;b--;
}
while(headA)
{if(headAheadB)return headA;headAheadA-next;headBheadB-next;
}
return NULL;
}
struct ListNode *detectCycle(struct ListNode *head)
{ListNode*fast,*slow;fastslowhead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){//将带环链表的环拆开ListNode*newheadslow-next;slow-nextNULL;return getIntersectionNode(newhead,head);}}return NULL;
}7.3 追击问题扩展
根据前两题可以知道对于带环的链表fast走2步slow走1步
1、必然会相遇不会错过
2、Ln-1*CC-x 一个指针从相遇点走一个指针从链表头走最后会在入口点相遇 如果fast走3步slow走1步可以得到什么结论
