在广州黑马程序员学习完后，我收集了以下的面试总结，以方便一个星期后的面试。
一. 算法 • （一）经典的算法： • 1.递归算法： • 1）数据定义按递归定 义 fibonacci • 2）问题揭发按递归解 决 回溯算法 • 3）数据结构按递归定 义 树遍历图搜索 • 经典题-整数划分：
（一）经典的算法： • 2.分治算法： • 对于规模为n的问题分解成k个规模小的问题他们彼此独立，然后再将 它们合并 • 分治策略的算法设计模式 •Divide_and_Conquer（P） • { •if (|P|＜＝n0 ) return adhoc§； •divide P into smaller substances P1，P2，…，Pk； • for (i＝1; i＜＝k; k＋＋) •yi＝Divide-and-Conquer（Pi） //递归解决Pi •Return merge（y1，y2，…，yk） //合并子问题 • }
• 二分搜索： •Public static int binarysearch(int[]data,intbeginindex,intendindex) •Int beginindex=0;int endindex =n-1; •While(beginindex<endindex) •{ int mid =(beginindex+endindex)/2 •If(x==a[mid] return mid; •If(x>a[mid] beginindex=mid+1; •Else endindex=mid-1;} •Return -1 • a[0:n-1] 找出 • 第k小的元素 • 快速排序算法 • 是分治算法的应 • 1.分析最优子结构： • 2.重叠子问题； • 题-最长公共子序列：
• 题-最大子段和： • B[j]=max{b[j-1]+a[j],a[j]}//条件b[i-j]>0 int MaxSum(int n) [AppleScript] 纯文本查看 复制代码 • 题0-1背包问题： • 第一个式子是不装入物品i，也可能物品i无 法装入，背包的容量不变，转化为前i+1个 物品放与容量为j的背包中 • 第二个式子装入物品i则新增加价值vi，但容 量变位j-w，对于最后一个物品n，若j》=w p(i，j) max( p(i 1，j)，p(i 1，j wi ) vi } j wi p(i 1，j) 0 j wi • 题：最长单调子系列 • 辅助数组b表示以a为结尾的最长递增子 序列长度，则序列L的最长递增子序列的长 度：max {b} • B[1]=1; • B=max{b[k]}+1 int LIS_n2(int n) //教材上这一句丢掉了 { int b[NUM]={0}; //辅助数组b int i,j; b[1] = 1; int max = 0; //数组b的最大值 for (i=2;i<=n; i++) { int k = 0; for (j=1; j<i; j++) //0~i-1之间，b的最大值 if (a[j]<=a && k<b[j]) k=b[j]; b = k+1; if (max<b) max=b; } return max; } • 贪心选择性质是指所求问题的整体最优解可以通 过一系列局部最优的选择，即贪心选择来达到 Greedy(A) { S={ }; //初始解集合为空集 while (not solution(S)) //集合S没有构成问题的一个解 { x = select(A); //在候选集合A中做贪心选择 if feasible(S, x) //判断集合S中加入x后的解是否 可行 S = S+{x}; A = A-{x}; } return S; ｝ （一）经典的算法：贪心算法背包 问题 double knapsack(int n, bag a[], double c) { double cleft = c; int i = 0; double b = 0; while(i<n && a.w<=cleft) { cleft -= a.w; b += a.v; //物品原先的序号是a.index，全部装入背包 a[a.index].x = 1.0; i++; } if (i<n) { a[a.index].x = 1.0cleft/a.w; b += a[a.index].xa.v; } return b; } • 令cw(i)表示目前搜索到第i层已经装入背包的 物品总重量，即部分解(x1, x2 , …, xi)的重量： i cw(i) x j wj j1 • 对于左子树， xi =1 ，其约束函数为： constraint (i) cw(i 1) wi • 若constraint(i)＞W，则停止搜索左子树，否 则继续搜索。 • 对于右子树，为了提高搜索效率，采用上界函数 Bound(i)剪枝。 • 令cv(i)表示目前到第i层结点已经装入背包的物品 价值：cv(i) x jv j j1
r(i)
n v j ji1 • 令r(i)表示剩余物品的总价值： Bound (i)
cv(i)
r(i) • 则限界函数Bound(i)为： #define NUM 100 int c; //背包的容量 int n; //物品的数量 int cw; //当前重量 int cv; //当前价值 int bestv; //当前最优价值 //描述每个物品的数据结构 struct Object{ int w; //物品的重量 int v; //物品的价值 double d; //物品的单位重量价值比 //物品的数组
void backtrack(int i) { //到达叶子结点时，更新最优值 if (i+1>n) {bestv = cv; return;} //进入左子树搜索 if (cw+Q.w<=c) { cw += Q.w; cv += Q.v; backtrack(i+1); cw -= Q.w; cv -= Q.v; } //进入右子树搜索 if (Bound(i+1)>bestv) backtrack(i+1);
int cleft = c-cw; //背包剩余的容量 int b = cv; //上界 //尽量装满背包 while (i<n && Q.w<=cleft) { cleft -= Q.w; b += Q.v; i++; } //剩余的部分空间也装满 if (i<n) b += 1.0cleftQ.v/Q.w; return b; } • 从活结点表中选择下一个活结点作为新的扩展 结点，分支限界算法通常可以分为两种形式： 1.FIFO（First In First Out）分支限界算法 –按照先进先出（FIFO）原则选择下一个活结点作为 扩展结点，即从活结点表中取出结点的顺序与加入结 点的顺序相同。 2.最小耗费或最大收益分支限界算法 –在这种情况下，每个结点都有一个耗费或收益。 –根据问题的需要，可能是要查找一个具有最小耗费 的解，或者是查找一个具有最大收益的解。 • 限界函数： • 求max维护或节点，从活节点选择一个节点 作为扩展节点，对扩展节点的每个分支i， 计算其上界值，若当前最大的目标函数值 best不小于bound（i）不会放入活节点，否 则放入，所以若bound（i）《=best表示正 在搜索的节点i为死节点减掉 • 深度优先 • 广度优先 无回溯快
想要更多免费资源可以到黑马程序员广州中心公众号寻找。
