第1页 / 共113页
第2页 / 共113页
第3页 / 共113页
第4页 / 共113页
第5页 / 共113页
第6页 / 共113页
第7页 / 共113页
第8页 / 共113页
2021最新版数据结构与算法面试题手册 1.pdf
2021最新版数据结构与算法⾯试题⼿册
2021最新版数据结构与算法⾯试题⼿册
题⽬来源⽹络，涉版权问题联系删除
1 | Java ⼯程师
1.1 | 哈希
请说⼀说，Java中的HashMap的⼯作原理是什么？
参考回答：
HashMap类有⼀个叫做Ent ry的内部类。这个Ent ry类包含了key-value作为实例变量。 每当往
hashmap⾥⾯存放key-value对的时候，都会为它们实例化⼀个Ent ry对象，这个Ent ry对象就
会存储在前⾯提到的Ent ry数组t able中。Ent ry具体存在t able的那个位置是 根据key的
hashcode()⽅法计算出来的hash值（来决定）。
介绍⼀下，什么是Hashmap?
参考回答：
HashMap 是⼀个散列表，它存储的内容是键值对(key-value)映射。
HashMap 继承于Abst ract Map，实现了Map、Cloneable、java.io.Serializable接⼝。
HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此
外，HashMap中的映射不是有序的。
HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因⼦”。容量 是哈希表中桶的
数量，初始容量 只是哈希表在创建时的容量。加载因⼦ 是哈希表在其容量⾃动增加之前可以
达到多满的⼀种尺度。当哈希表中的条⽬数超出了加载因⼦与当前容量的乘积时，则要对该哈
希表进⾏ rehash 操作（即重建内部数据结构），从⽽哈希表将具有⼤约两倍的桶数。
通常，默认加载因⼦是 0.75, 这是在时间和空间成本上寻求⼀种折衷。加载因⼦过⾼虽然减少
了空间开销，但同时也增加了查询成本（在⼤多数 HashMap 类的操作中，包
括 get 和 put 操作，都反映了这⼀点）。在设置初始容量时应该考虑到映射中所需的条⽬数
及其加载因⼦，以便最⼤限度地减少 rehash 操作次数。如果初始容量⼤于最⼤条⽬数除以加
载因⼦，则不会发⽣ rehash 操作。
hashmap共有4个构造函数：
// 默认构造函数。HashMap()
// 指定“容量⼤⼩”的构造函数
HashMap(int capacit y)
// 指定“容量⼤⼩”和“加载因⼦”的构造函数
HashMap(int capacit y, float loadFact or)
// 包含“⼦Map”的构造函数
HashMap(Map map)
讲⼀讲，如何构造⼀致性哈希算法。
参考回答：
先构造⼀个⻓度为232的整数环（这个环被称为⼀致性Hash环），根据节点名称的Hash值
（其分布为[0, 232-1]）将服务器节点放置在这个Hash环上，然后根据数据的Key值计算得到
其Hash值（其分布也为[0, 232-1]），接着在Hash环上顺时针查找距离这个Key值的Hash值
最近的服务器节点，完成Key到服务器的映射查找。
这种算法解决了普通余数Hash算法伸缩性差的问题，可以保证在上线、下线服务器的情况下
尽量有多的请求命中原来路由到的服务器。
请谈⼀谈，hashCode() 和equals() ⽅法的重要性体现在什么地⽅？
参考回答：
Java中的HashMap使⽤hashCode()和equals()⽅法来确定键值对的索引，当根据键获取值的
时候也会⽤到这两个⽅法。如果没有正确的实现这两个⽅法，两个不同的键可能会有相同的
hash值，因此，可能会被集合认为是相等的。⽽且，这两个⽅法也⽤来发现重复元素。所以
这两个⽅法的实现对HashMap的精确性和正确性是⾄关重要的。
请问，Object作为HashMap的key的话，对Object有什么要求吗？
参考回答：
要求Object 中hashcode不能变。
请问 hashset 存的数是有序的吗？
参考回答：
Hashset 是⽆序的。
1.2 | ⼆叉树
原⽂链接：ht t ps://www.jianshu.com/p/0190985635eb
求⼆叉树的最⼤深度
参考回答：
1
2
3
4
5
class TreeNode{
int val;
//左孩子
TreeNode left;
//右孩子
TreeNode right;
6
}7
求⼆叉树的最⼩深度
参考回答：
int getMinDepth(TreeNode root){
if(root == null){
return 0;
}
return getMin(root);
1
2
3
4
5
}6
7
8
9
10
11
12
13
14
15
int getMin(TreeNode root){
if(root == null){
return Integer.MAX_VALUE;
}
if(root.left == null&&root.right == null){
return 1;
}
return Math.min(getMin(root.left),getMin(root.right)) + 1;
}
求⼆叉树中节点的个数
参考回答：
int numOfTreeNode(TreeNode root){
if(root == null){
return 0;
}
int left = numOfTreeNode(root.left);
int right = numOfTreeNode(root.right);
return left + right + 1;
}
求⼆叉树中叶⼦节点的个数
参考回答：
int numsOfNoChildNode(TreeNode root){
if(root == null){
return 0;
}
if(root.left==null&&root.right==null){
return 1;
}
return
numsOfNodeTreeNode(root.left)+numsOfNodeTreeNode(root.right);
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
10
}
求⼆叉树中第k层节点的个数
参考回答：
1
2
3
4
5
6
7
8
9
10
11
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
2
3
4
5
6
7
8
9
10
int numsOfkLevelTreeNode(TreeNode root,int k){
if(root == null||k<1){
return 0;
}
if(k==1){
return 1;
}
int numsLeft = numsOfkLevelTreeNode(root.left,k-1);
int numsRight = numsOfkLevelTreeNode(root.right,k-1);
return numsLeft + numsRight;
}
判断⼆叉树是否是平衡⼆叉树
参考回答：
boolean isBalanced(TreeNode node){
return maxDeath2(node)!=-1;
}
int maxDeath2(TreeNode node){
if(node == null){
return 0;
}
int left = maxDeath2(node.left);
int right = maxDeath2(node.right);
if(left==-1||right==-1||Math.abs(left-right)>1){
return -1;
}
return Math.max(left, right) + 1;
}
判断⼆叉树是否是完全⼆叉树
参考回答：
boolean isCompleteTreeNode(TreeNode root){
if(root == null){
return false;
}
Queue queue = new LinkedList();
queue.add(root);
boolean result = true;
boolean hasNoChild = false;
while(!queue.isEmpty()){
TreeNode current = queue.remove();
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if(hasNoChild){
if(current.left!=null||current.right!=null){
result = false;
break;
}
}else{
if(current.left!=null&¤t.right!=null){
queue.add(current.left);
queue.add(current.right);
}else if(current.left!=null&¤t.right==null){
queue.add(current.left);
hasNoChild = true;
}else if(current.left==null&¤t.right!=null){
result = false;
break;
}else{
hasNoChild = true;
}
}
}
return result;
}
两个⼆叉树是否完全相同
参考回答：
boolean isSameTreeNode(TreeNode t1,TreeNode t2){
if(t1==null&&t2==null){
return true;
}
else if(t1==null||t2==null){
return false;
}
if(t1.val != t2.val){
return false;
}
boolean left = isSameTreeNode(t1.left,t2.left);
boolean right = isSameTreeNode(t1.right,t2.right);
return left&&right;
}
两个⼆叉树是否互为镜像
参考回答：
1
boolean isMirror(TreeNode t1,TreeNode t2){
2
3
4
5
6
7
8
9
10
11
12
13
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if(t1==null&&t2==null){
return true;
}
if(t1==null||t2==null){
return false;
}
if(t1.val != t2.val){
return false;
}
return isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left);
}
翻转⼆叉树or镜像⼆叉树
参考回答：
TreeNode mirrorTreeNode(TreeNode root){
if(root == null){
return null;
}
TreeNode left = mirrorTreeNode(root.left);
TreeNode right = mirrorTreeNode(root.right);
root.left = right;
root.right = left;
return root;
}
求两个⼆叉树的最低公共祖先节点
参考回答：
TreeNode getLastCommonParent(TreeNode root,TreeNode t1,TreeNode t2){
if(findNode(root.left,t1)){
if(findNode(root.right,t2)){
return root;
}else{
return getLastCommonParent(root.left,t1,t2);
}
}else{
if(findNode(root.left,t2)){
return root;
}else{
return getLastCommonParent(root.right,t1,t2)
}
}
}
// 查找节点node是否在当前 二叉树中
boolean findNode(TreeNode root,TreeNode node){
if(root == null || node == null){
19
20
21
22
23
24
25
26
27
28
29
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
2
3
4
5
6
7
8
9
10
11
return false;
}
if(root == node){
return true;
}
boolean found = findNode(root.left,node);
if(!found){
found = findNode(root.right,node);
}
return found;
}
⼆叉树的前序遍历
参考回答：
迭代解法
ArrayList preOrder(TreeNode root){
Stack stack = new Stack();
ArrayList list = new ArrayList();
if(root == null){
return list;
}
stack.push(root);
while(!stack.empty()){
TreeNode node = stack.pop();
list.add(node.val);
if(node.right!=null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
return list;
}
递归解法
ArrayList preOrderReverse(TreeNode root){
ArrayList result = new ArrayList();
preOrder2(root,result);
return result;
}
void preOrder2(TreeNode root,ArrayList result){
if(root == null){
return;
}
result.add(root.val);
12
13
14
preOrder2(root.left,result);
preOrder2(root.right,result);
}
⼆叉树的中序遍历
参考回答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
2
3
4
5
6
7
8
9
10
ArrayList inOrder(TreeNode root){
ArrayList list = new ArrayList<();
Stack stack = new Stack();
TreeNode current = root;
while(current != null|| !stack.empty()){
while(current != null){
stack.add(current);
current = current.left;
}
current = stack.peek();
stack.pop();
list.add(current.val);
current = current.right;
}
return list;
}
⼆叉树的后序遍历
参考回答：
ArrayList postOrder(TreeNode root){
ArrayList list = new ArrayList();
if(root == null){
return list;
}
list.addAll(postOrder(root.left));
list.addAll(postOrder(root.right));
list.add(root.val);
return list;
}
前序遍历和后序遍历构造⼆叉树
参考回答：
1
2
3
4
TreeNode buildTreeNode(int[] preorder,int[] inorder){
if(preorder.length!=inorder.length){
return null;
}
