电子商务电商网站饿建设,管理网站建设,做虾苗网站有哪些流程,免费建电子商务网站前言#xff1a;
在前面我们了解到了时间复杂度与空间复杂度#xff0c;这里我们就可以尝试一下做一些关于时间复杂度与空间复杂度的题目。
1. 数组篇
题目一#xff1a;消失的数字
消失的数字#xff1a;. - 力扣#xff08;LeetCode#xff09; 思路#xff1a; 看…前言
在前面我们了解到了时间复杂度与空间复杂度这里我们就可以尝试一下做一些关于时间复杂度与空间复杂度的题目。
1. 数组篇
题目一消失的数字
消失的数字. - 力扣LeetCode 思路 看到这个题目我们首先的思路是先排序然后如果后一个数字不等于前一个数字1的话那么这个就是消失的数字那么排序我们选择冒泡排序呢还是qsort排序我们发现这个题目限制了时间复杂度为0(N),冒泡排序的时间复杂度是O(N^2),这个不行那么我们选择qsort排序吗qsort排序的时间复杂度是O(N*logn)这个貌似也是不行的。 这里我们就需要利用到一种新的思路了用异或^来进行解决我们知道0^任何数都是任何数相同的数异或就是0,比如说1^2^1的结果是2我们利用这个思路首先用0来异或0到N之间的所有数字然后再把这个结果拿到数组里面进行异或最后异或的结果就是那个消失的数字。 时间复杂度是O(N) 空间复杂度是O(1) 代码
int missingNumber(int* nums, int numsSize){int ret 0;//这里我们先异或0到N之间的数字for(int i 0;inumsSize;i){ret ret^i;}//然后将异或完的结果拿到数组里面进行异或for(int i 0;i numsSize; i){ret ret^nums[i];}//最后的结果就是消失的数字我们直接返回这个值return ret;
} 题目二轮转数组
轮转数组. - 力扣LeetCode
思路 首先看到这个题目我们的想法是先创建一个变量把数组的最后一个元素存起来然后将数组整体完后移动一位然后将存起来的元素放在数组的首元素然后循环k次这样就完成了但是这个思路过不了这个题目。 这里力扣给出了一个超长的数组。所以过不了。 那我们就选择另一种思路 三段逆置法 我们首先将数组的前numsSize-k个数据进行逆置然后再将数组的后k个数据进行逆置最后将我们的数组整体进行逆置这样就完成了轮转数组。 时间复杂度为O(N) 空间复杂度为O(1) 当然这一种思路可能不是那么容易想到 我们这里还有一种思路创建一个数组然后将原数组的后k个拷贝到新数组里面然后再将前numsSize-k个拷贝到新数组里面最后再将新数组里面的数据都拷贝到原数组里面这样 也可完成这个轮转数组 时间复杂度为O(N) 空间复杂度为O(N) 三段逆置代码
void revolve(int*a ,int m,int n)
{int left m;int right n;while(left right){int tmp a[left];a[left] a[right];a[right] tmp;left;right--;}
}
void rotate(int* nums, int numsSize, int k) {k k % numsSize;//将数组的前numsSize-k个逆置revolve(nums,0,numsSize-k-1);//将数组的后k个逆置revolve(nums,numsSize-k,numsSize-1);//将数组整体逆置revolve(nums,0,numsSize-1);
}
创建新数组拷贝方法
void _rotate(int*nums,int numsSize,int k,int*tmp)
{k k%numsSize;int n numsSize;//将后k个数据拷贝到新数组里面memcpy(tmp,numsn-k,sizeof(int)*k);//将前n-k个数据拷贝到新数组里面memcpy(tmpk,nums,sizeof(int)*(n-k));//将新数组里面的数据全部拷贝到原数组里面memcpy(nums,tmp,sizeof(int)*n);
}
void rotate(int* nums, int numsSize, int k) {int tmp[numsSize];_rotate(nums,numsSize,k,tmp);} 2. 单链表篇
题目一返回倒数第k个节点
返回倒数第k个节点. - 力扣LeetCode 这里如果说给我们加上一个限制条件空间复杂度是O(1),只能遍历一遍链表那么这个题应该怎么解呢
思路 首先我们用到我们之前使用过的快慢指针这样的一个解法我们先让快指针走k步然后它们两个同时走当快指针走到空时慢指针刚好走到倒数第k个节点。 时间复杂度为O(N) 空间复杂度为O(1) 代码
typedef struct ListNode sl;
int kthToLast(struct ListNode* head, int k){//首先我们创建两个指针sl* slow head;sl* fast head;//让快指针先走k步while(k--){fast fast-next;}//再两个指针同时走while(fast){fast fast-next;slow slow-next;}//当快指针走到空时这时慢指针刚好就是倒数第k个节点return slow-val;
}题目二回文链表
回文链表. - 力扣LeetCode 这里可能很多人不清楚什么是回文回文相当于是链表从中间切开是对称的。
思路 我们这里首先要找到链表的中间节点然后将中间节点之后的节点进行逆置我们再从链表的第一个有效节点和链表的中间节点开始进行比对。 代码
typedef struct ListNode sl;sl* revse(sl* phead){sl* p1 NULL;sl* p2 phead;sl* p3 phead-next;while(p2){p2-next p1;p1 p2;p2 p3;if(p3! NULL){p3 p3-next;}}return p1;}
bool isPalindrome(struct ListNode* head) {//创建快慢指针找中间节点sl* slow head;sl* fast head;while(fastfast-next){slow slow-next;fast fast-next-next;}//将中间节点之后的节点逆置sl* phead revse(slow);sl* pcur head;//遍历链表进行比对while(phead){if(phead-val! pcur-val){return false;}pcur pcur-next;phead phead-next;}return true;
}
题目三相交链表
相交链表:. - 力扣LeetCode 思路 要解决这一题首先我们要判断链表是否相交。怎么判断相交呢我们直接看两个链表的尾节点的地址是否相同如果相同就是相交的反之就是不相交这里我们判断尾节点是否相同的时候不要用节点里面的数据来判断是否相交这样容易出错。 到这里就说明它们两个相交了那么这里我们有两种思路可以求解 思路1暴力求解将A链表的节点依次的跟B链表的所有节点进行比较A链表某个节点跟B链表的某个节点相同这个节点就是交点。我们考虑这个思路的时候也是可以分析一下它的时间复杂度这个链表肯定需要两层循环来帮助我们进行判断那么它的时间复杂度为O(N^2)。 思路2若不想采取思路1的方法我们是否可以找到更优的解法呢?当然有就是让两个链表从同一个位置开始走怎么样才能让两个链表从同一个位置走呢我们先计算A链表的长度在计算B链表的长度算出它们长度的差让开链表先走差距步然后再让两个链表同时走找相同节点的地址这个节点就是它们的交点。我们简单分析一下这个思路的时间复杂度为O(N)发现比前一个思路更优那我们就采取第二种方法进行求解。 代码
typedef struct ListNode sl;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//创建两个指针遍历两个链表sl* pcura headA;sl* pcurb headB;//创建两个变量记录两个链表的长度int counta 0;int countb 0;while(pcura-next){pcura pcura-next;counta;}while(pcurb-next){pcurb pcurb-next;countb;}//判断两个尾节点是否相同if(pcura ! pcurb){return NULL;}//这里计算出它们两个的差距int gap abs(counta-countb);//我这里先使用假设法假设长链表是A链表短链表是B链表sl* longlist headA;sl* shortlist headB;//这里再判断B链表节点的个数大于A链表节点再设置谁是长链表谁是短链表if(countbcounta){longlist headB;shortlist headA;}//让长链表先走差距步while(gap--){longlist longlist-next;}//再两个链表同时走while(longlist!shortlist){longlist longlist-next;shortlist shortlist-next;}//最后随便返回两个链表中的一个节点地址就好了return shortlist;}
题目四环形链表Ⅰ
环形链表Ⅰ. - 力扣LeetCode 思路 这里我们采用快慢指针的思路来进行解题这里我们让慢指针一次走一步快指针一次走两步这样就变成了一个追击问题了如果快指针在环里面碰见了慢指针说明带环如果快指针走到了空说明是不带环的。 代码
typedef struct ListNode sl;
bool hasCycle(struct ListNode *head) {//创建快慢指针sl* slow head;sl* fast head;//循环遍历链表while(fastfast-next){slow slow-next;fast fast-next-next;//如果快指针在环里面遇见了慢指针if(fast slow){//说明带环return true;}}//如果出了循环代表链表不带环return false;
}
其实呢这个题目的考点是这样的。
1.为什么一定会相遇有没有可能会错过永远追不上请你证明 2.slow每次走1步fast每次走3步4步5步N步请证明一定会追上吗
这里我们就简单用fast每次走三步来进行证明 这里永远追不上的条件有两个
1.N是奇数 2.c-1是奇数
那么存在同时N是奇数且C是偶数的情况吗 其实不会同时存在这两种情况所以一定能追上。
其他fast走4步5步,N步推理同理只不过情况不一样。
题目五环形链表Ⅱ
环形链表Ⅱ. - 力扣LeetCode
思路 这个题目需要我们判断链表是否带环如果带环找出入环的第一个节点。 思路1这里我们找到它们的相遇点然后然后创建一个指针newhead指向相遇点的下一个节点再将相遇点的指针指向置为空然后再定义一个指针指向原链表的头这样就变成两个链表的相交问题了 思路2直接使用双指针法一个从头节点开始走一个从相遇点开始走当这两个指针再次相遇的地方就是链表入环的第一个节点。 这里我们采取的是思路二的代码
代码
typedef struct ListNode sl;
struct ListNode *detectCycle(struct ListNode *head){//创建快慢指针sl* slow head;sl* fast head;while(fastfast-next){slow slow-next;fast fast-next-next;//如果带环if(fast slow){//创建指针指向相遇的节点sl* meet fast;//慢指针从头开始走slow head;//遍历链表while(slow){//如果相遇了if(meet slow){//说明这个节点就是入环口return meet;}meet meet-next;slow slow-next;}}}return NULL;
} 这里有一个问题为什么从meet节点走和从头节点开始走时的路程是一样的。 题目六随机链表的复制
随机链表的复制:. - 力扣LeetCode 什么是深拷贝 深拷贝拷贝一个值和指针指向跟当前链表一模一样的链表 思路 这个题目拷贝链表不是问题问题在于怎么把拷贝链表的random指针的指向弄准确这里就有一个方法我们把每个拷贝的节点都插入在链表节点的后面那么拷贝节点就跟链表节点有了关联再将拷贝节点的random指针指向对应的拷贝节点最后再将拷贝节点从原链表上面拿下来。这样就完成了复杂链表的拷贝。 代码
typedef struct Node sl;
struct Node* copyRandomList(struct Node* head) {sl* pcur head;//将拷贝的每一个节点都尾插在原链表节点的后面while(pcur){sl* copy (sl*)malloc(sizeof(sl));copy-val pcur-val;copy-next pcur-next;pcur-next copy;pcur copy-next;}pcur head;//将拷贝的每个节点的random指向对应的拷贝节点while(pcur){sl* copy pcur-next;if(pcur-random NULL){copy-random NULL;}else{copy-random pcur-random-next;}pcur copy-next;}//创建新链表进行接收拷贝的所有节点pcur head;sl*phead NULL;sl* ptail NULL;while(pcur){sl* copy pcur-next;sl*next copy-next;if(phead NULL){phead ptail copy;}else{ptail-next copy;ptail ptail-next;}pcur next;}return phead;
}
