算法与数据结构进阶
概述
算法与数据结构是Java高级开发工程师必须掌握的基础知识，不仅在面试中经常考察，在实际工作中也是解决复杂问题和系统优化的重要工具。本文深入讲解常用算法、数据结构的实现和应用场景。
核心面试问题
1. 高级数据结构实现
面试问题：如何实现一个线程安全的LRU缓存？手写红黑树的插入操作？
LRU缓存实现
// 线程安全的LRU缓存实现
public class ThreadSafeLRUCache<K, V> {
private final int capacity;
private final Map<K, Node<K, V>> cache;
private final Node<K, V> head;
private final Node<K, V> tail;
private final ReentrantReadWriteLock lock;
private final Lock readLock;
private final Lock writeLock;
private static class Node<K, V> {
K key;
V value;
Node<K, V> prev;
Node<K, V> next;
Node(K key, V value) {
this.key = key;
this.value = value;
}
}
public ThreadSafeLRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.lock = new ReentrantReadWriteLock();
this.readLock = lock.readLock();
this.writeLock = lock.writeLock();
// 创建虚拟头尾节点
this.head = new Node<>(null, null);
this.tail = new Node<>(null, null);
head.next = tail;
tail.prev = head;
}
public V get(K key) {
readLock.lock();
try {
Node<K, V> node = cache.get(key);
if (node == null) {
return null;
}
// 需要升级为写锁来移动节点
readLock.unlock();
writeLock.lock();
try {
// 双重检查
node = cache.get(key);
if (node != null) {
moveToHead(node);
return node.value;
}
return null;
} finally {
readLock.lock(); // 降级为读锁
writeLock.unlock();
}
} finally {
readLock.unlock();
}
}
public void put(K key, V value) {
writeLock.lock();
try {
Node<K, V> node = cache.get(key);
if (node != null) {
// 更新现有节点
node.value = value;
moveToHead(node);
} else {
// 插入新节点
Node<K, V> newNode = new Node<>(key, value);
if (cache.size() >= capacity) {
// 移除最少使用的节点
Node<K, V> lastNode = tail.prev;
removeNode(lastNode);
cache.remove(lastNode.key);
}
addToHead(newNode);
cache.put(key, newNode);
}
} finally {
writeLock.unlock();
}
}
private void moveToHead(Node<K, V> node) {
removeNode(node);
addToHead(node);
}
private void removeNode(Node<K, V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addToHead(Node<K, V> node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
public int size() {
readLock.lock();
try {
return cache.size();
} finally {
readLock.unlock();
}
}
public void clear() {
writeLock.lock();
try {
cache.clear();
head.next = tail;
tail.prev = head;
} finally {
writeLock.unlock();
}
}
}
// 使用ConcurrentHashMap的简化版本
public class SimpleLRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
private final Object lock = new Object();
public SimpleLRUCache(int capacity) {
super(capacity + 1, 1.0f, true); // accessOrder = true
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
@Override
public V get(Object key) {
synchronized (lock) {
return super.get(key);
}
}
@Override
public V put(K key, V value) {
synchronized (lock) {
return super.put(key, value);
}
}
}
红黑树实现
// 红黑树实现
public class RedBlackTree<T extends Comparable<T>> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node<T> root;
private static class Node<T> {
T data;
Node<T> left;
Node<T> right;
Node<T> parent;
boolean color;
Node(T data, boolean color, Node<T> parent) {
this.data = data;
this.color = color;
this.parent = parent;
}
}
public void insert(T data) {
Node<T> newNode = new Node<>(data, RED, null);
if (root == null) {
root = newNode;
root.color = BLACK;
return;
}
// 标准BST插入
Node<T> current = root;
Node<T> parent = null;
while (current != null) {
parent = current;
int cmp = data.compareTo(current.data);
if (cmp < 0) {
current = current.left;
} else if (cmp > 0) {
current = current.right;
} else {
// 数据已存在，更新值
current.data = data;
return;
}
}
newNode.parent = parent;
int cmp = data.compareTo(parent.data);
if (cmp < 0) {
parent.left = newNode;
} else {
parent.right = newNode;
}
// 修复红黑树性质
fixInsert(newNode);
}
private void fixInsert(Node<T> node) {
// 案例1：节点是根节点
if (node.parent == null) {
node.color = BLACK;
return;
}
// 案例2：父节点是黑色
if (node.parent.color == BLACK) {
return;
}
Node<T> parent = node.parent;
Node<T> grandparent = parent.parent;
Node<T> uncle = getUncle(node);
// 案例3：父节点和叔叔节点都是红色
if (uncle != null && uncle.color == RED) {
parent.color = BLACK;
uncle.color = BLACK;
grandparent.color = RED;
fixInsert(grandparent);
return;
}
// 案例4：父节点是红色，叔叔节点是黑色（或不存在）
// 需要旋转
if (parent == grandparent.left) {
if (node == parent.right) {
// 左右情况：先左旋父节点
rotateLeft(parent);
node = parent;
parent = node.parent;
}
// 左左情况：右旋祖父节点
rotateRight(grandparent);
parent.color = BLACK;
grandparent.color = RED;
} else {
if (node == parent.left) {
// 右左情况：先右旋父节点
rotateRight(parent);
node = parent;
parent = node.parent;
}
// 右右情况：左旋祖父节点
rotateLeft(grandparent);
parent.color = BLACK;
grandparent.color = RED;
}
}
private Node<T> getUncle(Node<T> node) {
Node<T> grandparent = node.parent.parent;
if (grandparent == null) {
return null;
}
if (node.parent == grandparent.left) {
return grandparent.right;
} else {
return grandparent.left;
}
}
private void rotateLeft(Node<T> node) {
Node<T> rightChild = node.right;
node.right = rightChild.left;
if (rightChild.left != null) {
rightChild.left.parent = node;
}
rightChild.parent = node.parent;
if (node.parent == null) {
root = rightChild;
} else if (node == node.parent.left) {
node.parent.left = rightChild;
} else {
node.parent.right = rightChild;
}
rightChild.left = node;
node.parent = rightChild;
}
private void rotateRight(Node<T> node) {
Node<T> leftChild = node.left;
node.left = leftChild.right;
if (leftChild.right != null) {
leftChild.right.parent = node;
}
leftChild.parent = node.parent;
if (node.parent == null) {
root = leftChild;
} else if (node == node.parent.right) {
node.parent.right = leftChild;
} else {
node.parent.left = leftChild;
}
leftChild.right = node;
node.parent = leftChild;
}
public boolean search(T data) {
return search(root, data) != null;
}
private Node<T> search(Node<T> node, T data) {
if (node == null) {
return null;
}
int cmp = data.compareTo(node.data);
if (cmp == 0) {
return node;
} else if (cmp < 0) {
return search(node.left, data);
} else {
return search(node.right, data);
}
}
public void inorderTraversal() {
inorderTraversal(root);
System.out.println();
}
private void inorderTraversal(Node<T> node) {
if (node != null) {
inorderTraversal(node.left);
System.out.print(node.data + "(" + (node.color ? "R" : "B") + ") ");
inorderTraversal(node.right);
}
}
}
并发安全的跳表实现
// 跳表实现（类似ConcurrentSkipListMap）
public class ConcurrentSkipList<T extends Comparable<T>> {
private static final int MAX_LEVEL = 32;
private static final double P = 0.5;
private final Node<T> header;
private volatile int level;
private final Random random;
private static class Node<T> {
final T value;
final Node<T>[] forward;
volatile boolean marked;
@SuppressWarnings("unchecked")
Node(T value, int level) {
this.value = value;
this.forward = new Node[level + 1];
this.marked = false;
}
}
@SuppressWarnings("unchecked")
public ConcurrentSkipList() {
this.header = new Node<>(null, MAX_LEVEL);
this.level = 0;
this.random = new Random();
}
public boolean contains(T value) {
return findNode(value) != null;
}
private Node<T> findNode(T value) {
Node<T> current = header;
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null &&
!current.forward[i].marked &&
current.forward[i].value.compareTo(value) < 0) {
current = current.forward[i];
}
}
current = current.forward[0];
if (current != null && !current.marked && current.value.equals(value)) {
return current;
}
return null;
}
public boolean add(T value) {
Node<T>[] update = new Node[MAX_LEVEL + 1];
Node<T> current = header;
// 找到插入位置
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null &&
!current.forward[i].marked &&
current.forward[i].value.compareTo(value) < 0) {
current = current.forward[i];
}
update[i] = current;
}
current = current.forward[0];
// 检查是否已存在
if (current != null && !current.marked && current.value.equals(value)) {
return false;
}
// 生成新节点的层级
int newLevel = randomLevel();
if (newLevel > level) {
for (int i = level + 1; i <= newLevel; i++) {
update[i] = header;
}
level = newLevel;
}
Node<T> newNode = new Node<>(value, newLevel);
// 插入新节点
for (int i = 0; i <= newLevel; i++) {
newNode.forward[i] = update[i].forward[i];
update[i].forward[i] = newNode;
}
return true;
}
public boolean remove(T value) {
Node<T>[] update = new Node[MAX_LEVEL + 1];
Node<T> current = header;
// 找到要删除的节点
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null &&
!current.forward[i].marked &&
current.forward[i].value.compareTo(value) < 0) {
current = current.forward[i];
}
update[i] = current;
}
current = current.forward[0];
if (current == null || current.marked || !current.value.equals(value)) {
return false;
}
// 标记为删除
current.marked = true;
// 更新指针
for (int i = 0; i <= level; i++) {
if (update[i].forward[i] != current) {
break;
}
update[i].forward[i] = current.forward[i];
}
// 更新层级
while (level > 0 && header.forward[level] == null) {
level--;
}
return true;
}
private int randomLevel() {
int level = 0;
while (random.nextDouble() < P && level < MAX_LEVEL) {
level++;
}
return level;
}
public void printList() {
for (int i = level; i >= 0; i--) {
System.out.print("Level " + i + ": ");
Node<T> current = header.forward[i];
while (current != null) {
if (!current.marked) {
System.out.print(current.value + " ");
}
current = current.forward[i];
}
System.out.println();
}
}
}
2. 高级算法实现
面试问题：实现KMP字符串匹配算法，设计一个高效的topK算法？
字符串匹配算法
public class StringMatchingAlgorithms {
// KMP算法实现
public static class KMP {
public static int search(String text, String pattern) {
if (pattern.isEmpty()) return 0;
if (text.length() < pattern.length()) return -1;
int[] lps = computeLPS(pattern);
int i = 0; // text的索引
int j = 0; // pattern的索引
while (i < text.length()) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
}
if (j == pattern.length()) {
return i - j; // 找到匹配
} else if (i < text.length() && text.charAt(i) != pattern.charAt(j)) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return -1; // 未找到匹配
}
private static int[] computeLPS(String pattern) {
int[] lps = new int[pattern.length()];
int len = 0; // 最长相等前后缀的长度
int i = 1;
while (i < pattern.length()) {
if (pattern.charAt(i) == pattern.charAt(len)) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
// 查找所有匹配位置
public static List<Integer> searchAll(String text, String pattern) {
List<Integer> results = new ArrayList<>();
if (pattern.isEmpty()) return results;
int[] lps = computeLPS(pattern);
int i = 0, j = 0;
while (i < text.length()) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
}
if (j == pattern.length()) {
results.add(i - j);
j = lps[j - 1];
} else if (i < text.length() && text.charAt(i) != pattern.charAt(j)) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return results;
}
}
// Rabin-Karp算法（滚动哈希）
public static class RabinKarp {
private static final int PRIME = 101;
public static List<Integer> search(String text, String pattern) {
List<Integer> results = new ArrayList<>();
int m = pattern.length();
int n = text.length();
if (m > n) return results;
// 计算模式字符串的哈希值
long patternHash = hash(pattern, m);
long textHash = hash(text, m);
// 滑动窗口
for (int i = 0; i <= n - m; i++) {
// 检查哈希值
if (patternHash == textHash) {
// 哈希值相等，需要逐字符比较确认
if (text.substring(i, i + m).equals(pattern)) {
results.add(i);
}
}
// 计算下一个窗口的哈希值
if (i < n - m) {
textHash = rollingHash(textHash, text.charAt(i),
text.charAt(i + m), m);
}
}
return results;
}
private static long hash(String str, int length) {
long hash = 0;
for (int i = 0; i < length; i++) {
hash += str.charAt(i) * Math.pow(PRIME, i);
}
return hash;
}
private static long rollingHash(long oldHash, char oldChar, char newChar, int length) {
long newHash = (oldHash - oldChar) / PRIME;
newHash += newChar * Math.pow(PRIME, length - 1);
return newHash;
}
}
// AC自动机（多模式匹配）
public static class AhoCorasick {
private static class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
TrieNode failure = null;
List<String> output = new ArrayList<>();
}
private TrieNode root;
public AhoCorasick(List<String> patterns) {
buildTrie(patterns);
buildFailureFunction();
}
private void buildTrie(List<String> patterns) {
root = new TrieNode();
for (String pattern : patterns) {
TrieNode current = root;
for (char c : pattern.toCharArray()) {
current.children.putIfAbsent(c, new TrieNode());
current = current.children.get(c);
}
current.output.add(pattern);
}
}
private void buildFailureFunction() {
Queue<TrieNode> queue = new LinkedList<>();
// 第一层的失效指针都指向根节点
for (TrieNode child : root.children.values()) {
child.failure = root;
queue.offer(child);
}
while (!queue.isEmpty()) {
TrieNode current = queue.poll();
for (Map.Entry<Character, TrieNode> entry : current.children.entrySet()) {
char c = entry.getKey();
TrieNode child = entry.getValue();
// 构建失效指针
TrieNode failure = current.failure;
while (failure != null && !failure.children.containsKey(c)) {
failure = failure.failure;
}
if (failure != null) {
child.failure = failure.children.get(c);
} else {
child.failure = root;
}
// 合并输出
child.output.addAll(child.failure.output);
queue.offer(child);
}
}
}
public List<MatchResult> search(String text) {
List<MatchResult> results = new ArrayList<>();
TrieNode current = root;
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
// 沿着失效指针找到匹配的转移
while (current != null && !current.children.containsKey(c)) {
current = current.failure;
}
if (current != null) {
current = current.children.get(c);
} else {
current = root;
}
// 输出所有匹配的模式
for (String pattern : current.output) {
results.add(new MatchResult(pattern, i - pattern.length() + 1));
}
}
return results;
}
public static class MatchResult {
public final String pattern;
public final int position;
public MatchResult(String pattern, int position) {
this.pattern = pattern;
this.position = position;
}
@Override
public String toString() {
return "Pattern: " + pattern + ", Position: " + position;
}
}
}
}
TopK算法实现
public class TopKAlgorithms {
// 使用小顶堆的TopK实现
public static class HeapBasedTopK<T extends Comparable<T>> {
private final int k;
private final PriorityQueue<T> minHeap;
public HeapBasedTopK(int k) {
this.k = k;
this.minHeap = new PriorityQueue<>(k);
}
public void add(T element) {
if (minHeap.size() < k) {
minHeap.offer(element);
} else if (element.compareTo(minHeap.peek()) > 0) {
minHeap.poll();
minHeap.offer(element);
}
}
public List<T> getTopK() {
List<T> result = new ArrayList<>(minHeap);
result.sort(Collections.reverseOrder()); // 降序排列
return result;
}
}
// 快速选择算法（Quick Select）
public static class QuickSelect {
public static int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
private static int quickSelect(int[] nums, int left, int right, int kIndex) {
if (left == right) {
return nums[left];
}
// 随机选择基准点，避免最坏情况
Random random = new Random();
int pivotIndex = left + random.nextInt(right - left + 1);
pivotIndex = partition(nums, left, right, pivotIndex);
if (kIndex == pivotIndex) {
return nums[kIndex];
} else if (kIndex < pivotIndex) {
return quickSelect(nums, left, pivotIndex - 1, kIndex);
} else {
return quickSelect(nums, pivotIndex + 1, right, kIndex);
}
}
private static int partition(int[] nums, int left, int right, int pivotIndex) {
int pivotValue = nums[pivotIndex];
// 将基准移到末尾
swap(nums, pivotIndex, right);
int storeIndex = left;
for (int i = left; i < right; i++) {
if (nums[i] < pivotValue) {
swap(nums, storeIndex, i);
storeIndex++;
}
}
// 将基准移到正确位置
swap(nums, storeIndex, right);
return storeIndex;
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// 获取TopK元素
public static List<Integer> getTopK(int[] nums, int k) {
if (k <= 0 || k > nums.length) {
return new ArrayList<>();
}
int[] copy = nums.clone();
int kthLargest = findKthLargest(copy, k);
List<Integer> result = new ArrayList<>();
int count = 0;
for (int num : nums) {
if (num > kthLargest || (num == kthLargest && count < k)) {
result.add(num);
if (num == kthLargest) {
count++;
}
}
}
return result;
}
}
// 分布式TopK算法
public static class DistributedTopK {
// 模拟分布式环境下的TopK计算
public static List<Integer> distributedTopK(List<List<Integer>> partitions, int k) {
// 第一阶段：每个分区计算本地TopK
List<List<Integer>> localTopKs = partitions.parallelStream()
.map(partition -> getLocalTopK(partition, k))
.collect(Collectors.toList());
// 第二阶段：合并所有本地TopK结果
List<Integer> mergedList = localTopKs.stream()
.flatMap(List::stream)
.collect(Collectors.toList());
// 第三阶段：从合并结果中选择全局TopK
return QuickSelect.getTopK(mergedList.stream().mapToInt(i -> i).toArray(), k);
}
private static List<Integer> getLocalTopK(List<Integer> partition, int k) {
HeapBasedTopK<Integer> topK = new HeapBasedTopK<>(k);
for (Integer num : partition) {
topK.add(num);
}
return topK.getTopK();
}
}
// 流式TopK算法（适用于数据流场景）
public static class StreamingTopK<T extends Comparable<T>> {
private final int k;
private final PriorityQueue<T> minHeap;
private final Map<T, Integer> counts;
public StreamingTopK(int k) {
this.k = k;
this.minHeap = new PriorityQueue<>(k);
this.counts = new HashMap<>();
}
public void process(T element) {
counts.put(element, counts.getOrDefault(element, 0) + 1);
if (!minHeap.contains(element)) {
if (minHeap.size() < k) {
minHeap.offer(element);
} else if (element.compareTo(minHeap.peek()) > 0) {
minHeap.poll();
minHeap.offer(element);
}
}
}
public List<TopKItem<T>> getCurrentTopK() {
return minHeap.stream()
.map(item -> new TopKItem<>(item, counts.get(item)))
.sorted((a, b) -> b.count - a.count)
.collect(Collectors.toList());
}
public static class TopKItem<T> {
public final T item;
public final int count;
public TopKItem(T item, int count) {
this.item = item;
this.count = count;
}
@Override
public String toString() {
return item + "(" + count + ")";
}
}
}
}
3. 动态规划经典问题
面试问题：最长公共子序列、背包问题、股票买卖问题的DP解法？
经典DP问题实现
public class DynamicProgramming {
// 最长公共子序列（LCS）
public static class LCS {
public static int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
// dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的LCS长度
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
// 返回具体的LCS字符串
public static String getLCSString(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
// 构建DP表
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// 回溯构建LCS字符串
StringBuilder lcs = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
lcs.append(text1.charAt(i - 1));
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return lcs.reverse().toString();
}
// 空间优化版本
public static int longestCommonSubsequenceOptimized(String text1, String text2) {
int m = text1.length();
int n = text2.length();
// 只需要两行
int[] prev = new int[n + 1];
int[] curr = new int[n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
curr[j] = prev[j - 1] + 1;
} else {
curr[j] = Math.max(prev[j], curr[j - 1]);
}
}
// 交换数组
int[] temp = prev;
prev = curr;
curr = temp;
}
return prev[n];
}
}
// 0-1背包问题
public static class Knapsack {
public static int knapsack01(int[] weights, int[] values, int capacity) {
int n = weights.length;
// dp[i][w] 表示前i个物品在容量为w时的最大价值
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= capacity; w++) {
// 不选择第i个物品
dp[i][w] = dp[i - 1][w];
// 选择第i个物品（如果能放下）
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[n][capacity];
}
// 空间优化版本
public static int knapsack01Optimized(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weights.length; i++) {
// 逆序遍历，避免重复使用
for (int w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
// 返回选择的物品
public static List<Integer> getKnapsackItems(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
// 构建DP表
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= capacity; w++) {
dp[i][w] = dp[i - 1][w];
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]);
}
}
}
// 回溯找出选择的物品
List<Integer> selectedItems = new ArrayList<>();
int w = capacity;
for (int i = n; i > 0 && w > 0; i--) {
if (dp[i][w] != dp[i - 1][w]) {
selectedItems.add(i - 1); // 物品索引
w -= weights[i - 1];
}
}
Collections.reverse(selectedItems);
return selectedItems;
}
// 完全背包问题
public static int unboundedKnapsack(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weights.length; i++) {
for (int w = weights[i]; w <= capacity; w++) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
}
// 股票买卖问题
public static class StockTrading {
// 最多一次交易
public static int maxProfitOneTransaction(int[] prices) {
if (prices.length <= 1) return 0;
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
return maxProfit;
}
// 无限次交易
public static int maxProfitUnlimited(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
// 最多k次交易
public static int maxProfitKTransactions(int k, int[] prices) {
if (prices.length <= 1 || k == 0) return 0;
// 如果k很大，等同于无限次交易
if (k >= prices.length / 2) {
return maxProfitUnlimited(prices);
}
// dp[i][j][0] 表示第i天，最多j次交易，当前不持有股票的最大利润
// dp[i][j][1] 表示第i天，最多j次交易，当前持有股票的最大利润
int[][][] dp = new int[prices.length][k + 1][2];
for (int i = 0; i < prices.length; i++) {
for (int j = 0; j <= k; j++) {
if (i == 0) {
dp[i][j][0] = 0;
dp[i][j][1] = -prices[i];
continue;
}
// 不持有股票：昨天不持有或今天卖出
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
// 持有股票：昨天持有或今天买入
if (j > 0) {
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
} else {
dp[i][j][1] = dp[i - 1][j][1];
}
}
}
return dp[prices.length - 1][k][0];
}
// 含冷冻期的股票交易
public static int maxProfitWithCooldown(int[] prices) {
if (prices.length <= 1) return 0;
// hold: 持有股票, sold: 刚卖出股票（冷冻期）, rest: 不持有股票（非冷冻期）
int hold = -prices[0];
int sold = 0;
int rest = 0;
for (int i = 1; i < prices.length; i++) {
int prevHold = hold;
int prevSold = sold;
int prevRest = rest;
hold = Math.max(prevHold, prevRest - prices[i]);
sold = prevHold + prices[i];
rest = Math.max(prevRest, prevSold);
}
return Math.max(sold, rest);
}
// 含手续费的股票交易
public static int maxProfitWithFee(int[] prices, int fee) {
int hold = -prices[0];
int sold = 0;
for (int i = 1; i < prices.length; i++) {
hold = Math.max(hold, sold - prices[i]);
sold = Math.max(sold, hold + prices[i] - fee);
}
return sold;
}
}
// 编辑距离
public static class EditDistance {
public static int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
// dp[i][j] 表示 word1[0..i-1] 转换为 word2[0..j-1] 的最小操作数
int[][] dp = new int[m + 1][n + 1];
// 初始化
for (int i = 0; i <= m; i++) {
dp[i][0] = i; // 删除i个字符
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j; // 插入j个字符
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1]; // 不需要操作
} else {
dp[i][j] = Math.min(
Math.min(
dp[i - 1][j] + 1, // 删除
dp[i][j - 1] + 1 // 插入
),
dp[i - 1][j - 1] + 1 // 替换
);
}
}
}
return dp[m][n];
}
// 返回具体的操作序列
public static List<String> getEditOperations(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// 构建DP表
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1),
dp[i - 1][j - 1] + 1);
}
}
}
// 回溯构建操作序列
List<String> operations = new ArrayList<>();
int i = m, j = n;
while (i > 0 || j > 0) {
if (i > 0 && j > 0 && word1.charAt(i - 1) == word2.charAt(j - 1)) {
i--;
j--;
} else if (i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] + 1) {
operations.add("Replace " + word1.charAt(i - 1) + " with " + word2.charAt(j - 1));
i--;
j--;
} else if (i > 0 && dp[i][j] == dp[i - 1][j] + 1) {
operations.add("Delete " + word1.charAt(i - 1));
i--;
} else {
operations.add("Insert " + word2.charAt(j - 1));
j--;
}
}
Collections.reverse(operations);
return operations;
}
}
}
4. 图算法高级应用
面试问题：实现Dijkstra算法、检测图中的环、最小生成树算法？
图算法实现
public class GraphAlgorithms {
// 图的表示
public static class Graph {
private final int vertices;
private final List<List<Edge>> adjList;
public Graph(int vertices) {
this.vertices = vertices;
this.adjList = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
adjList.add(new ArrayList<>());
}
}
public void addEdge(int from, int to, int weight) {
adjList.get(from).add(new Edge(to, weight));
}
public void addUndirectedEdge(int u, int v, int weight) {
adjList.get(u).add(new Edge(v, weight));
adjList.get(v).add(new Edge(u, weight));
}
public List<Edge> getNeighbors(int vertex) {
return adjList.get(vertex);
}
public int getVertices() {
return vertices;
}
public static class Edge {
public final int to;
public final int weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
}
// Dijkstra最短路径算法
public static class Dijkstra {
public static class Result {
public final int[] distances;
public final int[] predecessors;
public Result(int[] distances, int[] predecessors) {
this.distances = distances;
this.predecessors = predecessors;
}
public List<Integer> getPath(int target) {
List<Integer> path = new ArrayList<>();
int current = target;
while (current != -1) {
path.add(current);
current = predecessors[current];
}
Collections.reverse(path);
return path;
}
}
public static Result shortestPath(Graph graph, int source) {
int n = graph.getVertices();
int[] distances = new int[n];
int[] predecessors = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(distances, Integer.MAX_VALUE);
Arrays.fill(predecessors, -1);
distances[source] = 0;
// 使用优先队列优化
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.distance));
pq.offer(new Node(source, 0));
while (!pq.isEmpty()) {
Node current = pq.poll();
int u = current.vertex;
if (visited[u]) continue;
visited[u] = true;
for (Graph.Edge edge : graph.getNeighbors(u)) {
int v = edge.to;
int weight = edge.weight;
if (!visited[v] && distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
predecessors[v] = u;
pq.offer(new Node(v, distances[v]));
}
}
}
return new Result(distances, predecessors);
}
private static class Node {
int vertex;
int distance;
Node(int vertex, int distance) {
this.vertex = vertex;
this.distance = distance;
}
}
}
// 环检测算法
public static class CycleDetection {
// 有向图环检测（DFS）
public static boolean hasCycleDirected(Graph graph) {
int n = graph.getVertices();
int[] color = new int[n]; // 0: white, 1: gray, 2: black
for (int i = 0; i < n; i++) {
if (color[i] == 0 && dfsHasCycle(graph, i, color)) {
return true;
}
}
return false;
}
private static boolean dfsHasCycle(Graph graph, int vertex, int[] color) {
color[vertex] = 1; // 标记为灰色
for (Graph.Edge edge : graph.getNeighbors(vertex)) {
int neighbor = edge.to;
if (color[neighbor] == 1) {
return true; // 找到后向边，存在环
}
if (color[neighbor] == 0 && dfsHasCycle(graph, neighbor, color)) {
return true;
}
}
color[vertex] = 2; // 标记为黑色
return false;
}
// 无向图环检测（并查集）
public static boolean hasCycleUndirected(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
if (uf.find(u) == uf.find(v)) {
return true; // 两个顶点已在同一连通分量中
}
uf.union(u, v);
}
return false;
}
public static class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
}
}
// 最小生成树算法
public static class MinimumSpanningTree {
// Kruskal算法
public static List<GraphEdge> kruskal(int n, List<GraphEdge> edges) {
List<GraphEdge> mst = new ArrayList<>();
// 按权重排序
edges.sort(Comparator.comparingInt(a -> a.weight));
CycleDetection.UnionFind uf = new CycleDetection.UnionFind(n);
for (GraphEdge edge : edges) {
if (uf.find(edge.from) != uf.find(edge.to)) {
uf.union(edge.from, edge.to);
mst.add(edge);
if (mst.size() == n - 1) {
break; // MST完成
}
}
}
return mst;
}
// Prim算法
public static List<GraphEdge> prim(Graph graph) {
int n = graph.getVertices();
List<GraphEdge> mst = new ArrayList<>();
boolean[] inMST = new boolean[n];
// 从顶点0开始
inMST[0] = true;
PriorityQueue<GraphEdge> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.weight));
// 添加顶点0的所有边
for (Graph.Edge edge : graph.getNeighbors(0)) {
pq.offer(new GraphEdge(0, edge.to, edge.weight));
}
while (!pq.isEmpty() && mst.size() < n - 1) {
GraphEdge edge = pq.poll();
if (inMST[edge.to]) {
continue; // 跳过已在MST中的顶点
}
mst.add(edge);
inMST[edge.to] = true;
// 添加新顶点的所有边
for (Graph.Edge neighbor : graph.getNeighbors(edge.to)) {
if (!inMST[neighbor.to]) {
pq.offer(new GraphEdge(edge.to, neighbor.to, neighbor.weight));
}
}
}
return mst;
}
public static class GraphEdge {
public final int from;
public final int to;
public final int weight;
public GraphEdge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public String toString() {
return "(" + from + "->" + to + ", " + weight + ")";
}
}
}
// 拓扑排序
public static class TopologicalSort {
public static List<Integer> topologicalSort(Graph graph) {
int n = graph.getVertices();
int[] indegree = new int[n];
// 计算入度
for (int i = 0; i < n; i++) {
for (Graph.Edge edge : graph.getNeighbors(i)) {
indegree[edge.to]++;
}
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
int current = queue.poll();
result.add(current);
for (Graph.Edge edge : graph.getNeighbors(current)) {
indegree[edge.to]--;
if (indegree[edge.to] == 0) {
queue.offer(edge.to);
}
}
}
// 检查是否存在环
if (result.size() != n) {
return null; // 存在环，无法进行拓扑排序
}
return result;
}
// DFS版本的拓扑排序
public static List<Integer> topologicalSortDFS(Graph graph) {
int n = graph.getVertices();
boolean[] visited = new boolean[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfsTopological(graph, i, visited, stack);
}
}
List<Integer> result = new ArrayList<>();
while (!stack.isEmpty()) {
result.add(stack.pop());
}
return result;
}
private static void dfsTopological(Graph graph, int vertex, boolean[] visited, Stack<Integer> stack) {
visited[vertex] = true;
for (Graph.Edge edge : graph.getNeighbors(vertex)) {
if (!visited[edge.to]) {
dfsTopological(graph, edge.to, visited, stack);
}
}
stack.push(vertex);
}
}
}
高频面试题目
1. 理论深度题目
Q: 红黑树和AVL树的区别？什么时候选择哪种？
A: 主要区别：
- 平衡性：AVL树严格平衡，红黑树近似平衡
- 旋转次数：AVL树插入时最多2次旋转，红黑树最多3次
- 查找性能：AVL树查找稍快，红黑树插入删除更快
- 应用场景：AVL树适合查找密集，红黑树适合插入删除频繁
Q: 时间复杂度和空间复杂度如何分析？
A: 复杂度分析方法：
- 时间复杂度：分析算法执行时间与输入规模的关系
- 空间复杂度：分析算法使用空间与输入规模的关系
- 最好/平均/最坏情况：全面分析算法性能
- 摊还分析：分析一系列操作的平均代价
2. 实战应用题目
Q: 如何设计一个支持高并发的排行榜系统？
答题要点：
- 数据结构选择：跳表、红黑树、堆的组合使用
- 分片策略：按分数区间或用户ID分片
- 缓存设计：多级缓存，定时更新
- 一致性保证：最终一致性，异步更新
- 性能优化：批量操作，预计算
Q: 海量数据下如何实现TopK？
答题要点：
- 分治策略：Map-Reduce模式处理大数据
- 内存优化：外部排序，分块处理
- 近似算法：Count-Min Sketch，HyperLogLog
- 流式处理：滑动窗口，增量更新
- 分布式计算：多机协作，结果合并
总结
算法与数据结构面试重点：
- 基础数据结构：数组、链表、栈、队列、树、图的实现和应用
- 高级数据结构：红黑树、跳表、并发数据结构的原理
- 算法设计：分治、动态规划、贪心、回溯等算法思想
- 复杂度分析：时间空间复杂度的准确分析
- 实际应用：能够将算法应用到具体业务场景中
建议通过大量练习巩固基础，重点理解算法思想和应用场景，能够快速选择合适的算法解决实际问题。