2021最新版数据结构与算法面试题手册.pdf
《2021最新版数据结构与算法面试题手册.pdf》由会员分享,可在线阅读,更多相关《2021最新版数据结构与算法面试题手册.pdf(113页珍藏版)》请在文库网上搜索。
1、2021最新版数据结构与算法试题册2021最新版数据结构与算法试题册题来源络,涉版权问题联系删除1 | Java 程师1.1 | 哈希 请说说,Java中的HashMap的作原理是什么?参考回答:HashMap类有个叫做Entry的内部类。这个Entry类包含了key-value作为实例变量。 每当往hashmap存放key-value对的时候,都会为它们实例化个Entry对象,这个Entry对象就会存储在前提到的Entry数组table中。Entry具体存在table的那个位置是 根据key的hashcode()法计算出来的hash值(来决定)。 介绍下,什么是Hashmap?参考回答:Ha
2、shMap 是个散列表,它存储的内容是键值对(key-value)映射。HashMap继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接。HashMap的实现不是同步的,这意味着它不是线程安全的。它的key、value都可以为null。此外,HashMap中的映射不是有序的。HashMap 的实例有两个参数影响其性能:“初始容量” 和 “加载因”。容量 是哈希表中桶的数量,初始容量 只是哈希表在创建时的容量。加载因 是哈希表在其容量动增加之前可以达到多满的种尺度。当哈希表中的条数超出了加载因与当前容量的乘积时,则要对该哈希表进rehash
3、操作(即重建内部数据结构),从哈希表将具有约两倍的桶数。通常,默认加载因是0.75,这是在时间和空间成本上寻求种折衷。加载因过虽然减少了空间开销,但同时也增加了查询成本(在多数HashMap类的操作中,包括get和put操作,都反映了这点)。在设置初始容量时应该考虑到映射中所需的条数及其加载因,以便最限度地减少rehash操作次数。如果初始容量于最条数除以加载因,则不会发rehash操作。hashmap共有4个构造函数:/ 默认构造函数。HashMap()/ 指定“容量”的构造函数HashMap(int capacity)/ 指定“容量”和“加载因”的构造函数HashMap(int capac
4、ity, float loadFactor)/ 包含“Map”的构造函数HashMap(Map map) 讲讲,如何构造致性哈希算法。参考回答:先构造个度为232的整数环(这个环被称为致性Hash环),根据节点名称的Hash值(其分布为0, 232-1)将服务器节点放置在这个Hash环上,然后根据数据的Key值计算得到其Hash值(其分布也为0, 232-1),接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点,完成Key到服务器的映射查找。这种算法解决了普通余数Hash算法伸缩性差的问题,可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。 请谈谈,
5、hashCode() 和equals() 法的重要性体现在什么地?参考回答:Java中的HashMap使hashCode()和equals()法来确定键值对的索引,当根据键获取值的时候也会到这两个法。如果没有正确的实现这两个法,两个不同的键可能会有相同的hash值,因此,可能会被集合认为是相等的。且,这两个法也来发现重复元素。所以这两个法的实现对HashMap的精确性和正确性是关重要的。 请问,Object作为HashMap的key的话,对Object有什么要求吗?参考回答:要求Object中hashcode不能变。 请问 hashset 存的数是有序的吗?参考回答:Hashset是序的。1.
6、2 | 叉树原链接:https:/ 求叉树的最深度参考回答:class TreeNode1 int val;2 /左孩子3 TreeNode left;4 /右孩子5 求叉树的最深度参考回答: 求叉树中节点的个数参考回答: 求叉树中叶节点的个数参考回答: TreeNode right;67int getMinDepth(TreeNode root)1 if(root = null)2 return 0;3 4 return getMin(root);56int getMin(TreeNode root)7 if(root = null)8 return Integer.MAX_VALUE;9
7、10 if(root.left = null&root.right = null)11 return 1;12 13 return Math.min(getMin(root.left),getMin(root.right) + 1;1415 int numOfTreeNode(TreeNode root)1 if(root = null)2 return 0;3 4 5 int left = numOfTreeNode(root.left);6 int right = numOfTreeNode(root.right);7 return left + right + 1;8 9 int num
8、sOfNoChildNode(TreeNode root)1 if(root = null)2 return 0;3 4 if(root.left=null&root.right=null)5 return 1;6 7 return numsOfNodeTreeNode(root.left)+numsOfNodeTreeNode(root.right);8 9 求叉树中第k层节点的个数参考回答: 判断叉树是否是平衡叉树参考回答: 判断叉树是否是完全叉树参考回答: 10 int numsOfkLevelTreeNode(TreeNode root,int k)1 if(root = null|k
9、1)10 return -1;11 12 return Math.max(left, right) + 1;13 14 boolean isCompleteTreeNode(TreeNode root)1 if(root = null)2 return false;3 4 Queue queue = new LinkedList();5 queue.add(root);6 boolean result = true;7 boolean hasNoChild = false;8 while(!queue.isEmpty()9 TreeNode current = queue.remove();1
10、0 两个叉树是否完全相同参考回答: 两个叉树是否互为镜像参考回答: if(hasNoChild)11 if(current.left!=null|current.right!=null)12 result = false;13 break;14 15 else16 if(current.left!=null¤t.right!=null)17 queue.add(current.left);18 queue.add(current.right);19 else if(current.left!=null¤t.right=null)20 queue.add(current.
11、left);21 hasNoChild = true;22 23 else if(current.left=null¤t.right!=null)24 result = false;25 break;26 else27 hasNoChild = true;28 29 30 31 32 return result;33 34 boolean isSameTreeNode(TreeNode t1,TreeNode t2)1 if(t1=null&t2=null)2 return true;3 4 else if(t1=null|t2=null)5 return false;6 7 if
12、(t1.val != t2.val)8 return false;9 10 boolean left = isSameTreeNode(t1.left,t2.left);11 boolean right = isSameTreeNode(t1.right,t2.right);12 return left&right;13 14 15 boolean isMirror(TreeNode t1,TreeNode t2)1 翻转叉树or镜像叉树参考回答: 求两个叉树的最低公共祖先节点参考回答: if(t1=null&t2=null)2 return true;3 4 if(t1=null|t2=nu
13、ll)5 return false;6 7 if(t1.val != t2.val)8 return false;9 10 return isMirror(t1.left,t2.right)&isMirror(t1.right,t2.left);11 12 13 TreeNode mirrorTreeNode(TreeNode root)1 if(root = null)2 return null;3 4 TreeNode left = mirrorTreeNode(root.left);5 TreeNode right = mirrorTreeNode(root.right);6 root.
14、left = right;7 root.right = left;8 return root;9 10 TreeNode getLastCommonParent(TreeNode root,TreeNode t1,TreeNode t2)1 if(findNode(root.left,t1)2 if(findNode(root.right,t2)3 return root;4 else5 return getLastCommonParent(root.left,t1,t2);6 7 else8 if(findNode(root.left,t2)9 return root;10 else11 r
15、eturn getLastCommonParent(root.right,t1,t2)12 13 14 15 / 查找节点node是否在当前 二叉树中16 boolean findNode(TreeNode root,TreeNode node)17 if(root = null | node = null)18 叉树的前序遍历参考回答:迭代解法 递归解法 return false;19 20 if(root = node)21 return true;22 23 boolean found = findNode(root.left,node);24 if(!found)25 found =
16、findNode(root.right,node);26 27 return found;28 29 ArrayList preOrder(TreeNode root)1 Stack stack = new Stack();2 ArrayList list = new ArrayList();3 if(root = null)4 return list;5 6 stack.push(root);7 while(!stack.empty()8 TreeNode node = stack.pop();9 list.add(node.val);10 if(node.right!=null)11 st
17、ack.push(node.right);12 13 if(node.left != null)14 stack.push(node.left);15 16 17 18 return list;19 20 ArrayList preOrderReverse(TreeNode root)1 ArrayList result = new ArrayList();2 preOrder2(root,result);3 return result;4 5 6 void preOrder2(TreeNode root,ArrayList result)7 if(root = null)8 return;9
18、 10 result.add(root.val);11 叉树的中序遍历参考回答: 叉树的后序遍历参考回答: 前序遍历和后序遍历构造叉树参考回答: preOrder2(root.left,result);12 preOrder2(root.right,result);13 14 ArrayList inOrder(TreeNode root)1 ArrayList list = new ArrayList();2 Stack stack = new Stack();3 TreeNode current = root;4 while(current != null| !stack.empty()5
19、 while(current != null)6 stack.add(current);7 current = current.left;8 9 current = stack.peek();10 stack.pop();11 list.add(current.val);12 current = current.right;13 14 15 return list;16 17 18 ArrayList postOrder(TreeNode root)1 ArrayList list = new ArrayList();2 if(root = null)3 return list;4 5 lis
20、t.addAll(postOrder(root.left);6 list.addAll(postOrder(root.right);7 list.add(root.val);8 return list;9 10 TreeNode buildTreeNode(int preorder,int inorder)1 if(preorder.length!=inorder.length)2 return null;3 4 在叉树中插节点参考回答: return myBuildTree(inorder,0,inorder.length-1,preorder,0,preorder.length-1);5
21、6 TreeNode myBuildTree(int inorder,int instart,int inend,int preorder,int prestart,int preend)7 if(instartinend)8 return null;9 10 TreeNode root = new TreeNode(preorderprestart);11 int position = findPosition(inorder,instart,inend,preorderstart);12 root.left = myBuildTree(inorder,instart,position-1,
22、preorder,prestart+1,prestart+position-instart);13 root.right = myBuildTree(inorder,position+1,inend,preorder,position-inend+preend+1,preend);14 return root;15 16 int findPosition(int arr,int start,int end,int key)17 int i;18 for(i = start;inode.val)10 tmp = tmp.left;11 else12 tmp = tmp.right;13 14 1
23、5 if(last!=null)16 if(last.valnode.val)17 last.left = node;18 输个叉树和个整数,打印出叉树中节点值的和等于输整数所有的路径参考回答: 叉树的搜索区间给定两个值 k1 和 k2(k1 k2)和个叉查找树的根节点。找到树中所有值在 k1 到 k2 范围内的节点。即打印所有x (k1 = x = k2) 其中 x 是叉查找树的中的节点值。返回所有升序的节点值。作者:IOExceptioner链接:https:/ else19 last.right = node;20 21 22 return root;23 24 void findPat
24、h(TreeNode r,int i)1 if(root = null)2 return;3 4 Stack stack = new Stack();5 int currentSum = 0;6 findPath(r, i, stack, currentSum);7 8 9 void findPath(TreeNode r,int i,Stack stack,int currentSum)10 currentSum+=r.val;11 stack.push(r.val);12 if(r.left=null&r.right=null)13 if(currentSum=i)14 for(int p
25、ath:stack)15 System.out.println(path);16 17 18 19 20 if(r.left!=null)21 findPath(r.left, i, stack, currentSum);22 23 if(r.right!=null)24 findPath(r.right, i, stack, currentSum);25 26 stack.pop();27 28参考回答: 叉树的层次遍历参考回答: ArrayList result;1 ArrayList searchRange(TreeNode root,int k1,int k2)2 result = n
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2021 最新版 数据结构 算法 试题 手册