算法工程师，一个听起来非常高大上的职业~ 不但轻轻松松月入过万，算法知识更是进入大厂必考的题目。
如何通过大厂算法岗面试？
如何轻轻松松拿到高薪？
如何成为算法技术大牛？
... ...
今天开发者社区就来为小伙伴们送福利啦！10+大厂面试必看的算法模拟题精解合辑送上，每天一个算法小知识，轻松备战大厂面试！
1、找出二叉搜索树的第2大的数
给定一个二叉搜索树，找出其第二大的数。
示例1
比如二叉搜索树如下
那么第二大的值是25。
解题过程： 这是一个关于二叉搜索树的知识点。
对于二叉搜索树，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
因为题中没有说这是一棵平衡的树，所以某些节点可能只有一棵子树。
对于树中最大的数是很容易找到的，一直选择右子树直到右子树为空就可以了。
对于第2大的数，存在两种情况。一种是最大数的节点存在左子树，一种是不存在左子树。查看更多>>
2、打怪兽
现在有3只怪兽，他们的都有自己的血量a,b,c(1<=a,b,c<=100)，当Tom打死第一怪兽的时候花费的代价为0，其余的怪兽的代价为当前的怪兽的血量减去上一个怪兽的血量的绝对值。问Tom打死这些怪兽所需要的最小代价?
解题过程： 根据题意，本题使用贪心算法完成，策略是每次打怪兽都选择代价最小的一只。
由于第一次打怪兽的花费为0，所以第一次可以打血量最小的（最大的也可以），接下来每次选择怪兽的时候就可以选择花费代价最小的。由于每次打怪兽的代价都是：当前怪兽的血量和上一个怪兽的血量的差的绝对值。于是可以得出结论，最小代价为所有怪兽血量的最大值减最小值。查看更多>>
3、超级区间
Tom现在有一个长度为n的数组，Jerry给Tom定义了一种超级区间，如果区间[l,r]满足(a[l]+…+a[r])>=k,则区间[l,r]被称为超级区间，现在Jerry想让Tom告诉他数组中有多少个超级区间？
解题过程： 使用 尺取法 对搜索空间进行遍历。
设当前区间为[L, R]。初始L = R = 0；使用尺取法需要判断什么时候调整L和R。
数组中的所有数都为正数。
情况1：假设对于某个区间[L1, R1]满足超级区间的定义。因为所有数都为正数，所以保持L1不变，依次增加R1直到n为止的所有区间都满足超级区间的定义。
情况2：假设对于某个区间[L2，R2]不满足超级区间的定义。则需要保持L2不动，增加R2才可能满足超级区间的定义。
情况3：是情况2拓展。如果[L2，n]不满足超级区间的定义，则任何i>L2，区间[i, n]都不满足超级区间的定义。查看更多>>
4、变换的密钥
Tom最开始有一个密钥s1，s1是长度为n的由小写字母组成的字符串。Jerry也有一个长度为n的由小写字母组成的密钥s2。
现在有m组关系，每组关系由两个数字[u,v]构成(1<=u,v<=26)，表示26个字母表中的第u个小写字母可以直接转换为第v个小写字母。
假设u=1，v=2,那么说明字母'a'可以直接转换为字母'b'。现在Tom对于s1的每个字母使用无数次转换，请判断s1能否转换为s2。
解题过程： 根据题意，只要根据给出的初始关系，计算出对于每个字母可以变成的字母，就可以直接判断s1能不能转化成s2了。
例如样例中计算过后：
a -> a,c,d
b -> b,c
c -> a,c,d
d -> d对于这个结果，可以使用一个26*26的二维数组change来保存。每一行表示原始字母，每一列表示可以变换成的字母。1表示可以变化，0表示不能变换。查看更多>>
5、能量半径
codancer来到了一个能量平面上的中心，坐标为(0,0)，接下来巫师Tom会在q个坐标上放置能量点，每个能量点的能量值为1，为了打败哥斯拉，他需要至少k点的能量，因此他想确定一个最小的整数半径r使得codancer能够从这个圆心为(0,0)，半径为r的圆形区域内得到至少k个能量值，请你帮他确定最小的整数半径r？
解题过程： 题目的含义就是找到距离原点最近的第k个点，并求它的半径。
计算每个点到原点的距离，为了减少计算量可以只计算到平方。使用long[n]这样的数组来保存。使用long类型是为了防止平方之后结果超出int类型范围。
对距离进行从小到大排序；取排序后的第k个数值开根号，转化为int类型并加1。加1是因为开根号后可能为小数，转化成int类型会直接舍去小数部分，导致结果比实际小一些。查看更多>>
6、全奇数组
codancer现在有n个正整数a[1],a[2]…a[n]，Tom告诉codancer他可以进行下列操作，选择某个偶数x，把这n个数中全部等于x的数字除2，Tom想知道把这n个数字全部变成奇数最少需要几次这样的操作？
解题过程： 从题意及示例可以知道，应该从大到小进行操作。当除2后，需要快速查找是否有相等的其他数，这个需求可以使用HashSet代替。
因此，先将n个中的偶数入HashSet，再对HashSet中元素从大到小排序，依次遍历；
每个元素除2后从HashSet查找，存在则移除，计数+1，直到该数变成奇数。
最坏情况下，除2过程没有重复数字。查看更多>>
7、移动射击
你正在数轴上跟小精灵对战。你拥有一个十分强力的技能称为移动射击，但是这个技能有一个缺点是在你发动之后只能改变一次方向。
你可以认为你的位置在数字0的位置上，在数轴的正方向上有n只精灵，负方向上有m只精灵。移动射击可以造成w点伤害。每个精灵都有自己的血量，当血量降为0时死亡。
在最开始时你可以选择向正方向或负方向释放移动射击，并且可以在任意时刻改变技能的方向。请问你最多可以击杀多少只小精灵?(n，m，w以及精灵的血量均在[1, 100000]范围内)
解题过程： 首先理解题意，题目说的“发动之后只能改变一次方向”是干扰你的，因为即使你在中间过程中左右摆，但宏观上还是最多改变了一次方向。
如果说：我先杀左边一个，然后转头杀右边一个，再转头杀左边三个，又回头杀右边1个，看起来是不是改变了三次方向，其实呢，相当于我先杀左边四个，再回头杀右边两个，效果是一样的。因为你想这个问题的时候，可以忽略这个限制。查看更多>>
8、数组变换
给出一个长度为 n 的数组，和一个正整数 d。
你每次可以选择其中任意一个元素 a[i] 将其变为 a[i] + d 或 a[i] - d，这算作一次操作。
你需要将所有的元素全部变成相等元素，如果有解，请输出最小操作次数，如果无解请输出-1。
解题过程： 首先判断无解的情况，可以发现 a[i]，a[i]+d, a[i]-d 在 模d情况下的余数不会发生改变，因此如果原数组中的存在任意两个数字它们对d取余结果不同，那么此时无解。
设余数为r。判断完无解之后，需要求出最小值。
先将数组a[i]排序，然后除以d，得到从r变成a[i]需要的步数。
枚举元素a[i]，将所有元素全部变成a[i]需要考虑两部分，i之前和i之后:对于i之前的元素，假设都是r，那么需要 (i-1)*a[i]，但是因为并不都是0，所有我们可以用一个变量val存放前i-1项的和，然后我们在减去val就是前i-1个元素真正需要操作的步数。查看更多>>
9、树的拆分
给你一个有n个节点的树,节点标号1-n。每个节点有一个权值w[i]，一棵树的价值为树上所有不同的权值的数量。
现在你可以删除一条边，问删除一条边后形成的两棵新树的价值之和最大为多少？
解题过程： 如果我们删除了一条边，那么一定将其分成了两棵树，其中一棵树一定为原树的子树，那么我们就可以利用DFS序将树遍历一遍得出每个点的时间戳。
DFS序即为每个点的在一次DFS中的遍历顺序，从定义可以知道，子树上的每个节点的DFS序一定连续，因此我们可以求出每棵子树所对应的区间，剩下的节点即为另一棵树。
此时我们就可以利用树状数组求每个区间里面不同的数的个数，由于一个子树区间可能会在数组中间，会将剩下的数字分为左右两部分，因此我们需要将原权值数组扩充一倍，然后进行计算。
需要注意的是，现在这个权值数组不是输入的权值数组，而是根据DFS序进行重新排序的数组。查看更多>>
10、Codancer的炸弹引爆
Codancer终于抵达了恶龙的城堡。现在他在城堡周围摆放了n枚电力炸弹，每个电力炸弹有两种属性m和p，只有已经引爆了m枚电力炸弹或者Codancer直接花费p的电力，第i枚炸弹才会被引爆，现在Codancer想使用最少的电力引爆所有的炸弹，请计算最少需要多少电力？
解题过程： 花费8电力引爆第3枚炸弹，那么第1枚就会被自动引爆，那么第2枚也会被自动引爆。
这种方案的花费是最小的。查看更多>>
11、Codancer的旅行
期末考试终于结束啦，Codancer开始了他的旅行，现在整个地图上由n个城市，这些城市之间有n-1条道路相连，每条道路都有一个距离，并且保证整个图是连通的，即这个地图可以看作是一棵树，现在假设Codancer要从城市A到城市B，那么他的路费就是从A-B的路径上边权最大的边的权值wmaxx元。现在Codancer有k元，他想知道他能选择那些(A,B)并且A<B使得codancer能够到达。
解题过程： 根据样例数据 从1到2的花费为1，从1到3的花费为2，从2到3的花费为1，花费都小于3，因此总共有三种方案。
首先按照边权将这些边从小到大排序，使用并查集记录当前连通块内的最大的边权。
当u和v连接起来的时候，假设此时的联通块大小为cnt,则答案应该加上cnt*(cnt-1)/2，同时应该减去之前u和v单独为连通块的方案数。
令ans[i]为最大边权为第i条时构成的连通块的方案数，那么对于k，二分查找最大的小于等于k的下标id，最终答案就是ans[id]。查看更多>>
热门活动
备战大厂每日挑战算法，坚持打卡更有社区定制周边奖品等你赢！
算法编程题目精解征文开始啦！快来Show出你的最优思路
更多资源
阿里面试官分享+真实面经+笔试模拟题，面试充电，就看这篇
面试一点通，帮你拿下好工作！
