做云图的网站,黄石手机网站建设,设备外贸用哪个网站,建设局平台系列综述#xff1a; #x1f49e;目的#xff1a;本系列是个人整理为了秋招面试的#xff0c;整理期间苛求每个知识点#xff0c;平衡理解简易度与深入程度。 #x1f970;来源#xff1a;材料主要源于左程云算法课程进行的#xff0c;每个知识点的修正和深入主要参考… 系列综述 目的本系列是个人整理为了秋招面试的整理期间苛求每个知识点平衡理解简易度与深入程度。 来源材料主要源于左程云算法课程进行的每个知识点的修正和深入主要参考各平台大佬的文章其中也可能含有少量的个人实验自证。 结语如果有帮到你的地方就点个赞和关注一下呗谢谢 【C】秋招实习面经汇总篇 文章目录 链表问题基本问题 参考博客 点此到文末惊喜↩︎
链表问题
基本问题
笔试和面试 对于笔试一般不需要在意空间复杂度对于面试时间复杂度作为第一位但是一定要尽量节省空间 题目 输入链表头节点奇数长度返回中点偶数长度返回上中点输入链表头节点奇数长度返回中点偶数长度返回下中点输入链表头节点奇数长度返回中点的前一个偶数长度返回上中点的前一个输入链表头节点奇数长度返回中点的前一个偶数长度返回下中点的前一个
// 输入链表头节点奇数长度返回中点偶数长度返回上中点
Node FindNode(Node head) {// 健壮性检查if (head nullptr || head-next nullptr || head-next-next nullptr)return head;// 初始化Node slow head-next;Node fast head-next-next;while (fast-next ! nullptr fast-next-next ! nullptr) {slow slwo-next;fast fast-next;}return slow;
}// 输入链表头节点奇数长度返回中点偶数长度返回下中点
Node FindNode(Node head) {// 健壮性检查if (head nullptr || head-next nullptr || head-next-next nullptr)return head;// 初始化Node slow head-next;Node fast head-next; // 初始化位置不同while (fast-next ! nullptr fast-next-next ! nullptr) {slow slwo-next;fast fast-next;}return slow;
}判断是否为链表是否回文 思路1先使用栈进行存储然后再从链表头开始与栈中元素进行比较思路2找到链表中间然后使用栈存储后半部分再链表与栈中进行一一比较思路3原地空间找到链表中间将后半部分指针逆序然后
// 定义三个匿名函数进行处理
auto 找中点
auto 反转链表
auto 比较链表调整小于放左边等于放中间大于放右边 笔试使用放在数组中然后进行partition桶思想进行区域划分小于、等于、大于的每个区域有两个指针
在这里插入代码片克隆带有随机指针的链表 思路1使用unordered_mapint, Node*遍历链表存入哈希表中再遍历一遍设置随机指针思路2在每个节点后面克隆并插入然后设置新插入节点的random指针分离新节点链表这个过程和random无关
Node* copyRandomList(Node* head) {if (head nullptr) return nullptr;// 复制结点并插入到结点后面Node *cur head;Node *next nullptr;while (cur ! nullptr) {next cur-next;cur-next new Node(cur-val);cur-next-next next;cur next;}// 复制所有结点的random关系cur head;Node *cur_copy nullptr;while (cur ! nullptr) {next cur-next-next; // 先记录cur_copy cur-next;cur_copy-random cur-random ! nullptr ? cur-random-next : nullptr;cur next; // 后迭代}// 分离链表Node *res head-next;cur head;while (cur ! nullptr) {// 先记录后使用注意每次迭代要还原和结尾情况next cur-next-next;cur_copy cur-next;cur-next next;cur_copy-next next ! nullptr ? next-next : nullptr;cur next;}return res;
}如何两个链表相交返回第一个交点 如果不相交返回nullptr 思路1使用unordered_set一边遍历一边查set表判断是否成环思路2遍历两个链表长度然后相减。再遍历长链表-短链表长度次最后共同再一起遍历
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if (headA nullptr || headB nullptr) return nullptr;ListNode *cur1 headA;ListNode *cur2 headB;// 求两个链表长度的差值int n 0;while (cur1-next ! nullptr) {n;cur1 cur1-next;} while (cur2-next ! nullptr) {--n;cur2 cur2-next;}// 如果两个链表相交必然最后一个结点地址相同// 否则两个链表不相交if (cur1 ! cur2) return nullptr;cur1 (n 0 ? headA : headB);cur2 (n 0 ? headB : headA);n abs(n); // 差值转正// 长链表头先走差值步while (n ! 0) {--n;cur1 cur1-next;}// 两个链表头一起走while (cur1 ! cur2) {cur1 cur1-next;cur2 cur2-next;}return cur1;
}链表成环问题如果成环返回环的入口结点 遍历成环的单链表如果思路1使用unordered_set一边遍历一边查set表判断是否成环思路2快指针一次走两步慢指针一次走一步。然后在环内相遇后然后快指针重新从头开始快慢指针继续走再次遇到环的入口
ListNode *detectCycle(ListNode *head) {// 健壮性检查注意必须都不为空if (head nullptr || head-next nullptr || head-next-next nullptr) return nullptr;// 先进行一次然后就可以将判断条件设置为fast ! slowwListNode *fast head-next-next;ListNode *slow head-next;// 快指针走两步慢指针走一步while (fast ! slow) {if (fast-next nullptr || fast-next-next nullptr)return nullptr;slow slow-next;fast fast-next-next;}// 然后快指针指向头两个指针同步每次走一步fast head;while (fast ! slow) {slow slow-next;fast fast-next;}return slow;
}知道一个单链表中的某个结点地址删除该结点 思路1遍历链表到该结点的前一个结点然后进行删除思路2借尸还魂使用该节点的后一个结点的值拷贝覆盖该结点然后删除该节点的后一个结点。 拷贝开销如果结点拷贝开销特别大如集群则无法进行结尾结点问题无法删除链表的最后一个结点但是结尾可以使用一个空结点哨兵标识结尾 少年我观你骨骼清奇颖悟绝伦必成人中龙凤。 不如点赞·收藏·关注一波 点此跳转到首行↩︎
参考博客 对数器 单调队列 快速链表quicklist《深入理解计算机系统》侯捷C全系列视频 待定引用 待定引用 待定引用
