求二叉树中节点的最大距离
情况A: 路径经过左子树的最深节点,通过根节点,再到右子树的最深节点。
方案:计算两个节点到根节点的深度相加。
情况B: 路径不穿过根节点,而是左子树或右子树的最大距离路径,取其大者。
方案:计算两个节点到子树根节点的深度相加
fibonacci数列的动态规划算法?
分配饼干问题?每个孩子都有一个满足度,每个饼干都有一个大小,只有饼干的大小大于一个孩子的满足度,该孩子才会获得满足。求解最多可以获得满足的孩子数量。Input:[1,2], [1,2,3]。Output: 2
贪心算法。对饼干、孩子满足度进行排序。然后先用小饼干给满足度低的孩子。不造成浪费。
如何计算二叉树的深度
public static int treeDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 计算左子树的深度
int left = treeDepth(root.left);
// 计算右子树的深度
int right = treeDepth(root.right);
// 树root的深度=路径最长的子树深度 + 1
return left >= right ? (left + 1) : (right + 1);
}
如何打印二叉树每层的节点?
- 借助一个队列,先把根节点入队,每打印一个节点的值时,也就是打印队列头的节点时,
- 都会把它的的左右孩子入队,并且把该节点出队。直到队列为空。
二叉树的Z型遍历?
借助一个队列和一个栈,方法和打印层遍历类似,区别在于隔层利用栈来逆序遍历。
反转单链表?
- 可以利用栈逆序拼接。
- 利用三个指针引用,一次性遍历反转,在每次反转两个节点的时候,都需要保存下一个节点,以免丢失原链表。
随机链表的复制?
复制成 1->1′->2->2′->3->3′ 的链表,然后再拆分出来 1′->2′->3′
链表-奇数位升序偶数位降序-让链表变成升序
第一种做法:先将链表拆分成奇数的链表,和偶数的链表,然后翻转偶数的链表,在合并两个链表。
bucket如果用链表存储,它的缺点是什么?
不支持随机访问,查找的时间复杂度是O(n)
如何判断链表检测环?
准备两个指针,一个步长为1,一个步长为2,当遍历到的指针相同时,则判定出现环
寻找一数组中前K个最大的数?
最小堆算法
求一个数组中连续子向量的最大和
遍历数组,从第一个大于0的数字开始累加,保存最大值,如果累加后的值小于等于0的话,就抛这一下标,
从下一个下标开始累积,如果超过之前的最大值的话就进行替换。使用sum和max变量进行操作
找出数组中和为S的一对组合。
将所有数字放入数字对应下标的数组,有N个相同的数字,该下标的值就为N。
从i下标开始遍历,S-i下标对应值>0的话,就找到组合。 i=s-i的话,做特殊处理。
一个数组,除一个元素外其它都是两两相等,求那个元素?
所有值进行异或运算。最后的值再和0异或,得到原来的值。
将一个二维数组顺时针旋转90度,说一下思路。
先找出旋转90度,下标的变换规律。 然后从外圈向内圈旋转变换。
各类排序算法总结?
排序算法 | 时间复杂度 |
---|---|
冒泡排序 | O(n2) |
选择排序 | O(n2) |
插入排序 | O(n2) |
希尔排序 | O(n1.5) |
快速排序 | O(N*logN) |
归并排序 | O(N*logN) |
堆排序 | O(N*logN) |
基数排序 | O(d(n+r)) |
快排的原理是什么?
基本思想:(分治)
- 先从数列中取出一个数作为key值;
- 将比这个数小的数全部放在它的左边,大于或等于它的数全部放在它的右边;
- 对左右两个小数列重复第二步,直至各区间只有1个数。
堆排序的原理是什么?
- 利用数组建立一个大根堆(父亲比孩子的值大);
- 把堆顶元素和堆尾元素互换;
- 把堆(无序区)的尺寸缩小1,并调用siftDown(arr, 0,len-1)从新的堆顶元素开始进行堆调整;
- 重复步骤,直到堆的大小为1;
归并排序的原理?
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
首先考虑下如何将2个有序数列合并。这个非常简单,只要从比较2个数列的第一个数,谁小就先取谁,
取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。
找出数据流的中位数?
- 插入排序,然后找到中间位置。
-
借鉴快排的思想,随机取一个数,大于它的排左边,小于它的排右边。检测所选数字是否位于数组中间。
是的话就返回,不是的话,小于数组中间位置就对右边递归,大于数组中间位置就对左边递归。
堆和栈的区别?
- 堆可以被看成是一棵完全二叉树树,如:堆排序。
- 一种先进后出的数据结构。
Java优先级队列?
PriorityQueue是一个基于优先级堆的无界队列,它的元素是按照自然顺序(natural order)排序的。
在创建的时候,我们可以给它提供一个负责给元素排序的比较器。PriorityQueue不允许null值,因为
他们没有自然顺序,或者说他们没有任何的相关联的比较器。最后,PriorityQueue不是线程安全的,
入队和出队的时间复杂度是O(log(n))。
为什么要设计后缀表达式,有什么好处?
从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,
进行运算,运算结果进栈,一直到最终获得结果。
对于表达式计算非常方便
LRU算法的实现原理?
重写LinkedHashMap
public class LRUCache<K, V> extends LinkedHashMap<K, V> { private final int MAX_CACHE_SIZE; public LRUCache2(int cacheSize) { super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true); MAX_CACHE_SIZE = cacheSize; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_CACHE_SIZE; } }
使用随机算法产生一个数,要求把1-1000W之间这些数全部生成。(考察高效率,解决产生冲突的问题)
声明一个大小为10000000的数组,每次随机出来的数i,都去数组下标i-1的位置看是否为0,如果为0的话,
写入这个数字,并记录数组的真实大小,等数组的真实大小为10000000的时候,停止随机。
两个有序数组的合并排序
同时遍历两个数组,每次对比两个数组当前坐标的值哪个小,小的存入新的数组,数组下表往后移一位,
大的那边坐标不变,继续下次大小对比。依次循环。
一个数组的倒序
每次交换头尾的值,并坐标向中间靠拢。
二叉树的前序,中序,后序遍历算法
前序递归:
public void preOrderTraverse1(TreeNode root) { if (root != null) { System.out.print(root.val + "->"); preOrderTraverse1(root.left); preOrderTraverse1(root.right); } }
前序非递归:
public void preOrderTraverse2(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (node != null || !stack.empty()) {
if (node != null) {
System.out.print(node.val + "->");
stack.push(node);
node = node.left;
} else {
TreeNode tem = stack.pop();
node = tem.right;
}
}
}
中序递归:
public void inOrderTraverse(TreeNode root) { if (root != null) { inOrderTraverse(root.left); System.out.print(root.val + "->"); inOrderTraverse(root.right); } }
中序非递归:
public void inOrderTraverse(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); TreeNode node = root; while (node != null || !stack.isEmpty()) { if (node != null) { stack.push(node); node = node.left; } else { TreeNode tem = stack.pop(); System.out.print(tem.val + "->"); node = tem.right; } } }
后序递归:
public void postOrderTraverse(TreeNode root) { if (root != null) { postOrderTraverse(root.left); postOrderTraverse(root.right); System.out.print(root.val + "->"); } }
后序非递归:
public void postOrderTraverse(TreeNode root) { TreeNode cur, pre = null; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.empty()) { cur = stack.peek(); if ((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right))) { System.out.print(cur.val + "->"); stack.pop(); pre = cur; } else { if (cur.right != null) stack.push(cur.right); if (cur.left != null) stack.push(cur.left); } } }
层次遍历:
public void levelOrderTraverse(TreeNode root) { if (root == null) { return; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); System.out.print(node.val + "->"); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } }
DFS,BFS算法
深度优先算法:利用栈实现
广度优先算法:利用队列来实现
逆波兰计算器
利用栈与后缀表达式利于计算机方便计算
Hoffman 编码
按权重将节点分布在一条右子树上,使得前缀不重复
平衡二叉树?
- 平衡二叉树,左右高度之差不超过1,Add/delete可能造成高度>1,此时要旋转,维持平衡状态,
- 避免二叉树退化为链表,让Add/Delete时间复杂度但控制在O(log2N),旋转算法2个方法,1是求树的高度,
- 2是求2个高度最大值,1个空树高度为-1,只有1个根节点的树的高度为0,以后每一层+1,平衡树任意节点
- 最多有2个儿子,因此高度不平衡时,此节点的2棵子树高度差为2。例如单旋转,双旋转,插入等。红黑树放弃
- 完全平衡,追求大致平衡,保证每次插入最多要3次旋转就能平衡。
海量url去重类问题(布隆过滤器)
利用bit数组,通过不同的哈希函数定位数组中的坐标。 如果都存在的话,代表存在。有一定误判率。
数组和链表数据结构描述,各自的时间复杂度
数组查找是O(1),删除或者新增是O(N) 链表查找是O(N),删除或者新增是O(1)
二叉树遍历
递归遍历和循环遍历
hash算法的有哪几种,优缺点,使用场景
MD5和SHA256
1.保护密码。
2.防止文件篡改
3.数字签名(对整段内容加密比较费性能,所以只对哈希值进行加密)
4.文件秒传
实际场景问题解决,典型的TOP K问题
可以使用类似选择排序,类似快排,类似最大堆的算法
用三个线程按顺序循环打印abc三个字母,比如abcabcabc。
利用原子数字,对三取余,打印对应的abc。或者利用三个condition进行唤醒。
10亿个数字里里面找最小的10个。
分治,加最小堆
有1亿个数字,其中有2个是重复的,快速找到它,时间和空间要最优。
1b是8比特。 1kb是8192比特 大概12mb内存可以代表1亿数字的比特位 利用哈希来判断
2亿个随机生成的无序整数,找出中间大小的值。
准备一个大数组。依次放入数组。数字出现n次,对应下标值就为n,完成之后,遍历数组。
当累加数值为1亿时,对应下标即为中位数。时间复杂度即为O(N)
有3n+1个数字,其中3n个中是重复的,只有1个是不重复的,怎么找出来。
累加每个位置上的bit位%3 即为不重复的数字的bit位
写一个字符串(如hello)反转函数。
在原数组中对调首尾对称的位置
二分查找的时间复杂度,优势。
log2N 优势是 性能平均
一个已经构建好的TreeSet,怎么完成倒排序。
递归更换左右子树即可
一个单向链表,删除倒数第N个数据。
准备两个指针,初始指向头结点, 1号指针先走n步,然后2号指针开始走,当1号指针走到尾节点时,2号指针即为倒数第N个数据。
200个有序的数组,每个数组里面100个元素,找出top20的元素。
依次遍历每个有序数组(假设数组从大到小),对比这200个数字,最大的放入top20数组,重复20次该操作,即可获得top20数组
单向链表,查找中间的那个元素。
一个步长为1的游标,一个步长为2的游标,当步长为2的游标到达链表末尾时,步长为1的游标即中间元素
10亿个数,找出最大的10个。
分割,或者流式读取,然后利用一个大小为10的小根堆。 或者分成100份,每份计算最大的10个数字,最后对比这个1000个数字
有几台机器存储着几亿淘宝搜索日志,你只有一台2g的电脑,怎么选出搜索热度最高的十个搜索关键词?
先划分成多个小文件,送进内存排序,然后再采用多路归并排序。
10万个数,输出从小到大?
快排等算法。
有十万个单词,找出重复次数最高十个?
先用遍历一次十万单词,放入hashmap中,key为单词,value为次数。然后再遍历hashmap,放入最小堆,可以使用priorityqueue或者大小为10的数组也行
原文
http://vc2x.com/articles/2020/03/29/1585495374621.html
本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 个人整理 – Java后端面试题 – 算法篇