Java 数据结构面试题
常见技术问题 刘宇帅 3月前 阅读量: 214
1. 实现单链表的反转
题目描述：
编写一个函数，反转一个单链表。
示例：
输入: 1 -> 2 -> 3 -> 4 -> 5 -> null
输出: 5 -> 4 -> 3 -> 2 -> 1 -> null解答：
反转单链表可以使用迭代或递归的方法。这里采用迭代法。
代码实现：
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}2. 判断链表中是否有环
题目描述：
给定一个链表，判断链表中是否有环。
示例：
输入: 1 -> 2 -> 3 -> 4 -> 2 (环起始于节点2)
输出: true解答：
使用快慢指针（Floyd 判圈算法），如果快慢指针在遍历过程中相遇，则存在环。
代码实现：
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) return false;
slow = slow.next;
fast = fast.next.next;
}
return true;
}3. 找出二叉树的最低公共祖先
题目描述：
给定一个二叉树，找出两个指定节点的最低公共祖先（LCA）。
示例：
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3解答：
递归遍历二叉树，当找到 p 或 q 时返回。左右子树都有返回值，则当前节点为 LCA。
代码实现：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
}4. 实现栈的最小值函数
题目描述：
设计一个支持 push，pop，top 操作，并能在常数时间内检索最小元素的栈。
示例：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // 返回 -3
minStack.pop();
minStack.top(); // 返回 0
minStack.getMin(); // 返回 -2解答：
使用两个栈，一个存储元素，一个存储最小值。
代码实现：
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (minStack.isEmpty() || x <= minStack.peek()) {
minStack.push(x);
}
}
public void pop() {
if (stack.pop().equals(minStack.peek())) {
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}5. 用两个栈实现队列
题目描述：
使用两个栈实现一个队列，支持队列的基本操作 push 和 pop。
示例：
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false解答：
使用两个栈 stack1 和 stack2，一个用于入队，一个用于出队。
代码实现：
class MyQueue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int peek() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}6. 二叉树的层序遍历
题目描述：
给定一个二叉树，返回其节点值的层序遍历。
示例：
输入: [3,9,20,null,null,15,7]
输出:
[
[3],
[9,20],
[15,7]
]解答：
使用队列进行广度优先搜索（BFS）。
代码实现：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
res.add(level);
}
return res;
}7. 判断二叉树是否对称
题目描述：
给定一个二叉树，检查它是否是镜像对称的。
示例：
输入: [1,2,2,3,4,4,3]
输出: true解答：
递归比较左右子树，或者使用队列进行迭代比较。
代码实现（递归）：
public boolean isSymmetric(TreeNode root) {
return root == null || isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null) return false;
return (left.val == right.val)
&& isMirror(left.left, right.right)
&& isMirror(left.right, right.left);
}8. 实现二叉搜索树的插入操作
题目描述：
在二叉搜索树中插入一个新节点，并返回根节点。
示例：
输入: root = [4,2,7,1,3], val = 5
输出: [4,2,7,1,3,5]解答：
递归或迭代遍历树，找到插入位置。
代码实现（递归）：
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}9. 哈希表实现
题目描述：
设计一个哈希映射（HashMap），支持 put、get 和 remove 操作。
解答：
使用数组加链表法（拉链法）处理哈希冲突。
代码实现（简化版）：
class MyHashMap {
private static final int SIZE = 1000;
private LinkedList<Node>[] map;
class Node {
int key, value;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public MyHashMap() {
map = new LinkedList[SIZE];
}
public void put(int key, int value) {
int hash = key % SIZE;
if (map[hash] == null) map[hash] = new LinkedList<>();
for (Node node : map[hash]) {
if (node.key == key) {
node.value = value;
return;
}
}
map[hash].add(new Node(key, value));
}
public int get(int key) {
int hash = key % SIZE;
if (map[hash] == null) return -1;
for (Node node : map[hash]) {
if (node.key == key) return node.value;
}
return -1;
}
public void remove(int key) {
int hash = key % SIZE;
if (map[hash] == null) return;
map[hash].removeIf(node -> node.key == key);
}
}10. 实现二叉堆（优先队列）
题目描述：
实现一个二叉最小堆，支持插入和删除最小元素操作。
解答：
使用数组表示二叉堆，维护堆的性质。
代码实现（简化版）：
class MinHeap {
private int[] heap;
private int size;
public MinHeap(int capacity) {
heap = new int[capacity];
size = 0;
}
public void insert(int val) {
if (size == heap.length) throw new RuntimeException("Heap is full");
heap[size] = val;
siftUp(size);
size++;
}
public int removeMin() {
if (size == 0) throw new RuntimeException("Heap is empty");
int min = heap[0];
heap[0] = heap[--size];
siftDown(0);
return min;
}
private void siftUp(int i) {
while (i > 0 && heap[i] < heap[(i - 1) / 2]) {
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
private void siftDown(int i) {
while (2 * i + 1 < size) {
int minChild = 2 * i + 1;
if (minChild + 1 < size && heap[minChild + 1] < heap[minChild]) {
minChild++;
}
if (heap[i] <= heap[minChild]) break;
swap(i, minChild);
i = minChild;
}
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}11. 实现 Trie（前缀树）
题目描述：
实现一个 Trie（前缀树），支持插入、搜索和前缀匹配。
解答：
使用多叉树，每个节点包含 26 个子节点（假设仅小写字母）。
代码实现：
class TrieNode {
boolean isWord;
TrieNode[] children = new TrieNode[26];
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (node.children[i] == null) node.children[i] = new TrieNode();
node = node.children[i];
}
node.isWord = true;
}
public boolean search(String word) {
TrieNode node = searchNode(word);
return node != null && node.isWord;
}
public boolean startsWith(String prefix) {
return searchNode(prefix) != null;
}
private TrieNode searchNode(String s) {
TrieNode node = root;
for (char c : s.toCharArray()) {
int i = c - 'a';
if (node.children[i] == null) return null;
node = node.children[i];
}
return node;
}
}12. 判断是否是二叉搜索树
题目描述：
给定一个二叉树，判断其是否是有效的二叉搜索树（BST）。
解答：
中序遍历二叉树，检查节点值是否按升序排列。
代码实现：
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
private boolean isValidBST(TreeNode node, Integer lower, Integer upper) {
if (node == null) return true;
int val = node.val;
if (lower != null && val <= lower) return false;
if (upper != null && val >= upper) return false;
if (!isValidBST(node.right, val, upper)) return false;
if (!isValidBST(node.left, lower, val)) return false;
return true;
}13. 实现图的深度优先搜索和广度优先搜索
题目描述：
在图结构中，实现深度优先搜索（DFS）和广度优先搜索（BFS）。
解答：
使用递归实现 DFS，使用队列实现 BFS。
代码实现（DFS）：
public void dfs(GraphNode node, Set<GraphNode> visited) {
if (node == null || visited.contains(node)) return;
visited.add(node);
// 处理节点
for (GraphNode neighbor : node.neighbors) {
dfs(neighbor, visited);
}
}代码实现（BFS）：
public void bfs(GraphNode start) {
Queue<GraphNode> queue = new LinkedList<>();
Set<GraphNode> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
while (!queue.isEmpty()) {
GraphNode node = queue.poll();
// 处理节点
for (GraphNode neighbor : node.neighbors) {
if (!visited.contains(neighbor)) {
queue.offer(neighbor);
visited.add(neighbor);
}
}
}
}14. 找出数组中第 K 大的元素
题目描述：
给定一个未排序的整数数组，找到其中第 K 大的元素。
示例：
输入: [3,2,1,5,6,4], k = 2
输出: 5解答：
使用快速选择算法，或者最小堆。
代码实现（快速选择）：
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
private int quickSelect(int[] nums, int left, int right, int k) {
if (left == right) return nums[left];
int pivotIndex = partition(nums, left, right);
if (pivotIndex == k) {
return nums[k];
} else if (pivotIndex < k) {
return quickSelect(nums, pivotIndex + 1, right, k);
} else {
return quickSelect(nums, left, pivotIndex - 1, k);
}
}
private int partition(int[] nums, int left, int right) {
int pivot = nums[right];
int storeIndex = left;
for (int i = left; i < right; i++) {
if (nums[i] < pivot) {
swap(nums, storeIndex, i);
storeIndex++;
}
}
swap(nums, storeIndex, right);
return storeIndex;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}15. 实现字符串匹配的 KMP 算法
题目描述：
实现 KMP 算法，在字符串中查找模式串出现的位置。
解答：
先计算模式串的部分匹配表（next 数组），然后使用 KMP 算法进行匹配。
代码实现：
public int strStr(String haystack, String needle) {
if (needle.isEmpty()) return 0;
int[] lps = computeLPSArray(needle);
int i = 0, j = 0;
while (i < haystack.length()) {
if (haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
if (j == needle.length()) return i - j;
} else if (j > 0) {
j = lps[j - 1];
} else {
i++;
}
}
return -1;
}
private int[] computeLPSArray(String pattern) {
int[] lps = new int[pattern.length()];
int len = 0, i = 1;
while (i < pattern.length()) {
if (pattern.charAt(i) == pattern.charAt(len)) {
lps[i++] = ++len;
} else if (len > 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
return lps;
}总结
以上列举了常见的 Java 数据结构面试题及其解答，涵盖了链表、树、图、栈、队列、堆、哈希表和字符串匹配等主题。在面试中，不仅要熟练掌握各种数据结构的实现和应用，还要能够根据具体问题选择合适的数据结构和算法。
建议在平时多练习相关题目，例如 LeetCode、牛客网等平台上的数据结构题，深入理解数据结构的原理和实现，提高编程能力和面试表现。
