企业官网建设流程全解析

网站开发公司谁家好,asp网站程序,ts wordpress,打造对外宣传工作平台网站建设文章目录 前言题目1 旋转链表算法分析代码实现实现细节与实战思考 题目2 广度优先遍历打印二叉树问题题目背景与核心需求算法分析代码实现细节分析与实战思考 总结 前言 考试方式是邮箱发送网址#xff0c;进行牛客网线上笔试#xff0c;四道编程题目#xff0c;两道标准算…文章目录前言题目1 旋转链表算法分析代码实现实现细节与实战思考题目2 广度优先遍历打印二叉树问题题目背景与核心需求算法分析代码实现细节分析与实战思考总结前言考试方式是邮箱发送网址进行牛客网线上笔试四道编程题目两道标准算法题目两道实际应用型算法题本篇博客分享前两道题。四道题全部写在一起篇幅太大了题目1 旋转链表题目链接牛客 NC211 旋转链表题目描述算法分析链表的旋转操作若直接逐节点移动会因重复遍历导致时间复杂度达到O ( k ∗ n ) O(k*n)O(k∗n)这在k较大时完全不可行。结合链表的特性我们可将其转化为环形结构来简化操作先遍历链表统计长度将尾节点指向头节点形成环此时旋转k个位置的本质是找到新头节点的位置并断开环。由于旋转n次n为链表长度后链表会回到初始状态因此我们只需计算k % n得到有效旋转次数再从原头节点向后移动n - (k % n)个节点该节点的下一个节点即为新头节点断开此处的环即可完成旋转。代码实现/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */classSolution{public:ListNode*rotateLinkedList(ListNode*head,intk){// 边界情况空链表或单节点链表无需旋转直接返回原头节点if(headnullptr||head-nextnullptr)returnhead;ListNode*curhead;intsize1;// 遍历链表统计长度同时定位到尾节点while(cur-next!nullptr){size;curcur-next;}// 将尾节点指向头节点构建环形链表cur-nexthead;// 计算有效旋转次数避免重复旋转k%size;// 计算需要移动的步数找到新头节点的前驱节点intmove_stepsize-k;ListNode*markhead;// 移动到新头节点的前驱节点for(inti1;imove_step;i)markmark-next;// 确定新头节点并断开环形结构ListNode*newheadmark-next;mark-nextnullptr;returnnewhead;}};实现细节与实战思考在实际解题过程中边界条件的处理是避免出错的关键空链表或仅有一个节点的链表无论旋转多少次结果都不变可直接返回原头节点。构建环形链表时需确保遍历到真正的尾节点——即cur-next为nullptr的节点而非仅遍历到最后一个有值节点。关于步数计算的细节容易成为易错点move_step表示从原头节点到新头节点前驱节点的步数循环从1开始而非0是因为初始时mark已指向原头节点对应第1个节点只需再移动move_step - 1次即可到达目标位置。例如链表长度为5、k2时move_step3循环执行2次mark最终指向第3个节点其下一个节点即为新头节点。题目2 广度优先遍历打印二叉树问题题目链接牛客 JZ78 把二叉树打印成多行 [ 并不是原题但是比这道题简单并不用分层直接就是程序便利输入到一个数组中即可。传送门这道题和我今天做的每日一题很像都是BFS解决二叉树层序遍历的问题更加详细的解释可以看这篇博客 N 叉树的层序遍历题目描述题目背景与核心需求二叉树的层序遍历是广度优先搜索BFS的经典应用本题要求将二叉树按层打印每一层的节点值单独存入一个数组最终返回二维数组结果。不同于普通的层序遍历本题需要精准区分每一层的节点避免不同层的节点混在一起这就要求在遍历过程中对每一层的节点数量进行精准统计。算法分析广度优先遍历依赖队列实现核心思路是利用队列的“先进先出”特性逐层处理节点。在遍历开始时先将根节点入队每一轮循环中先记录当前队列的大小即当前层的节点数再依次取出该数量的节点将节点值存入当前层的数组同时将每个节点的左右子节点若存在入队。当当前层的所有节点处理完毕后将该层的数组存入结果集重复此过程直到队列为空。这种方式能确保每一轮循环仅处理一层节点天然实现了层与层的分隔。代码实现/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */#includequeue#includevectorclassSolution{public:vectorvectorintPrint(TreeNode*pRoot){// 存储最终的分层打印结果vectorvectorintret;// 边界条件空树直接返回空结果if(pRootnullptr)returnret;// 队列用于存储待处理的节点实现广度优先遍历queueTreeNode*q;q.push(pRoot);// 队列非空时说明还有未处理的节点while(!q.empty()){// 记录当前层的节点数量这是分层的关键intlevel_sizeq.size();// 存储当前层的节点值vectorintlevel_nums;// 遍历当前层的所有节点while(level_size--){TreeNode*tmpq.front();level_nums.push_back(tmp-val);q.pop();// 左子节点存在则入队为下一层遍历做准备if(tmp-left!nullptr)q.push(tmp-left);// 右子节点存在则入队if(tmp-right!nullptr)q.push(tmp-right);}// 将当前层的结果存入最终结果集ret.push_back(level_nums);}returnret;}};细节分析与实战思考队列的使用是本题的核心其“先进先出”的特性恰好匹配层序遍历“从上到下、从左到右”的顺序。在实际解题时level_size的取值时机尤为重要——必须在处理当前层节点前获取队列大小因为处理节点的过程中会将下一层节点入队若在循环中获取会导致统计的节点数包含下一层内容。例如对于一棵三层二叉树初始时队列仅含根节点level_size1处理完根节点后其左右子节点入队此时队列大小变为2第二轮循环中level_size2处理完这两个节点后它们的子节点入队队列大小变为4以此类推。这种方式能精准划分每一层的节点避免层序混乱。此外边界条件的处理不可忽视空树的情况下直接返回空的二维数组避免后续操作中访问空指针导致程序崩溃。在遍历节点时需先判断左右子节点是否存在再将其入队这是防止无效节点入队的必要步骤。总结旋转链表问题的核心是通过构建环形链表简化旋转操作结合取模运算优化旋转次数同时需精准定位新头节点的前驱节点以断开环形结构边界条件空链表、单节点链表的处理是避免错误的关键。二叉树分层打印的核心是利用队列实现广度优先遍历通过记录每一轮循环前的队列大小区分不同层节点确保每一轮仅处理当前层节点子节点入队的时机和顺序决定了遍历的正确性。两道题目均体现了“先优化问题模型再处理细节”的解题思路旋转链表将多次旋转转化为环形结构的一次断开二叉树遍历将“分层”需求转化为队列大小的统计这种思路能有效降低时间复杂度提升代码效率。