引言
编程面试是技术求职者面临的重大挑战之一。面试官往往通过一系列算法题来考察应聘者的编程能力、逻辑思维和问题解决技巧。本文将介绍10大常考的算法题，帮助求职者更好地准备技术面试，轻松应对各种挑战。
1. 排序算法
1.1 冒泡排序
基本概念
：冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
代码示例
：
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
1.2 快速排序
基本概念
：快速排序是一个分而治之的算法，它将原始数组分为较小的数组和较大的数组，然后递归地对这两个数组进行快速排序。
代码示例
：
“`java
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
## 2. 查找算法
### 2.1 二分查找
- **基本概念**：二分查找是一种在有序数组中查找特定元素的搜索算法。
- **代码示例**：
```java
public static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
3. 链表操作
3.1 链表反转
基本概念
：链表反转是将链表中的节点顺序颠倒。
代码示例
：
public static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
4. 栈和队列
4.1 栈实现队列
基本概念
：使用两个栈实现队列操作。
代码示例
：
public class TwoStacksQueue {
private Stack
private Stack
public TwoStacksQueue() {
stackIn = new Stack<>();
stackOut = new Stack<>();
}
public void enqueue(int value) {
stackIn.push(value);
}
public int dequeue() {
if (stackOut.isEmpty()) {
while (!stackIn.isEmpty()) {
stackOut.push(stackIn.pop());
}
}
return stackOut.pop();
}
}
5. 图算法
5.1 深度优先搜索（DFS）
基本概念
：DFS是一种用于遍历或搜索树或图的算法。
代码示例
：
public void dfs(TreeNode node) {
if (node == null) return;
visit(node);
dfs(node.left);
dfs(node.right);
}
6. 动态规划
6.1 最长公共子序列（LCS）
基本概念
：LCS是两个序列中公共子序列的最长长度。
代码示例
：
public static int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else 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];
}
7. 字符串处理
7.1 正则表达式匹配
基本概念
：正则表达式是一种用于匹配字符串中字符组合的模式。
代码示例
：
public static boolean isMatch(String text, String pattern) {
if (pattern.isEmpty()) return text.isEmpty();
boolean firstMatch = (!text.isEmpty() && pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.');
if (pattern.length() >= 2 && pattern.charAt(1) == ‘*’) {
return (isMatch(text, pattern.substring(2)) || (firstMatch && isMatch(text.substring(1), pattern)));
} else {
return firstMatch && isMatch(text.substring(1), pattern.substring(1));
}
}
8. 数据结构
8.1 哈希表
基本概念
：哈希表是一种基于键值对的数据结构，它通过哈希函数来存储和检索数据。
代码示例
：
public class HashTable {
private static final int INITIAL_CAPACITY = 16;
private static final double LOAD_FACTOR = 0.75;
private Entry[] table;
public HashTable() {
table = new Entry[INITIAL_CAPACITY];
}
private static class Entry {
final int hash;
final Object key;
Object value;
Entry next;
Entry(int hash, Object key, Object value, Entry next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
public void put(Object key, Object value) {
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry e = table[i]; e != null; e = e.next) {
if (e.hash == hash && e.key.equals(key)) {
e.value = value;
return;
}
}
addEntry(hash, key, value, i);
}
private void addEntry(int hash, Object key, Object value, int bucketNum) {
Entry e = table[bucketNum];
table[bucketNum] = new Entry(hash, key, value, e);
}
private int hash(Object x) {
return (x == null) ? 0 : x.hashCode();
}
private int indexFor(int hash, int length) {
return hash & (length – 1);
}
}
9. 系统设计
9.1 缓存设计
基本概念
：缓存是一种用于提高数据检索速度的数据结构。
代码示例
：
public class Cache {
private final int capacity;
private final LinkedList
private final Map
public Cache(int capacity) {
this.capacity = capacity;
this.list = new LinkedList<>();
this.map = new HashMap<>();
}
public void put(Object key, Object value) {
Node node = map.get(key);
if (node != null) {
node.value = value;
list.remove(node);
list.addFirst(node);
} else {
node = new Node(key, value);
map.put(key, node);
list.addFirst(node);
if (list.size() > capacity) {
Node removed = list.removeLast();
map.remove(removed.key);
}
}
}
public Object get(Object key) {
Node node = map.get(key);
if (node == null) {
return null;
} else {
list.remove(node);
list.addFirst(node);
return node.value;
}
}
private static class Node {
final Object key;
final Object value;
Node(Object key, Object value) {
this.key = key;
this.value = value;
}
}
}
10. 编程技巧
10.1 单例模式
基本概念
：单例模式确保一个类只有一个实例，并提供一个全局访问点。
代码示例
：
public class Singleton {
private static Singleton instance;
private Singleton() {}
public static Singleton getInstance() {
if (instance == null) {
instance = new Singleton();
}
return instance;
}
}
总结与展望
掌握这些常考的算法题对于提高编程能力和应对技术面试至关重要。通过不断练习和总结，求职者可以更好地准备面试，迎接未来的挑战。