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
26、ew ArrayList();3 searchHelper(root,k1,k2);4 return result;5 6 void searchHelper(TreeNode root,int k1,int k2)7 if(root = null)8 return;9 10 if(root.valk1)11 searchHelper(root.left,k1,k2);12 13 if(root.val=k1&root.val=k2)14 result.add(root.val);15 16 if(root.valk2)17 searchHelper(root.right,k1,k2);18
27、19 20 ArrayListArrayList levelOrder(TreeNode root)1 ArrayListArrayList result = new ArrayListArrayList();2 if(root = null)3 return result;4 5 Queue queue = new LinkedList();6 queue.offer(root);7 while(!queue.isEmpty()8 int size = queue.size();9 ArrayList level = new ArrayList():10 for(int i = 0;i si
28、ze ;i+)11 TreeNode node = queue.poll();12 level.add(node.val);13 if(node.left != null)14 queue.offer(node.left);15 16 if(node.right != null)17 queue.offer(node.right);18 19 20 result.add(Level);21 22 叉树内两个节点的最距离叉树中两个节点的最距离可能有三种情况：1.左树的最深度+右树的最深度为叉树的最距离2.左树中的最距离即为叉树的最距离3.右树种的最距离即为叉树的最距离因此，递归求解即可作者：IO
29、Exceptioner链接：https:/ 不同的叉树给出n，问由 1.n为节点组成的不同的叉查找树有多少种？参考回答： return result;23 24private static class Result 1 int maxDistance; 2 int maxDepth; 3 public Result() 4 5 6 public Result(int maxDistance, int maxDepth) 7 this.maxDistance = maxDistance; 8 this.maxDepth = maxDepth; 9 10 11 int getMaxDistance
30、(TreeNode root)12 return getMaxDistanceResult(root).maxDistance;13 14 Result getMaxDistanceResult(TreeNode root)15 if(root = null)16 Result empty = new Result(0,-1);17 return empty;18 19 Result lmd = getMaxDistanceResult(root.left);20 Result rmd = getMaxDistanceResult(root.right);21 Result result =
31、new Result();22 result.maxDepth = Math.max(lmd.maxDepth,rmd.maxDepth) + 1;23 result.maxDistance = Math.max(lmd.maxDepth + rmd.maxDepth,Math.max(lmd.maxDistance,rmd.maxDistance);24 return result;25 26 判断叉树是否是合法的叉查找树(BST)棵BST定义为：节点的左树中的值要严格于该节点的值。节点的右树中的值要严格于该节点的值。左右树也必须是叉查找树。个节点的树也是叉查找树。参考回答： 1.3 | 链
32、表 谈谈，bucket如果链表存储，它的缺点是什么？参考回答：查找速度慢，因为查找时，需要循环链表访问 int numTrees(int n )1 int counts = new intn+2;2 counts0 = 1;3 counts1 = 1;4 for(int i = 2;i=n;i+)5 for(int j = 0;j= root.val)11 return false;12 13 firstNode = false;14 lastVal = root.val;15 if (!isValidBST(root.right) 16 return false;17 18 return t
33、rue;19 20如果进频繁插和删除操作，会导致速度很慢。 有个链表，奇数位升序偶数位降序，如何将链表变成升序？参考回答：public class1OddIncreaseEvenDecrease 2/*3* 按照奇偶位拆分成两个链表4* param head5* return6*/7public static Node getLists(Node head)8Node head1 =null;9Node head2 =null;1011Node cur1 =null;12Node cur2 =null;13int count =1;/用来计数14while(head !=null)15if(c
34、ount %2 =1)16if(cur1 !=null)17cur1.next = head;18cur1 = cur1.next;19else20cur1 = head;21head1 = cur1;2223else24if(cur2 !=null)25cur2.next = head;26cur2 = cur2.next;27else28cur2 = head;29head2 = cur2;303132head = head.next;33count+;3435/跳出循环，要让最后两个末尾元素的下一个都指向null36cur1.next =null;37cur2.next =null;38
35、39Node nodes =new Nodehead1,40head2;41return nodes;424344/*45* 反转链表46* param head47* return48*/49public static Node reverseList(Node head)50Node pre =null;51Node next =null;52while(head !=null)53next = head.next;54head.next = pre;55pre = head;56head = next;5758return pre;596061/*62* 合并两个有序链表63* para
36、m head164* param head265* return66*/67public static Node CombineList(Node head1,68Node head2)69if(head1 =null | head2 =null)70return head1 !=null ? head1 :71head2;7273Node head = head1.value head2.value ?74head1 : head2;75Node cur1 = head = head1 ? head1 :76head2;77Node cur2 = head = head1 ? head2 :
37、78head1;79Node pre =null;80Node next =null;81while(cur1 !=null & cur2 !=82null)83if(cur1.value next =3nullptr)4return head;5ListNode* p;6ListNode* q;7ListNode* r;8p = head;9q = head-next;10head-next = nullptr;/旧的头指针是新的尾指针 指向NULL11while(q)12r = q-next;/用来保存下一步要处理的指针13q-next = p;/p q 交替处理 进行反转单链表14p =
38、 q;15q = r;1617head = p;/最后的q必定指向NULL，p就成了新链表的头指针18return head;1920通过使STL库中的map表进映射。先定义 map m; 将个 NODE * 指针映射成数组的下标，并赋值为个 int 类型的数值。然后从链表的头指针开始往后遍历，每次遇到个指针p，就判断 mp 是否为0。如果为0，则将mp赋值为1，表示该节点第次访问；如果mp的值为1，则说明这个节点已经被访问过次了，于是就形成了环。 随机链表的复制参考回答：public RandomListNode copyRandomList(RandomListNode head) 12i
39、f (head =null)3return null;45RandomListNode p = head;67/ copy every node and insert to list8while (p !=null) 9RandomListNode copy =new RandomListNode(p.label);10copy.next = p.next;11p.next = copy;12p = copy.next;131415/ copy random pointer for each new node16p = head;17while (p !=null) 18if (p.rando
40、m !=null)19p.next.random = p.random.next;20p = p.next.next;212223/ break list to two24p = head;25RandomListNode newHead = head.next;26while (p !=null) 27RandomListNode temp = p.next;28p.next = temp.next;29if (temp.next !=null)30temp.next = temp.next.next;31p = p.next;3233341.4 | 数组 写个算法，可以将个维数组顺时针旋转
41、90度。参考回答： 个数组，除个元素外其它都是两两相等，求那个元素?参考回答： 找出数组中和为S的对组合，找出组就参考回答：return newHead;3536public void1rotate(int matrix) 2int n = matrix.length;3for (int i =0; i n/2; i+) 4for (int j = i; j n-1-i; j+)56int temp = matrixij;7matrixij =8matrixn-1-ji;9matrixn-1-ji =10matrixn-1-in-1-j;11matrixn-1-in-1-j =12matrix
42、jn-1-i;13matrixjn-1-i = temp;14151617public static int find1From2(int a)1int len = a.length, res =0;2for(int i =0; i len; i+)3res= res ai;45return res;67public int1twoSum(int nums,int target) 2 求个数组中连续向量的最和参考回答： 寻找数组中前K个最的数参考回答：HashMap map =3new HashMap();4int a =new int2;5map.put(nums0,0);6for (int
43、 i =1; i nums.length;7i+) 8if (map.containsKey(target - numsi) 9a0 = map.get(target -10numsi);11a1 = i;12return a;13else 14map.put(numsi, i);151617return a;1819public int1maxSubArray(int nums) 2int sum =0;3int maxSum = Integer.MIN_VALUE;4if (nums =null | nums.length =0) 5return sum;67for (int i =0;
44、i nums.length;8i+) 9sum += numsi;10maxSum = Math.max(maxSum, sum);11if (sum 0) 12sum =0;131415return maxSum;1617public int1findKthLargest(int nums,int k) 2if (k 1 | nums =null) 3return40;567return getKth(nums.length - k +1, nums,0,8nums.length -1);91011public int12getKth(int k,int nums,int start,int
45、 end) 1314int pivot = numsend;1516int left = start;17int right = end;1819while (true) 2021while22(numsleft pivot & left = pivot & right left) 28 right-;293031if32(left = right) 33 break;343536swap(nums,37left, right);383940swap(nums, left, end);41421.5 | 排序 Java写个冒泡排序？参考回答：if (k = left +1) 43return4
46、4pivot;45else if (k left +1) 46return47getKth(k, nums, start, left -1);48else 49return50getKth(k, nums, left +1, end);51525354public void55swap(int nums,int n1,int n2) 56int tmp = numsn1;57numsn1 = numsn2;58numsn2 = tmp;5960import1java.util.Comparator;2/*3* 排序器接口(策略模式: 将算法封装到具有共同接口的独立的类中使得它们可以相互替换)4
47、*/5public interface Sorter 6/*7*8*/9public interface Sorter 10/*11* 排序12* param list 待排序的数组13*/14public Textends Comparablevoid sort(T list);15/*16* 排序17* param list 待排序的数组18* param comp 比较两个对象的比较器19*/20public void sort(T list, Comparator comp);2122import java.util.Comparator;23/*24* 冒泡排序25*26*/27pu
48、blic class BubbleSorterimplements Sorter 28Override29public Textends Comparablevoid sort(T30list) 31boolean swapped =true;32for (int i =1, len = list.length; i33 len & swapped; +i) 34swapped =35false;36for (int j =370; j 0) 4041T temp = listj;4243listj = listj +1;4445listj +1 = temp;4647swapped =tru
49、e;484950515253Override54public void sort(T list, Comparator55comp) 56boolean swapped =true;57for (int i =1, len = list.length; i58 len & swapped; +i) 59swapped =60 介绍下，排序都有哪种法？请列举出来参考回答：排序的法有：插排序（直接插排序、希尔排序），交换排序（冒泡排序、快速排序），选择排序（直接选择排序、堆排序），归并排序，分配排序（箱排序、基数排序）快速排序的伪代码。/ /使快速排序法对a 0 :n- 1 排序从a 0 :n-
50、1 中选择个元素作为m i d d l e，该元素为点把余下的元素分割为两段left和r i g h t，使得l e f t中的元素都于等于点，right中的元素都于等于点递归地使快速排序法对left进排序递归地使快速排序法对right进排序所得结果为l e f t + m i d d l e + r i g h t 介绍下，归并排序的原理是什么？参考回答：（1）归并排序是建在归并操作上的种有效的排序算法。该算法是采分治法（Divide and Conquer）的个常典型的应。（2）先考虑下如何将将个有序数列合并。这个常简单，只要从较个数列的第个数，谁就先取谁，取了后就在对应数列中删除这个数。
