企业官网建设流程全解析

免费做会计试题网站,wordpress建设软件下载站,做网站安全认证,海外网文文章目录一、二叉树的前序遍历递归法迭代法二、用栈实现队列1. push(int x)#xff1a;将元素加入队列尾部2. pop()#xff1a;移除并返回队列头部元素3. peek()#xff1a;返回队列头部元素4. empty()#xff1a;判断队列是否为空三、无重复字符的最长字串四、打家劫舍1. …文章目录一、二叉树的前序遍历递归法迭代法二、用栈实现队列1. push(int x)将元素加入队列尾部2. pop()移除并返回队列头部元素3. peek()返回队列头部元素4. empty()判断队列是否为空三、无重复字符的最长字串四、打家劫舍1. 状态定义2. 状态转移方程3. 边界条件五、合并K个升序链表合并两个升序链表递归迭代归并一、二叉树的前序遍历前序遍历的核心顺序是先访问根节点再递归 / 遍历左子树最后递归 / 遍历右子树。递归法终止条件当前节点为null时直接返回无子树可遍历.遍历顺序先访问当前节点记录节点值递归遍历当前节点的左子树递归遍历当前节点的右子树。intidx;typedefstructTreeNodeTreeNode;voidprev(TreeNode*root,int*res){if(rootNULL){return;}res[idx]root-val;prev(root-left,res);prev(root-right,res);}int*preorderTraversal(structTreeNode*root,int*returnSize){idx0;int*res(int*)malloc(200*sizeof(int));prev(root,res);*returnSizeidx;returnres;}迭代法迭代法需要手动用栈模拟递归的调用流程核心是控制 “根→左→右” 的顺序。因为前序遍历是 “根→左→右”而栈是 “后进先出” 结构因此入栈顺序需先压右子树再压左子树这样出栈时左子树先被访问符合 “根→左→右”。步骤 1初始化栈将根节点入栈步骤 2循环取栈顶节点弹出栈顶节点访问并记录其值若该节点有右子树将右子树入栈若该节点有左子树将左子树入栈步骤 3栈为空时遍历结束。int*preorderTraversal(structTreeNode*root,int*returnSize){if(rootNULL){*returnSize0;returnNULL;}int*res(int*)malloc(sizeof(int)*200);*returnSize0;structTreeNode*stack[100];inttop0;stack[top]root;// 根节点入栈while(top0){structTreeNode*currstack[--top];// 弹出栈顶res[(*returnSize)]curr-val;// 访问节点// 先压右子树后进先出左子树会先出栈if(curr-right!NULL){stack[top]curr-right;}// 再压左子树if(curr-left!NULL){stack[top]curr-left;}}returnres;}二、用栈实现队列要实现 “用两个栈模拟队列”核心是利用栈的 “后进先出” 特性通过 “倒栈” 转换为队列的 “先进先出” 特性。队列是「先进先出」栈是「后进先出」—— 用两个栈分工实现顺序转换输入栈inStack仅负责接收新元素push操作元素入栈后栈顶是 “最新加入的元素”输出栈outStack仅负责提供待取出的元素pop/peek操作栈顶是 “最早加入的元素”倒栈时机当outStack为空时将inStack的所有元素依次弹出并压入outStack—— 此时inStack的 “栈底元素最早加入” 会变成outStack的 “栈顶元素最早取出”实现顺序反转。1.push(int x)将元素加入队列尾部直接将元素压入inStack输入栈负责接收新元素。示例push(1) → push(2) → push(3)inStack状态[1,2,3]栈顶是 3。2.pop()移除并返回队列头部元素先检查outStack是否为空若空将inStack的所有元素倒栈到outStack弹出outStack的栈顶元素即队列头部。示例执行pop()时outStack为空 → 把inStack的3、2、1依次弹出压入outStack→inStack空outStack状态[3,2,1]栈顶是 1→ 弹出 1队列头部。3.peek()返回队列头部元素逻辑与pop()一致但不弹出元素仅返回outStack的栈顶值。4.empty()判断队列是否为空当inStack和outStack都为空时队列才为空所有元素已被处理。// 定义栈的结构用数组模拟typedefstructStack{int*data;inttop;// 栈顶指针指向栈顶元素的下一个位置intcapacity;// 栈容量}Stack;// 初始化栈Stack*stackInit(intcapacity){Stack*s(Stack*)malloc(sizeof(Stack));s-data(int*)malloc(sizeof(int)*capacity);s-top0;s-capacitycapacity;returns;}// 压栈voidstackPush(Stack*s,intx){s-data[s-top]x;}// 弹栈返回栈顶元素intstackPop(Stack*s){returns-data[--s-top];}// 获取栈顶元素intstackPeek(Stack*s){returns-data[s-top-1];}// 判断栈是否为空boolstackEmpty(Stack*s){returns-top0;}// 定义队列结构包含两个栈typedefstruct{Stack*inStack;Stack*outStack;}MyQueue;// 初始化队列MyQueue*myQueueCreate(){MyQueue*q(MyQueue*)malloc(sizeof(MyQueue));q-inStackstackInit(100);// 假设最大容量100q-outStackstackInit(100);returnq;}// 倒栈将inStack的元素转移到outStackvoidtransfer(MyQueue*q){if(stackEmpty(q-outStack)){// 仅当outStack为空时倒栈while(!stackEmpty(q-inStack)){intvalstackPop(q-inStack);stackPush(q-outStack,val);}}}// push操作voidmyQueuePush(MyQueue*obj,intx){stackPush(obj-inStack,x);}// pop操作intmyQueuePop(MyQueue*obj){transfer(obj);returnstackPop(obj-outStack);}// peek操作intmyQueuePeek(MyQueue*obj){transfer(obj);returnstackPeek(obj-outStack);}// empty操作boolmyQueueEmpty(MyQueue*obj){returnstackEmpty(obj-inStack)stackEmpty(obj-outStack);}// 释放资源voidmyQueueFree(MyQueue*obj){free(obj-inStack-data);free(obj-inStack);free(obj-outStack-data);free(obj-outStack);free(obj);}因为每个元素最多被 “压栈 2 次、弹栈 2 次”一次在inStack一次在outStack因此每个操作的均摊时间复杂度为 O (1)。三、无重复字符的最长字串本题是滑动窗口、哈希表搭配的经典例题核心是通过双指针维护一个 “无重复字符的连续子串窗口”结合哈希 / 数组快速判断字符重复.初始化左指针left 0窗口左边界最大长度max_len 0记录最长无重复子串的长度哈希集合 / 数组container存储当前窗口内的字符。遍历右指针右指针right从 0 遍历到字符串末尾逐个处理每个字符s[right]若s[right]已在窗口内移动左指针left并从container中移除s[left]直到窗口内无s[right]将s[right]加入窗口把s[right]存入container更新最大长度计算当前窗口长度right - left 1若大于max_len则更新。intlengthOfLongestSubstring(char*s){intnstrlen(s);bool exist[128]{false};// 用数组代替哈希集合判断字符是否存在intleft0,max_len0;for(intright0;rightn;right){// 若当前字符已在窗口内移动左指针while(exist[s[right]]){exist[s[left]]false;left;}// 加入当前字符exist[s[right]]true;// 更新最大长度intlenright-left1;max_lenlenmax_len?len:max_len;}returnmax_len;}四、打家劫舍本题是典型的动态规划问题核心是通过 “状态转移” 决策 “偷 / 不偷当前房屋”由于相邻房屋不能同时偷因此对第i间房屋有两种选择偷第i间则第i-1间不能偷总金额 第i间金额 前i-2间的最大金额不偷第i间总金额 前i-1间的最大金额。1. 状态定义dp[i]表示偷前i1间房屋即下标0~i能得到的最大金额。2. 状态转移方程基于两种选择取最大值d p [ i ] max ⁡ ( d p [ i − 1 ] , d p [ i − 2 ] n u m s [ i ] ) dp[i] \max(dp[i-1],\ dp[i-2] nums[i])dp[i]max(dp[i−1],dp[i−2]nums[i])3. 边界条件若只有 1 间房屋i0dp[0] nums[0]只能偷这一间若有 2 间房屋i1dp[1] max(nums[0], nums[1])选金额大的那间。introb(int*nums,intnumsSize){if(numsSize0){return0;}if(numsSize1){returnnums[0];}intdp[numsSize];dp[0]nums[0];dp[1]nums[0]nums[1]?nums[0]:nums[1];for(inti2;inumsSize;i){dp[i]dp[i-1](dp[i-2]nums[i])?dp[i-1]:(dp[i-2]nums[i]);}returndp[numsSize-1];}五、合并K个升序链表“合并 K 个升序链表” 的核心其实还是基于“合并两个升序链表”通过归并法扩展到 K 个链表合并两个升序链表用递归 / 迭代法比较两个链表的头节点取较小的节点再递归 / 迭代合并剩余部分。递归structListNode*mergeTwoLists(ListNode*l1,ListNode*l2){if(l1NULL){returnl2;}if(l2NULL){returnl1;}if(l1-vall2-val){l1-nextmergeTwoLists(l1-next,l2);returnl1;}else{l2-nextmergeTwoLists(l2-next,l1);returnl2;}}迭代ListNode*mergeTwolists(ListNode*l1,ListNode*l2){ListNode*dummy(ListNode*)malloc(sizeof(ListNode));ListNode*curdummy;while(l1!NULLl2!NULL){if(l1-vall2-val){cur-nextl2;curl2;l2l2-next;}else{cur-nextl1;curl1;l1l1-next;}}cur-next(l1!NULL)?l1:l2;returndummy-next;}归并核心思路分而治之将 K 个链表的合并问题拆解为多个 “合并两个链表” 的子问题拆分将链表数组分成左右两部分递归合并左半部分和右半部分得到两个有序链表合并将这两个有序链表合并得到最终结果。typedefstructListNodeListNode;structListNode*mergeTwoLists(ListNode*l1,ListNode*l2){if(l1NULL){returnl2;}if(l2NULL){returnl1;}if(l1-vall2-val){l1-nextmergeTwoLists(l1-next,l2);returnl1;}else{l2-nextmergeTwoLists(l2-next,l1);returnl2;}}structListNode*mergeKLists(ListNode**lists,intlistsSize){// 终止条件if(listsSize0){returnNULL;}if(listsSize1){returnlists[0];}// 拆分intmidlistsSize/2;ListNode*leftmergeKLists(lists,mid);ListNode*rightmergeKLists(listsmid,listsSize-mid);// 合并左右结果returnmergeTwoLists(left,right);}