黑马程序员技术交流社区

标题: 100家IT名企面试总结------Java篇 [打印本页]

作者: 播妞 时间: 2017-9-21 13:34
标题: 100家IT名企面试总结------Java篇
一. 算法
•       （一）经典的算法：
•       1.递归算法：
•       1）数据定义按递归定义 fibonacci
•       2）问题揭发按递归解决回溯算法
•       3）数据结构按递归定义树遍历图搜索
•       经典题-整数划分：

（一）经典的算法：
•       2.分治算法：
•       对于规模为n的问题分解成k个规模小的问题他们彼此独立，然后再将它们合并
•       分治策略的算法设计模式
•Divide_and_Conquer（P）
•       {
•if (|P|＜＝n0 ) return adhoc(P)；
•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] 纯文本查看 复制代码

{

int sum=0; int b=0;

for (int i=1;i<=n;i++)

{

if (b>0) b+=a; else b=a; if (b>sum) sum=b;

}

return sum;

int MaxSum(int n, int &besti, int &bestj)

{

int sum=0; int b=0;

int begin = 0;

for (int i=1;        i<=n;        i++)

{

if (b>0)        b+=a;

else {b=a;        begin = i;}

if (b>sum) //得到新的最优值时，更新最优解

{

sum = b; besti = begin; bestj = i;

}

}

return sum;

}

•       题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.0*cleft/a.w;
b += a[a.index].x*a.v;
}
return b;
}
•       令cw(i)表示目前搜索到第i层已经装入背包的物品总重量，即部分解(x1, x2 , …, xi)的重量：
i
cw(i)   x j wj
j1
•       对于左子树， xi =1 ，其约束函数为：
constraint (i)  cw(i  1)  wi
•       若constraint(i)＞W，则停止搜索左子树，否
则继续搜索。
•       对于右子树，为了提高搜索效率，采用上界函数
Bound(i)剪枝。
•       令cv(i)表示目前到第i层结点已经装入背包的物品
价值：cv(i)   x jv j
j1

r(i) 

n
v j
ji1
•       令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.0*cleft*Q.v/Q.w; return b;
}
•       从活结点表中选择下一个活结点作为新的扩展结点，分支限界算法通常可以分为两种形式：
1.FIFO（First In First Out）分支限界算法
–按照先进先出（FIFO）原则选择下一个活结点作为扩展结点，即从活结点表中取出结点的顺序与加入结点的顺序相同。
2.最小耗费或最大收益分支限界算法
–在这种情况下，每个结点都有一个耗费或收益。
–根据问题的需要，可能是要查找一个具有最小耗费的解，或者是查找一个具有最大收益的解。
•       限界函数：
•       求max维护或节点，从活节点选择一个节点作为扩展节点，对扩展节点的每个分支i，计算其上界值，若当前最大的目标函数值 best不小于bound（i）不会放入活节点，否则放入，所以若bound（i）《=best表示正在搜索的节点i为死节点减掉
•       深度优先
•       广度优先无回溯快

温馨提醒，文本格式略有错乱，建议大家回帖下载PDF版本，回帖即可下载附件，赶紧下载学习吧~

作者: battlexing 时间: 2017-9-21 13:38
mark,mark,谢谢播妞

作者: YuanMxy 时间: 2017-9-22 18:41
好好学习天天向上

作者: 18732697514 时间: 2017-9-22 20:30
求面试题

作者: 乌龟 时间: 2017-9-22 20:53
楼主好人

作者: Cxxian❤ 时间: 2017-9-22 23:42
好东西要分享

作者: Yin灬Yan 时间: 2017-9-22 23:59
吼哈我来拿pdf

作者: IceLoveInFire丶 时间: 2017-9-23 00:02
现在面试算法啥也不会了-_-||

作者: uuiop 时间: 2017-9-23 11:42
休息休息休息休息休息休息下

作者: qiuyuexin 时间: 2017-9-23 12:00
asdfasdasdfasd

作者: ThinkingOutLoud 时间: 2017-9-23 17:25
THANK YOU FENGXIANG

作者: 梦编之程 时间: 2017-9-23 21:10
谢谢谢谢

作者: 忆流年ZhBy 时间: 2017-9-23 23:02
求下载求题

作者: 忆流年ZhBy 时间: 2017-9-23 23:03
谢谢谢谢侬

作者: xgwhsgws 时间: 2017-9-24 10:23
很有用，值得学习，感谢楼主分享

作者: pagemyron 时间: 2017-9-24 16:26
666666666

作者: 空城灬 时间: 2017-9-24 16:31
求资源求资源求资源

作者: 旧梦空城灬 时间: 2017-9-24 16:36
资源免费就好了

作者: 15059320049 时间: 2017-9-24 19:27
好东西啊啊啊啊啊

作者: Elroy 时间: 2017-9-24 20:57
下载下来看看，感谢

作者: 我认识你 时间: 2017-9-24 22:54
顶一个！！

作者: FamilyGlory 时间: 2017-9-24 23:29
66666666666666666666666

作者: liub 时间: 2017-9-25 09:59
KANKAN1111

作者: su36306 时间: 2017-9-25 20:23
666666666666666666666666666666666666666666666666

作者: tavis 时间: 2017-9-26 08:33
谢谢还不错

作者: 黑马278 时间: 2017-9-26 23:21
学习学习

作者: 午夜幽灵 时间: 2017-9-27 08:49
{:8_468:}哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈

作者: 李伟锋 时间: 2017-9-27 14:58
总结技术中的精髓啊

作者: ywygg 时间: 2017-9-27 23:31
100家IT名企面试总结--

作者: niuheng 时间: 2017-9-28 12:36
ty eheheertrhertr

作者: 会哭的纸飞机 时间: 2017-9-28 13:35
谢谢谢谢我来拿PDF

作者: 953900576 时间: 2017-9-28 15:38
谢谢楼主分享

作者: bnjsj 时间: 2017-9-28 17:04
看看看个完整的资料

作者: sennn 时间: 2017-9-28 22:28
6666666666666666666

作者: 0..0 时间: 2017-9-29 06:56
mark,mark,谢谢播妞

作者: 你94太年轻 时间: 2017-9-29 16:34
真的太感谢楼主了，谢谢你

作者: longskyer 时间: 2017-9-29 16:55
资料资料资料资料资料资料资料

作者: 江枫渔火 时间: 2017-9-29 20:29
好好学习拿offer

作者: sgssd 时间: 2017-9-30 07:47
提示: 作者被禁止或删除内容自动屏蔽

作者: haosun33 时间: 2017-9-30 12:59
非常感谢

作者: fashionkillyou 时间: 2017-9-30 14:26
pdf收割

作者: Studio1 时间: 2017-9-30 16:00
回帖

作者: 东方飒 时间: 2017-10-1 17:26
mark,mark,谢谢谢谢

作者: Hello_cc 时间: 2017-10-2 10:01

好好学习天天向上

作者: jackshen 时间: 2017-10-2 16:15
这是好东西

作者: hpu145 时间: 2017-10-4 22:50
88888888888

作者: 随遇而安666 时间: 2017-10-5 00:53
我要回复

作者: ycy1992911 时间: 2017-10-5 18:33
好好学习天天向上

作者: ycy1992911 时间: 2017-10-5 18:34
好好学习天天向上

作者: ycy1992911 时间: 2017-10-5 18:35
好好学习天天向上

作者: ycy1992911 时间: 2017-10-5 18:36
天天向上好好学习

作者: 枝间 时间: 2017-10-5 22:51
谢谢求求给下载

作者: king大秦 时间: 2017-10-6 09:47
好好学习天天向上感谢楼主

作者: lonely1314 时间: 2017-10-6 15:11
给力
给力给力给力给力给力给力

作者: MoonZero 时间: 2017-10-6 23:24

作者: rememple 时间: 2017-10-6 23:46

谢谢分享！！

作者: lijingwh 时间: 2017-10-7 01:14
谁禁言个

作者: uc001 时间: 2017-10-7 02:20

作者: 探险者 时间: 2017-10-7 09:41
感谢分享

作者: 踏歌 时间: 2017-10-7 20:46
膜拜膜拜

作者: Ruin 时间: 2017-10-9 00:02
100家IT名企面试总结------Java篇

作者: hinzzz 时间: 2017-10-9 16:01
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq

作者: 夜貓1994 时间: 2017-10-9 18:02
999999999999999999999

作者: 夜貓1994 时间: 2017-10-9 18:04

8888888888888

作者: 夜貓1994 时间: 2017-10-9 18:05
777777777777777

作者: 小周周 时间: 2017-10-9 23:09

作者: xinfei.liu 时间: 2017-10-11 00:18
赞赞赞赞赞赞赞

作者: 小杨师兄 时间: 2017-10-11 15:28
good study，dayday up

作者: 小杨师兄 时间: 2017-10-11 16:06
666666666666

作者: alan.yin 时间: 2017-10-12 08:44
谢谢，播妞

作者: vocter 时间: 2017-10-12 12:57
给发高热啊过热

作者: 随风521 时间: 2017-10-12 13:19
ok我们知道了

作者: 15830739980 时间: 2017-10-13 19:34
课程健康监测解析成南石道街给你时间

作者: longwang2008 时间: 2017-10-13 21:56
jkloqijdahklg

作者: 雷攀博 时间: 2017-10-14 08:57
可爱的播妞，下载，下载，马上回来！~

作者: 新新凯 时间: 2017-10-14 09:24
厉害，我要好好学习java了

作者: 小黑子学IT 时间: 2017-10-14 21:07
好好学习

作者: 午托饭 时间: 2017-10-15 12:02
分享给我吧

作者: lindy 时间: 2017-10-15 12:08

作者: lindy 时间: 2017-10-15 12:09
求面试题目

作者: lindy 时间: 2017-10-15 12:10
求面试题目哈哈哈哈真的是，没有黑币了怎么办

作者: 午托饭 时间: 2017-10-15 12:22
我来拿面试题的

作者: 午托饭 时间: 2017-10-15 12:23

Elroy 发表于 2017-9-24 20:57
下载下来看看，感谢

没法下载

作者: ygg1124491042 时间: 2017-10-15 23:11
感谢楼主分享资源三

作者: masf 时间: 2017-10-16 09:04
赞。。。。学习学习

作者: 最伟大的 时间: 2017-10-16 11:37
好好学习天天向上

作者: yinman 时间: 2017-10-17 10:09
很不错啊

作者: 技术男 时间: 2017-10-17 10:31
双击66666

作者: HAHAA 时间: 2017-10-17 11:12
嘻嘻嘻嘻嘻

作者: 丶偏执 时间: 2017-10-17 11:26
1111111111111111111111111111

作者: 石头.... 时间: 2017-10-17 15:56
好东西，给力

作者: 天道轮回 时间: 2017-10-17 16:04
来看看看那

作者: chenxuyu 时间: 2017-10-17 17:18
感谢楼主分享。。。

作者: 日日月月曰 时间: 2017-10-17 20:00
不错不错

作者: 摩羯编写人生 时间: 2017-10-18 11:32
好人一生平胸！！！

作者: heimazombie 时间: 2017-10-18 19:03
好好学习天天向上

作者: _不见不思念 时间: 2017-10-18 20:32
很好谢谢

作者: 去年买百达 时间: 2017-10-18 21:20
谢谢啦，学习了

作者: 15989276724 时间: 2017-10-18 21:33
不错哈,谢谢分享.

作者: yanbo 时间: 2017-10-18 22:07
fdghfghdfghfdghtytry

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2