Java八股文（数据结构）
Java八股文の数据结构
- 数据结构
数据结构
- 请解释以下数据结构的概念：链表、栈、队列和树。
链表是一种线性数据结构，由节点组成，每个节点包含了指向下一个节点的指针；
（图片来源网络，侵删）栈是一种后进先出（LIFO）的数据结构，只能在一端进行插入和删除操作；
队列是一种先进先出（FIFO）的数据结构，一端进行插入操作，在另一端进行删除操作；
树是一种非线性数据结构，由节点和边组成，其中父节点可以有多个子节点。
- 请解释下面时间复杂度符号的含义：O(1)、O(log n)、O(n)和O(n^2)。
O(1)表示算法的执行时间不随输入规模变化；
O(log n)表示算法的执行时间随输入规模的增加而增加，但增加速度较慢；
O(n)表示算法的执行时间与输入规模成正比；
（图片来源网络，侵删）O(n^2)表示算法的执行时间与输入规模的平方成正比。
- 请解释什么是二分查找，并提供一个二分查找的实现。
二分查找是一种在有序数组中查找元素的算法，每次都将区间缩小为原来的一半，直到找到目标元素或无法再缩小。
以下是一个二分查找的实现（Java）：
public int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; while (left int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] heap[parentIndex(index)]) { swap(index, parentIndex(index)); index = parentIndex(index); } } public int removeMax() { if (size == 0) { throw new IllegalStateException("Heap is empty"); } int max = heap[0]; heap[0] = heap[size - 1]; size--; siftDown(0); return max; } private void siftDown(int index) { while (leftChildIndex(index) heap[leftChildIndex(index)]) { maxIndex = rightChildIndex(index); } if (heap[index] >= heap[maxIndex]) { break; } swap(index, maxIndex); index = maxIndex; } } // Helper methods for calculating parent and child indices private int parentIndex(int index) { return (index - 1) / 2; } private int leftChildIndex(int index) { return 2 * index + 1; } private int rightChildIndex(int index) { return 2 * index + 2; } private void swap(int index1, int index2) { int temp = heap[index1]; heap[index1] = heap[index2]; heap[index2] = temp; } }该堆类提供了插入和删除最大值的操作，并保持了堆的性质。
- 请解释什么是哈夫曼树，并提供一个哈夫曼编码的实现。
哈夫曼树是一种用于数据编码的树结构，用于将频率较高的字符编码为较短的二进制码，以实现更高的压缩比。
哈夫曼编码的实现需要构建哈夫曼树，并通过DFS遍历树来生成每个字符的编码。
以下是一个哈夫曼编码的实现（Java）：
class HuffmanNode implements Comparable { char value; int frequency; HuffmanNode left; HuffmanNode right; public HuffmanNode(char value, int frequency) { this.value = value; this.frequency = frequency; } @Override public int compareTo(HuffmanNode other) { return this.frequency - other.frequency; } } public String huffmanEncode(String text) { if (text.isEmpty()) { return ""; } // Calculate character frequencies Map frequencies = new HashMap(); for (char c : text.toCharArray()) { frequencies.put(c, frequencies.getOrDefault(c, 0) + 1); } // Build Huffman tree PriorityQueue pq = new PriorityQueue(); for (Map.Entry entry : frequencies.entrySet()) { pq.offer(new HuffmanNode(entry.getKey(), entry.getValue())); } while (pq.size() > 1) { HuffmanNode left = pq.poll(); HuffmanNode right = pq.poll(); HuffmanNode merged = new HuffmanNode('-', left.frequency + right.frequency); merged.left = left; merged.right = right; pq.offer(merged); } // Generate Huffman codes Map codes = new HashMap(); generateCodes(pq.peek(), "", codes); // Encode the text StringBuilder encodedText = new StringBuilder(); for (char c : text.toCharArray()) { encodedText.append(codes.get(c)); } return encodedText.toString(); } private void generateCodes(HuffmanNode node, String code, Map codes) { if (node == null) { return; } if (node.left == null && node.right == null) { codes.put(node.value, code); } generateCodes(node.left, code + "0", codes); generateCodes(node.right, code + "1", codes); }该示例中，huffmanEncode方法接受一个字符串，并返回其哈夫曼编码后的结果。
- 请解释深度优先搜索（DFS）和广度优先搜索（BFS）的区别。
DFS和BFS是两种图遍历的算法。
DFS以深度为优先，从起始节点开始，尽可能深入地访问其邻居节点，直到无法再深入为止，然后回溯到上一个节点。
BFS以广度为优先，从起始节点开始，依次访问同一层级的节点，再逐层向下一层级访问。
DFS适用于查找目标在树或图中的路径，而BFS适用于查找最短路径或查找目标在特定距离内的节点。
- 请解释什么是红黑树，并说明其性质。
红黑树是一种自平衡的二叉搜索树，具有以下性质：
● 每个节点是红色或黑色。
● 根节点是黑色。
● 每个叶子节点（NIL节点）是黑色。
● 如果一个节点是红色，则其子节点必须是黑色（不能有两个相邻的红色节点）。
● 从任一节点到其每个叶子的所有路径都包含相同数量的黑色节点。
- 请解释什么是AVL树，并说明其性质。
AVL树是一种自平衡的二叉搜索树，具有以下性质：
● 对于每个节点，其左子树和右子树的高度差（平衡因子）最多为1。
● 任意节点的左子树和右子树都是AVL树。
- 请解释什么是B树，并说明其特点。
B树是一种自平衡的多路搜索树，具有以下特点：
● 每个节点最多有M个子节点（M>=2）。
● 除根节点和叶子节点外，每个节点至少有M/2个子节点。
● 所有叶子节点都在同一层级上。
- 请解释什么是缓存淘汰策略，并提供两个常见的缓存淘汰策略。
缓存淘汰策略用于在缓存容量不足时确定哪些项目应从缓存中淘汰。
常见的缓存淘汰策略有：
● 最近最少使用（Least Recently Used, LRU）：淘汰最近最少使用的项目，即最长时间未被访问的项目。
● 最不常用（Least Frequently Used, LFU）：淘汰使用频率最低的项目，即被访问次数最少的项目。
- 请解释什么是拓扑排序，并提供一个拓扑排序的实现。
拓扑排序是一种对有向无环图进行排序的算法，使得所有边的方向均从前向后。
以下是一个拓扑排序的实现（Java）：
public List topologicalSort(int numCourses, int[][] prerequisites) { List sortedOrder = new ArrayList(); if (numCourses return sortedOrder; } // 1. 构建图和入度数组 Map graph.put(i, new ArrayList int parent = prerequisite[1]; int child = prerequisite[0]; graph.get(parent).add(child); inDegree[child]++; } // 2. 将入度为0的节点加入队列 Queue if (inDegree[i] == 0) { queue.offer(i); } } // 3. 逐个从队列取出节点，减少相关节点的入度并判断是否入队 while (!queue.isEmpty()) { int node = queue.poll(); sortedOrder.add(node); List inDegree[child]--; if (inDegree[child] == 0) { queue.offer(child); } } } // 4. 判断是否存在环 if (sortedOrder.size() != numCourses) { return new ArrayList private int[] parent; private int[] rank; public UnionFind(int size) { parent = new int[size]; rank = new int[size]; for (int i = 0; i该并查集类提供了查找和合并操作，并使用路径压缩和按秩合并的优化策略。
- 请解释什么是动态规划，并提供一个使用动态规划解决的问题示例。
动态规划（Dynamic Programming，简称DP）是一种解决多阶段决策最优化问题的方法。
它将问题划分为若干个子问题，并保存子问题的解来避免重复计算。
通过递推求解各个子问题，最终得到原问题的解。
一个典型的动态规划问题是求解最长公共子序列（Longest Common Subsequence，简称LCS）。
给定两个字符串s1和s2，求它们的最长公共子序列的长度。
示例：
public class LongestCommonSubsequence { public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(); int n = text2.length(); int[][] dp = new int[m + 1][n + 1]; // dp[i][j]表示text1前i个字符和text2前j个字符的最长公共子序列长度 for (int i = 1; i for (int j = 1; j if (text1.charAt(i - 1) == text2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; // 当前字符相等，最长公共子序列长度加1 } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // 当前字符不相等，取前一步的最优解 } } } return dp[m][n]; } } int val; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; } } public class PreorderTraversal { public List List return result; } Stack TreeNode node = stack.pop(); result.add(node.val); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return result; } } private Stack inStack = new Stack inStack.push(x); } public int pop() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.pop(); } public int peek() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.peek(); } public boolean empty() { return inStack.isEmpty() && outStack.isEmpty(); } } private Deque stack = new LinkedList stack.push(x); } public int pop() { return stack.pop(); } public int top() { return stack.peek(); } public boolean empty() { return stack.isEmpty(); } } int val; ListNode next; public ListNode(int val) { this.val = val; } } public class ReverseLinkedList { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } } private int V; private List this.V = V; adj = new ArrayList adj.add(new ArrayList adj.get(u).add(v); } public void DFS(int v) { boolean[] visited = new boolean[V]; DFSUtil(v, visited); } private void DFSUtil(int v, boolean[] visited) { visited[v] = true; System.out.print(v + " "); for (int i : adj.get(v)) { if (!visited[i]) { DFSUtil(i, visited); } } } } private int V; private List this.V = V; adj = new ArrayList adj.add(new ArrayList adj.get(u).add(v); } public void BFS(int v) { boolean[] visited = new boolean[V]; Queue int curr = queue.poll(); System.out.print(curr + " "); for (int i : adj.get(curr)) { if (!visited[i]) { visited[i] = true; queue.offer(i); } } } } } private int[] heap; private int size; public MinHeap(int capacity) { heap = new int[capacity]; size = 0; } public void insert(int key) { if (size == heap.length) { // 堆已满 return; } size++; int i = size - 1; heap[i] = key; while (i 0 && heap[parent(i)] heap[i]) { // 交换节点值 swap(i, parent(i)); i = parent(i); } } public void delete(int key) { int index = -1; for (int i = 0; i heap[i]) { swap(i, parent(i)); i = parent(i); } } private void minHeapify(int i) { int smallest = i; int left = leftChild(i); int right = rightChild(i); if (left- 实现一个哈希表。
class MyHashMap { private final int SIZE = 10000; private ListNode[] table; class ListNode { int key; int value; ListNode next; public ListNode(int key, int value) { this.key = key; this.value = value; this.next = null; } } public MyHashMap() { table = new ListNode[SIZE]; } public void put(int key, int value) { int index = getIndex(key); if (table[index] == null) { table[index] = new ListNode(-1, -1); } ListNode prev = findElement(table[index], key); if (prev.next == null) { prev.next = new ListNode(key, value); } else { prev.next.value = value; } } public int get(int key) { int index = getIndex(key); if (table[index] == null) { return -1; } ListNode prev = findElement(table[index], key); if (prev.next == null) { return -1; } return prev.next.value; } public void remove(int key) { int index = getIndex(key); if (table[index] == null) { return; } ListNode prev = findElement(table[index], key); if (prev.next == null) { return; } prev.next = prev.next.next; } private int getIndex(int key) { return Integer.hashCode(key) % SIZE; } private ListNode findElement(ListNode bucket, int key) { ListNode prev = null; ListNode curr = bucket; while (curr != null && curr.key != key) { prev = curr; curr = curr.next; } return prev; } }- 实现一个动态数组。
class DynamicArray { private int[] array; private int size; private int capacity; public DynamicArray() { array = new int[10]; size = 0; capacity = 10; } public void add(int value) { if (size == capacity) { expandCapacity(); } array[size] = value; size++; } public int get(int index) { if (index = size) { throw new IndexOutOfBoundsException(); } return array[index]; } public void set(int index, int value) { if (index = size) { throw new IndexOutOfBoundsException(); } array[index] = value; } public int size() { return size; } public void remove(int index) { if (index = size) { throw new IndexOutOfBoundsException(); } for (int i = index; i- 实现一个有序数组的二分查找。
class BinarySearch { public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid]
文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。
还没有评论，来说两句吧...