考核算法题纠错-编程实验室

考核题算法题纠错

打家劫舍

introb(int*nums,intnumsSize){if(numsSize==0)return0;if(numsSize==1)returnnums[0];intprev_prev=nums[0];intprev=nums[0]>nums[1]?nums[0]:nums[1];for(inti=2;i<numsSize;++i){intcurrent=prev>(prev_prev+nums[i])?prev:(prev_prev+nums[i]);prev_prev=prev;prev=current;}returnprev;}

本题主要用的是动态规划
逻辑：偷第 i 间房：不能偷第 i-1 间，总金额 = 第 i 间金额 + 前 i-2 间的最大金额
不偷第 i 间房：总金额 = 前 i-1 间的最大金额
取两者最大值，即为前 i 间房的最大金额
步骤一：定义两个变量prev_prev为前i-2间房的最大金额，prev为前i-1间房的的最大金额
步骤二：状态转移方程：
遍历到第 i 间房时，当前最大金额：current = max(不偷当前房：prev, 偷当前房：prev_prev + nums[i])
步骤三：初始化：
无房屋（numsSize=0）：返回 0
仅 1 间房屋（numsSize=1）：返回 nums[0]
仅 2 间房屋（numsSize=2）：返回 max(nums[0], nums[1])（初始化 prev_prev 和 prev）
步骤四:迭代计算：
从第 3 间房（i=2）开始遍历，每轮计算后更prev_prev 和 prev：
prev_prev = 原来的prev（旧的 i-1 变为新的 i-2
prev = current（当前 i 的最优解变为新的 i-1）
遍历结束后，prev 即为所有房屋的最大金额。

合并k个升序链表

structListNode*mergeTwoLists(structListNode*l1,structListNode*l2){if(l1==NULL)returnl2;if(l2==NULL)returnl1;structListNodedummy;structListNode*tail=&dummy;while(l1!=NULL&&l2!=NULL){if(l1->val<l2->val){tail->next=l1;l1=l1->next;}else{tail->next=l2;l2=l2->next;}tail=tail->next;}tail->next=(l1!=NULL)?l1:l2;returndummy.next;}structListNode*merge(structListNode**lists,intleft,intright){if(left>right)returnNULL;if(left==right)returnlists[left];intmid=left+(right-left)/2;structListNode*leftMerge=merge(lists,left,mid);structListNode*rightMerge=merge(lists,mid+1,right);returnmergeTwoLists(leftMerge,rightMerge);}structListNode*mergeKLists(structListNode**lists,intlistsSize){if(listsSize==0)returnNULL;returnmerge(lists,0,listsSize-1);}

逻辑：

拆分：将k个链表的数组从中间分成左右两部分，递归合并成左半部分和右半部分
合并：递归的终止条件是拆分到只剩0/1个链表（直接返回），或2个链表

关键步骤：

辅助函数：mergeTwoLists（合并两个升序链表）
作用：负责合并两个有序链表；
逻辑：用虚拟头节点 dummy 遍历两个链表，每次取较小的节点接入结果，最后拼接剩余节点。
递归核心：merge 函数
lists 是链表数组，left/right 是当前处理的数组区间
终止条件：left > right：空区间，返回 NULL；
left == right：区间内只有 1 个链表，直接返回该链表
递归：计算中间点 mid，将区间拆分为 [left, mid] 和 [mid+1, right]，分别递归合并
向上合并：将左右两个子区间合并的结果，再调用 mergeTwoLists 合并为一个链表
主函数：mergeKLists
处理边界（空数组）后，调用 merge 函数，初始区间是 [0, listsSize-1]（整个数组）。

二叉树的前序遍历

int*preorderTraversal(structTreeNode*root,int*returnSize){if(root==NULL){*returnSize=0;returnNULL;}structTreeNode*stack[10000];intstackTop=0;stack[stackTop++]=root;int*result=(int*)malloc(sizeof(int)*10000);intidx=0;while(stackTop>0){structTreeNode*curr=stack[--stackTop];result[idx++]=curr->val;if(curr->right!=NULL){stack[stackTop++]=curr->right;}if(curr->left!=NULL){stack[stackTop++]=curr->left;}}*returnSize=idx;returnresult;}