Java版《算法分析与设计》期末代码题：全部考点+题型总结（万字详解，附完整代码）

Java版《算法分析与设计》期末代码题：全部考点+题型总结（万字详解，附完整代码）

适用对象：本科计算机专业期末考试复习 侧重点：手写Java代码，不考复杂底层证明 核心考点：递归、分治、贪心、动态规划、回溯、图算法、查找排序 分值分布：代码题一般6～10分一题，要求写方法/完整类、输出结果、分析复杂度 本文特色：每个考点均附完整可运行Java代码 + 复杂度分析 + 考试坑点提醒

目录

前言：期末考试到底考什么？

每到期末，算法分析与设计这门课总是让无数计算机专业的同学头疼。不同于数据结构侧重"会用"，算法课更强调 理解思想 和 手写代码 的能力。

根据多年期末考试的经验总结，算法分析与设计的期末代码题有以下规律：

• 基础小题（5分左右）：二分查找、并查集、归并merge函数、快排partition函数——写核心函数即可
• 中档大题（8～12分）：01背包、最长公共子序列（LCS）、回溯全排列、Dijkstra最短路径、Floyd多源最短路径
• 拔高题（10分以上）：N皇后、归并排序求逆序对、编辑距离、拓扑排序判环

考试写Java代码的通用要求：

下面我们就按照考点逐一展开，每个考点都给出完整可运行的Java代码、详细的思路分析、复杂度计算以及考试中容易踩的坑。

一、分治算法（必考高频）

1.1 核心思想

分治（Divide and Conquer）的核心思想可以用三步概括：

时间复杂度分析的核心工具是主定理（Master Theorem）：

对于递推式

T

(

n

)

=

a

T

(

n

/

b

)

+

f

(

n

)

T(n) = aT(n/b) + f(n)

T(n)=aT(n/b)+f(n)：

• 若 $f(n)=O(n^{{\log }_{b}a-ϵ})$
• 若 $f(n)=\Theta (n^{{\log }_{b}a})$
• 若 $f(n)=\Omega (n^{{\log }_{b}a+ϵ})$

1.2 二分查找（最基础，必会）

题目描述：给定一个有序数组 nums 和目标值 target，查找 target 在数组中的下标，不存在则返回 -1。

非递归版本：

public class BinarySearch {

/**
* 基础二分查找 – 非递归版本
* 时间复杂度：O(log n)
* 空间复杂度：O(1)
*/
public static int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0) return –1;

int left = 0, right = nums.length – 1;
while (left <= right) {
int mid = left + (right – left) / 2; // 防止溢出！不要写 (left + right) / 2
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid – 1;
}
}
return –1;
}

/**
* 二分查找 – 递归版本
* 时间复杂度：O(log n)
* 空间复杂度：O(log n)（递归栈）
*/
public static int binarySearchRecursive(int[] nums, int target, int left, int right) {
if (left > right) return –1;

int mid = left + (right – left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
return binarySearchRecursive(nums, target, mid + 1, right);
} else {
return binarySearchRecursive(nums, target, left, mid – 1);
}
}

/**
* 进阶：查找第一个等于target的位置（高频变体）
* 时间复杂度：O(log n)
*/
public static int findFirst(int[] nums, int target) {
int left = 0, right = nums.length – 1;
int result = –1;
while (left <= right) {
int mid = left + (right – left) / 2;
if (nums[mid] == target) {
result = mid; // 记录当前位置
right = mid – 1; // 继续往左找
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid – 1;
}
}
return result;
}

/**
* 进阶：查找最后一个等于target的位置（高频变体）
* 时间复杂度：O(log n)
*/
public static int findLast(int[] nums, int target) {
int left = 0, right = nums.length – 1;
int result = –1;
while (left <= right) {
int mid = left + (right – left) / 2;
if (nums[mid] == target) {
result = mid; // 记录当前位置
left = mid + 1; // 继续往右找
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid – 1;
}
}
return result;
}

public static void main(String[] args) {
int[] nums = {1, 2, 2, 2, 3, 4, 5};
System.out.println("基础查找: " + binarySearch(nums, 2)); // 输出: 某个2的下标
System.out.println("第一个2: " + findFirst(nums, 2)); // 输出: 1
System.out.println("最后一个2: " + findLast(nums, 2)); // 输出: 3
System.out.println("查找6: " + binarySearch(nums, 6)); // 输出: -1
}
}

⚠️ 考试坑点：

1.3 归并排序（超级高频，尤其是求逆序对）

题目描述：使用分治思想对数组进行排序。

public class MergeSort {

/**
* 归并排序主方法
* 时间复杂度：O(n log n)
* 空间复杂度：O(n)
*/
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return; // 递归终止条件

int mid = left + (right – left) / 2;
mergeSort(arr, left, mid); // 递归排序左半部分
mergeSort(arr, mid + 1, right); // 递归排序右半部分
merge(arr, left, mid, right); // 合并两个有序子数组
}

/**
* 合并两个有序子数组 arr[left..mid] 和 arr[mid+1..right]
*/
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right – left + 1];
int i = left, j = mid + 1, k = 0;

while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 处理剩余元素
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];

// 将temp复制回原数组
for (int p = 0; p < temp.length; p++) {
arr[left + p] = temp[p];
}
}

public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10};
mergeSort(arr, 0, arr.length – 1);
System.out.println("排序结果: " + java.util.Arrays.toString(arr));
// 输出: [3, 9, 10, 27, 38, 43, 82]
}
}

⭐ 归并排序改造：求逆序对数量（期末超级高频！）

题目描述：给定一个数组，求其中逆序对的总数。逆序对即 i < j 且 arr[i] > arr[j]。

核心思路：在归并排序的 merge 过程中，当左半部分的 arr[i] > arr[j] 时，说明 arr[i] 及其后面的所有元素都大于 arr[j]，因此逆序对数量增加 mid – i + 1。

public class InversionCount {

private static int count = 0; // 逆序对计数器

/**
* 求逆序对数量（基于归并排序改造）
* 时间复杂度：O(n log n)
* 空间复杂度：O(n)
*/
public static int countInversions(int[] arr, int left, int right) {
if (left >= right) return 0;

int mid = left + (right – left) / 2;
countInversions(arr, left, mid);
countInversions(arr, mid + 1, right);
mergeAndCount(arr, left, mid, right);
return count;
}

private static void mergeAndCount(int[] arr, int left, int mid, int right) {
int[] temp = new int[right – left + 1];
int i = left, j = mid + 1, k = 0;

while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
// arr[i] > arr[j]，产生逆序对
// 左半部分从i到mid的所有元素都大于arr[j]
count += (mid – i + 1); // ★★★ 核心公式 ★★★
temp[k++] = arr[j++];
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];

for (int p = 0; p < temp.length; p++) {
arr[left + p] = temp[p];
}
}

public static void main(String[] args) {
int[] arr = {7, 5, 6, 4}; // 逆序对: (7,5),(7,6),(7,4),(5,4),(6,4) = 5
count = 0; // 重置
System.out.println("逆序对数量: " + countInversions(arr, 0, arr.length – 1));
// 输出: 5
}
}

⚠️ 考试坑点：

1.4 快速排序

public class QuickSort {

/**
* 快速排序主方法
* 时间复杂度：平均O(n log n)，最坏O(n²)
* 空间复杂度：O(log n)（递归栈）
*/
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) return;

int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex – 1);
quickSort(arr, pivotIndex + 1, right);
}

/**
* 分区函数：选最右元素为基准，将小于pivot的放左边，大于的放右边
* 返回pivot的最终位置
*/
public static int partition(int[] arr, int left, int right) {
int pivot = arr[right]; // 选最右边的元素作为基准
int i = left – 1; // i指向小于pivot的最后一个元素

for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right); // 把pivot放到正确位置
return i + 1;
}

private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length – 1);
System.out.println("排序结果: " + java.util.Arrays.toString(arr));
// 输出: [1, 5, 7, 8, 9, 10]
}
}

⭐ 快速选择：求第K大/第K小元素

public class QuickSelect {

/**
* 求数组中第k小的元素（不用完全排序）
* 时间复杂度：平均O(n)，最坏O(n²)
* 空间复杂度：O(log n)
*/
public static int findKthSmallest(int[] arr, int left, int right, int k) {
if (left == right) return arr[left];

int pivotIndex = partition(arr, left, right);

if (k – 1 == pivotIndex) {
return arr[pivotIndex];
} else if (k – 1 < pivotIndex) {
return findKthSmallest(arr, left, pivotIndex – 1, k);
} else {
return findKthSmallest(arr, pivotIndex + 1, right, k);
}
}

private static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left – 1;
for (int j = left; j < right; 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[right]; arr[right] = temp;
return i + 1;
}

public static void main(String[] args) {
int[] arr = {3, 2, 1, 5, 6, 4};
// 第2小的元素
System.out.println("第2小: " + findKthSmallest(arr, 0, arr.length – 1, 2));
// 输出: 2

// 第2大 = 第(n-2+1)小 = 第5小
int k = 2; // 第k大
System.out.println("第2大: " + findKthSmallest(arr, 0, arr.length – 1, arr.length – k + 1));
// 输出: 5
}
}

1.5 最大子数组（分治版本）

public class MaxSubarrayDivideConquer {

/**
* 分治法求最大子数组和
* 时间复杂度：O(n log n)
* 空间复杂度：O(log n)
* 注意：此题DP版本（Kadane算法）更优，为O(n)，见动态规划部分
*/
public static int maxSubArray(int[] arr, int left, int right) {
if (left == right) return arr[left];

int mid = left + (right – left) / 2;

// 三种情况取最大值
int leftMax = maxSubArray(arr, left, mid); // 最大子数组在左半部分
int rightMax = maxSubArray(arr, mid + 1, right); // 最大子数组在右半部分
int crossMax = maxCrossingSum(arr, left, mid, right); // 最大子数组跨越中点

return Math.max(Math.max(leftMax, rightMax), crossMax);
}

/**
* 求跨越中点的最大子数组和
*/
private static int maxCrossingSum(int[] arr, int left, int mid, int right) {
// 向左延伸的最大和
int leftSum = Integer.MIN_VALUE;
int sum = 0;
for (int i = mid; i >= left; i—) {
sum += arr[i];
leftSum = Math.max(leftSum, sum);
}

// 向右延伸的最大和
int rightSum = Integer.MIN_VALUE;
sum = 0;
for (int i = mid + 1; i <= right; i++) {
sum += arr[i];
rightSum = Math.max(rightSum, sum);
}

return leftSum + rightSum;
}

public static void main(String[] args) {
int[] arr = {–2, 1, –3, 4, –1, 2, 1, –5, 4};
System.out.println("最大子数组和: " + maxSubArray(arr, 0, arr.length – 1));
// 输出: 6（子数组 [4, -1, 2, 1]）
}
}

分治部分小结：分治算法在期末考试中出题概率极高，尤其是归并排序求逆序对和快速排序的partition函数。写代码时一定要注意数组边界和递归终止条件，这两个是最容易扣分的地方。

二、贪心算法（中等频率）

2.1 核心思想

贪心算法的核心是：每一步都选择当前看来最优的方案，期望局部最优能推出全局最优。

贪心算法的代码特点：

• 一般不需要递归，排序+一次遍历即可
• 代码通常比较短，但正确性证明（简答题）需要单独分析
• 考试中贪心代码题一般只需要写实现，证明一般出简答题

2.2 活动选择问题

题目描述：给定 n 个活动的开始时间和结束时间，选择尽可能多的互不重叠的活动。

贪心策略：按结束时间升序排序，每次选结束时间最早且与已选活动不冲突的活动。

import java.util.*;

public class ActivitySelection {

/**
* 活动选择问题 – 贪心算法
* 时间复杂度：O(n log n)（排序）
* 空间复杂度：O(n)
*/
public static List<int[]> selectActivities(int[][] activities) {
// 按结束时间升序排序
Arrays.sort(activities, (a, b) -> a[1] – b[1]);

List<int[]> selected = new ArrayList<>();
int lastEndTime = –1;

for (int[] activity : activities) {
if (activity[0] >= lastEndTime) {
// 当前活动的开始时间 >= 上一个选中活动的结束时间
selected.add(activity);
lastEndTime = activity[1];
}
}

return selected;
}

public static void main(String[] args) {
// 每个活动: {开始时间, 结束时间}
int[][] activities = {
{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9},
{6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}
};

List<int[]> result = selectActivities(activities);
System.out.println("最多选择 " + result.size() + " 个活动:");
for (int[] act : result) {
System.out.println(" 活动 [" + act[0] + ", " + act[1] + ")");
}
// 输出: 4个活动
}
}

2.3 哈夫曼编码（优先队列构造哈夫曼树）

题目描述：给定一组字符及其频率，构造哈夫曼树，计算带权路径长度（WPL）。

import java.util.*;

public class HuffmanCoding {

// 哈夫曼树节点
static class HuffmanNode implements Comparable<HuffmanNode> {
char ch;
int freq;
HuffmanNode left, right;

HuffmanNode(char ch, int freq) {
this.ch = ch;
this.freq = freq;
}

@Override
public int compareTo(HuffmanNode other) {
return this.freq – other.freq; // 按频率升序
}
}

/**
* 构造哈夫曼树，返回根节点
* 时间复杂度：O(n log n)
* 空间复杂度：O(n)
*/
public static HuffmanNode buildHuffmanTree(char[] chars, int[] freqs) {
PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();

for (int i = 0; i < chars.length; i++) {
pq.offer(new HuffmanNode(chars[i], freqs[i]));
}

while (pq.size() > 1) {
HuffmanNode left = pq.poll(); // 取出频率最小的两个节点
HuffmanNode right = pq.poll();

HuffmanNode parent = new HuffmanNode('\\0', left.freq + right.freq);
parent.left = left;
parent.right = right;

pq.offer(parent); // 新节点入队
}

return pq.poll(); // 根节点
}

/**
* 计算带权路径长度（WPL）
*/
public static int calculateWPL(HuffmanNode root, int depth) {
if (root == null) return 0;
// 叶子节点
if (root.left == null && root.right == null) {
return root.freq * depth;
}
return calculateWPL(root.left, depth + 1) + calculateWPL(root.right, depth + 1);
}

/**
* 打印哈夫曼编码
*/
public static void printCodes(HuffmanNode root, String code) {
if (root == null) return;
if (root.left == null && root.right == null) {
System.out.println(" 字符 '" + root.ch + "': " + code + " (频率=" + root.freq + ")");
}
printCodes(root.left, code + "0");
printCodes(root.right, code + "1");
}

public static void main(String[] args) {
char[] chars = {'a', 'b', 'c', 'd', 'e', 'f'};
int[] freqs = {45, 13, 12, 16, 9, 5};

HuffmanNode root = buildHuffmanTree(chars, freqs);

System.out.println("哈夫曼编码:");
printCodes(root, "");
System.out.println("WPL = " + calculateWPL(root, 0));
}
}

2.4 零钱兑换（贪心版本）

public class CoinChangeGreedy {

/**
* 零钱兑换 – 贪心算法（仅适用于规范币值，如1,5,10,25,50,100）
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*
* 注意：贪心法不是通用解法！对于币值{1,3,4}凑6元，贪心给出4+1+1=3枚，
* 但最优解是3+3=2枚。考试时老师会说明硬币满足贪心条件。
*/
public static int coinChangeGreedy(int[] coins, int amount) {
// 假设coins已经按降序排列（或先排序）
Arrays.sort(coins);
int count = 0;

for (int i = coins.length – 1; i >= 0; i—) {
if (amount <= 0) break;
count += amount / coins[i];
amount %= coins[i];
}

return amount == 0 ? count : –1;
}

public static void main(String[] args) {
int[] coins = {1, 5, 10, 25};
System.out.println("凑 63 分需要: " + coinChangeGreedy(coins, 63) + " 枚硬币");
// 25*2 + 10*1 + 1*3 = 6枚
}
}

贪心部分小结：贪心算法代码一般较短，核心是排序+一次遍历。期末考试中贪心代码题出现频率中等，但贪心策略的证明（简答/选择题）出现频率较高。

三、动态规划（期末代码大题TOP1，重中之重）

3.1 核心思想

动态规划（Dynamic Programming, DP）是期末考试中出题频率最高、分值最大的考点。

DP解题四步法：

考试关键提醒：

• 必须写迭代版本，不要写递归（递归会超时，而且老师会扣分）
• 01背包逆序遍历容量，完全背包正序遍历容量——这个循环顺序是高频扣分点！

3.2 一维DP

3.2.1 爬楼梯

题目描述：每次可以爬1或2个台阶，求到达第n阶有多少种方法。

public class ClimbingStairs {

/**
* 爬楼梯 – 动态规划
* 状态定义：dp[i] = 到达第i阶的方法数
* 状态转移：dp[i] = dp[i-1] + dp[i-2]
* 时间复杂度：O(n)
* 空间复杂度：O(1)（空间优化后）
*/
public static int climbStairs(int n) {
if (n <= 2) return n;

// 空间优化：只需要前两个状态
int prev2 = 1; // dp[1]
int prev1 = 2; // dp[2]

for (int i = 3; i <= n; i++) {
int current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}

return prev1;
}

// 未优化版本（考试建议先写这个，更清晰）
public static int climbStairsFullDP(int n) {
if (n <= 2) return n;
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i – 1] + dp[i – 2];
}
return dp[n];
}

public static void main(String[] args) {
System.out.println("爬5阶楼梯: " + climbStairs(5) + " 种方法");
// 输出: 8
}
}

3.2.2 最大连续子数组和（Kadane算法）

public class MaxSubArrayDP {

/**
* 最大连续子数组和 – 动态规划（Kadane算法）
* 状态定义：dp[i] = 以arr[i]结尾的最大连续子数组和
* 状态转移：dp[i] = max(arr[i], dp[i-1] + arr[i])
* 时间复杂度：O(n)
* 空间复杂度：O(1)（空间优化后）
*/
public static int maxSubArray(int[] arr) {
if (arr == null || arr.length == 0) return 0;

int currentMax = arr[0];
int globalMax = arr[0];

for (int i = 1; i < arr.length; i++) {
currentMax = Math.max(arr[i], currentMax + arr[i]);
globalMax = Math.max(globalMax, currentMax);
}

return globalMax;
}

public static void main(String[] args) {
int[] arr = {–2, 1, –3, 4, –1, 2, 1, –5, 4};
System.out.println("最大子数组和: " + maxSubArray(arr));
// 输出: 6（子数组 [4, -1, 2, 1]）
}
}

3.2.3 打家劫舍

题目描述：相邻房屋不能同时偷，求能偷到的最大金额。

public class HouseRobber {

/**
* 打家劫舍 – 动态规划
* 状态定义：dp[i] = 偷到第i个房屋时能获得的最大金额
* 状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
* – 不偷第i个：dp[i-1]
* – 偷第i个：dp[i-2] + nums[i]
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
public static int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0];

int prev2 = 0; // dp[i-2]
int prev1 = 0; // dp[i-1]

for (int num : nums) {
int current = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = current;
}

return prev1;
}

public static void main(String[] args) {
int[] nums = {2, 7, 9, 3, 1};
System.out.println("最大偷窃金额: " + rob(nums));
// 输出: 12（偷房屋0(2) + 房屋2(9) + 房屋4(1) = 12）
}
}

3.3 二维DP（大题高频区）

⭐ 3.3.1 01背包（必考！！！）

题目描述：有 n 个物品，每个物品有重量 weight[i] 和价值 value[i]，背包容量为 W。每个物品只能选一次，求能装入背包的最大价值。

public class ZeroOneKnapsack {

/**
* 01背包 – 动态规划（二维DP数组版本，考试推荐）
*
* 状态定义：dp[i][j] = 前i个物品，背包容量为j时的最大价值
* 状态转移：
* 不选第i个物品：dp[i][j] = dp[i-1][j]
* 选第i个物品：dp[i][j] = dp[i-1][j-weight[i-1]] + value[i-1] （需j >= weight[i-1]）
* dp[i][j] = max(不选, 选)
*
* 时间复杂度：O(n * W)
* 空间复杂度：O(n * W)
*/
public static int knapsack01(int[] weights, int[] values, int W) {
int n = weights.length;
int[][] dp = new int[n + 1][W + 1];

// 初始化：dp[0][j] = 0（0个物品，价值为0），dp[i][0] = 0（容量为0，价值为0）
// Java数组默认初始化为0，所以可以省略

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (j >= weights[i – 1]) {
// 可以选或不选第i个物品
dp[i][j] = Math.max(
dp[i – 1][j], // 不选
dp[i – 1][j – weights[i – 1]] + values[i – 1] // 选
);
} else {
// 容量不够，不能选
dp[i][j] = dp[i – 1][j];
}
}
}

return dp[n][W];
}

/**
* 01背包 – 空间优化版本（一维DP数组）
* ★★★ 注意：容量j必须逆序遍历！★★★
* 空间复杂度：O(W)
*/
public static int knapsack01Optimized(int[] weights, int[] values, int W) {
int n = weights.length;
int[] dp = new int[W + 1];

for (int i = 0; i < n; i++) {
// ★★★ 关键：逆序遍历容量 ★★★
// 原因：每个物品只能选一次，逆序保证不会重复选取
for (int j = W; j >= weights[i]; j—) {
dp[j] = Math.max(dp[j], dp[j – weights[i]] + values[i]);
}
}

return dp[W];
}

public static void main(String[] args) {
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int W = 8;

System.out.println("01背包最大价值（二维）: " + knapsack01(weights, values, W));
System.out.println("01背包最大价值（一维优化）: " + knapsack01Optimized(weights, values, W));
// 输出: 10（选物品0(重量2,价值3) + 物品3(重量5,价值6) = 价值9…
// 或选物品1(重量3,价值4) + 物品2(重量4,价值5) = 价值9… 不对
// 选物品0(2,3) + 物品2(4,5) = 重量6, 价值8
// 选物品1(3,4) + 物品3(5,6) = 重量8, 价值10 ✓）
}
}

⚠️ 超级重要坑点：01背包空间优化版本中，容量 j 必须从大到小（逆序）遍历！如果正序遍历，同一个物品可能被重复选取，就变成了完全背包。这个循环顺序是期末考试中最常见的扣分点！

⭐ 3.3.2 完全背包

题目描述：与01背包相同，但每个物品可以无限次选取。

public class CompleteKnapsack {

/**
* 完全背包 – 动态规划（一维DP数组）
* 状态转移：dp[j] = max(dp[j], dp[j – weights[i]] + values[i])
*
* ★★★ 关键区别：容量j正序遍历！★★★
* 原因：物品可以重复选取，正序遍历允许同一物品被多次使用
*
* 时间复杂度：O(n * W)
* 空间复杂度：O(W)
*/
public static int completeKnapsack(int[] weights, int[] values, int W) {
int n = weights.length;
int[] dp = new int[W + 1];

for (int i = 0; i < n; i++) {
// ★★★ 关键：正序遍历容量 ★★★（与01背包相反）
for (int j = weights[i]; j <= W; j++) {
dp[j] = Math.max(dp[j], dp[j – weights[i]] + values[i]);
}
}

return dp[W];
}

public static void main(String[] args) {
int[] weights = {2, 3, 4};
int[] values = {3, 4, 5};
int W = 8;

System.out.println("完全背包最大价值: " + completeKnapsack(weights, values, W));
// 选4次物品0(重量2*4=8, 价值3*4=12) = 12
}
}

01背包 vs 完全背包 循环顺序对比：

• 01背包（一维优化）：for (int j = W; j >= weights[i]; j–) 逆序
• 完全背包（一维优化）：for (int j = weights[i]; j <= W; j++) 正序

记住这个区别，考试必考！

⭐ 3.3.3 最长公共子序列 LCS

题目描述：给定两个字符串 s1 和 s2，求它们的最长公共子序列的长度。

public class LCS {

/**
* 最长公共子序列 – 动态规划
* 状态定义：dp[i][j] = s1前i个字符和s2前j个字符的LCS长度
* 状态转移：
* 若 s1[i-1] == s2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
* 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
* 时间复杂度：O(m * n)
* 空间复杂度：O(m * n)
*/
public static int lcsLength(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m + 1][n + 1];

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i – 1) == s2.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的具体子序列（加分项，部分考试要求）
* 通过回溯dp数组还原
*/
public static String lcsString(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m + 1][n + 1];

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i – 1) == s2.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 sb = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (s1.charAt(i – 1) == s2.charAt(j – 1)) {
sb.append(s1.charAt(i – 1));
i—; j—;
} else if (dp[i – 1][j] > dp[i][j – 1]) {
i—;
} else {
j—;
}
}

return sb.reverse().toString();
}

public static void main(String[] args) {
String s1 = "ABCBDAB";
String s2 = "BDCAB";
System.out.println("LCS长度: " + lcsLength(s1, s2)); // 输出: 4
System.out.println("LCS子序列: " + lcsString(s1, s2)); // 输出: BCAB
}
}

3.3.4 最长回文子串

public class LongestPalindrome {

/**
* 最长回文子串 – 动态规划
* 状态定义：dp[i][j] = s[i..j] 是否为回文串（boolean）
* 状态转移：
* 若 s[i] == s[j]：dp[i][j] = dp[i+1][j-1]（当j-i<=2时为true）
* 否则：dp[i][j] = false
* 时间复杂度：O(n²)
* 空间复杂度：O(n²)
*/
public static String longestPalindrome(String s) {
if (s == null || s.length() < 2) return s;

int n = s.length();
boolean[][] dp = new boolean[n][n];
int maxLen = 1, start = 0;

// 单个字符都是回文
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}

// 注意遍历顺序：先枚举长度，再枚举起点
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n – len; i++) {
int j = i + len – 1;

if (s.charAt(i) == s.charAt(j)) {
if (len <= 3) { // 长度2或3且首尾相同，一定是回文
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j – 1];
}
}

if (dp[i][j] && len > maxLen) {
maxLen = len;
start = i;
}
}
}

return s.substring(start, start + maxLen);
}

public static void main(String[] args) {
System.out.println("最长回文子串: " + longestPalindrome("babad"));
// 输出: "bab" 或 "aba"
System.out.println("最长回文子串: " + longestPalindrome("cbbd"));
// 输出: "bb"
}
}

3.3.5 编辑距离

题目描述：给定两个字符串 word1 和 word2，计算将 word1 转换成 word2 所使用的最少操作数（插入、删除、替换）。

public class EditDistance {

/**
* 编辑距离 – 动态规划
* 状态定义：dp[i][j] = word1前i个字符转换为word2前j个字符的最少操作数
* 状态转移：
* 若 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]（不需要操作）
* 否则：dp[i][j] = min(
* dp[i-1][j] + 1, // 删除word1[i-1]
* dp[i][j-1] + 1, // 在word1中插入word2[j-1]
* dp[i-1][j-1] + 1 // 将word1[i-1]替换为word2[j-1]
* )
* 初始化：dp[i][0] = i（全删除），dp[0][j] = j（全插入）
* 时间复杂度：O(m * n)
* 空间复杂度：O(m * n)
*/
public static int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];

// 初始化
for (int i = 0; i <= m; i++) dp[i][0] = i; // word1前i个字符变为空串，需i次删除
for (int j = 0; j <= n; j++) dp[0][j] = j; // 空串变为word2前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], dp[i][j – 1]), // 删除、插入
dp[i – 1][j – 1] // 替换
) + 1;
}
}
}

return dp[m][n];
}

public static void main(String[] args) {
System.out.println("编辑距离(horse, ros): " + minDistance("horse", "ros"));
// 输出: 3 (horse -> rorse -> rose -> ros)

System.out.println("编辑距离(intention, execution): " + minDistance("intention", "execution"));
// 输出: 5
}
}

3.3.6 矩阵链乘法

题目描述：给定n个矩阵的维度，确定矩阵相乘的顺序，使得标量乘法次数最少。

public class MatrixChainMultiplication {

/**
* 矩阵链乘法 – 动态规划
* 状态定义：dp[i][j] = 矩阵Ai到Aj相乘的最小标量乘法次数
* 状态转移：dp[i][j] = min{ dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j] }，i <= k < j
* 时间复杂度：O(n³)
* 空间复杂度：O(n²)
*/
public static int matrixChainOrder(int[] p) {
int n = p.length – 1; // n个矩阵
int[][] dp = new int[n + 1][n + 1];

// dp[i][i] = 0，单个矩阵不需要乘法

// len: 链的长度，从2开始
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n – len + 1; i++) {
int j = i + len – 1;
dp[i][j] = Integer.MAX_VALUE;

for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + p[i – 1] * p[k] * p[j];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}

return dp[1][n];
}

public static void main(String[] args) {
// 矩阵维度：A1=10×30, A2=30×5, A3=5×60
int[] p = {10, 30, 5, 60};
System.out.println("最小乘法次数: " + matrixChainOrder(p));
// 输出: 4500 ((A1*A2)*A3 = 10*30*5 + 10*5*60 = 1500 + 3000 = 4500)
}
}

动态规划部分小结：DP是期末考试的绝对核心，01背包和LCS是最高频考点。写DP代码时要牢记四步法（状态定义、转移方程、初始化、填表顺序），写完后一定要标注时间复杂度和空间复杂度。

四、回溯算法（非常高频代码题）

4.1 核心思想

回溯算法的本质是递归 + 剪枝，通过枚举所有可能的解，并在搜索过程中及时排除不符合条件的分支。

Java回溯算法的通用模板：

void backtrack(路径, 选择列表) {
if (满足结束条件) {
结果.add(路径);
return;
}

for (选择 : 选择列表) {
做选择; // path.add(choice)
backtrack(路径, 选择列表);
撤销选择; // path.remove(choice) ★★★ 回溯核心 ★★★
}
}

关键要点：

• Java中一般用 List<List<Integer>> 保存结果集
• 回溯时 add 之后，递归返回一定要 remove（撤销选择）
• 剪枝是得分点，能写剪枝一定要写

4.2 子集问题

import java.util.*;

public class Subsets {

/**
* 子集 – 回溯算法
* 给定一个不含重复元素的数组，返回所有可能的子集
* 时间复杂度：O(n * 2^n)
* 空间复杂度：O(n)（递归栈深度）
*/
public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums, 0);
return result;
}

private static void backtrack(List<List<Integer>> result, List<Integer> path,
int[] nums, int startIndex) {
// 每个节点都是一个有效子集（不需要判断终止条件）
result.add(new ArrayList<>(path)); // 注意：必须new ArrayList复制！

for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]); // 做选择
backtrack(result, path, nums, i + 1); // 递归
path.remove(path.size() – 1); // 撤销选择（回溯）
}
}

public static void main(String[] args) {
int[] nums = {1, 2, 3};
List<List<Integer>> result = subsets(nums);
System.out.println("所有子集: " + result);
// 输出: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
}
}

4.3 子集II（含重复元素，去重）

import java.util.*;

public class SubsetsII {

/**
* 子集II – 含重复元素，需要去重
* 关键：先排序，然后在同一层中跳过重复元素
* 时间复杂度：O(n * 2^n)
*/
public static List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums); // ★ 必须先排序！
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums, 0);
return result;
}

private static void backtrack(List<List<Integer>> result, List<Integer> path,
int[] nums, int startIndex) {
result.add(new ArrayList<>(path));

for (int i = startIndex; i < nums.length; i++) {
// ★ 剪枝去重：同一层中，如果当前元素和前一个相同，跳过
if (i > startIndex && nums[i] == nums[i – 1]) {
continue;
}
path.add(nums[i]);
backtrack(result, path, nums, i + 1);
path.remove(path.size() – 1);
}
}

public static void main(String[] args) {
int[] nums = {1, 2, 2};
System.out.println("去重子集: " + subsetsWithDup(nums));
// 输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]
}
}

4.4 全排列

import java.util.*;

public class Permutations {

/**
* 全排列 – 回溯算法
* 时间复杂度：O(n * n!)
* 空间复杂度：O(n)
*/
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length]; // 标记元素是否已使用
backtrack(result, new ArrayList<>(), nums, used);
return result;
}

private static void backtrack(List<List<Integer>> result, List<Integer> path,
int[] nums, boolean[] used) {
// 终止条件：路径长度等于数组长度
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}

for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // 已使用的元素跳过

used[i] = true; // 做选择
path.add(nums[i]);
backtrack(result, path, nums, used);
path.remove(path.size() – 1); // 撤销选择
used[i] = false; // 撤销标记
}
}

/**
* 全排列II – 含重复元素，去重
*/
public static List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums); // ★ 先排序
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrackUnique(result, new ArrayList<>(), nums, used);
return result;
}

private static void backtrackUnique(List<List<Integer>> result, List<Integer> path,
int[] nums, boolean[] used) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}

for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
// ★ 去重剪枝：同一层中，前一个相同元素未被使用时跳过
if (i > 0 && nums[i] == nums[i – 1] && !used[i – 1]) {
continue;
}

used[i] = true;
path.add(nums[i]);
backtrackUnique(result, path, nums, used);
path.remove(path.size() – 1);
used[i] = false;
}
}

public static void main(String[] args) {
int[] nums = {1, 2, 3};
System.out.println("全排列: " + permute(nums));
// 输出: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

int[] nums2 = {1, 1, 2};
System.out.println("去重全排列: " + permuteUnique(nums2));
// 输出: [[1,1,2], [1,2,1], [2,1,1]]
}
}

4.5 N皇后（经典大题）

题目描述：在 n×n 的棋盘上放置 n 个皇后，使得它们互不攻击（不在同一行、同一列、同一对角线）。

import java.util.*;

public class NQueens {

private static int solutionCount = 0;

/**
* N皇后 – 回溯算法
* 时间复杂度：O(n!)
* 空间复杂度：O(n)
*/
public static List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
backtrack(result, board, 0, n);
return result;
}

private static void backtrack(List<List<String>> result, char[][] board, int row, int n) {
if (row == n) {
// 找到一种解法
List<String> solution = new ArrayList<>();
for (char[] r : board) {
solution.add(new String(r));
}
result.add(solution);
solutionCount++;
return;
}

for (int col = 0; col < n; col++) {
if (isValid(board, row, col, n)) {
board[row][col] = 'Q'; // 放置皇后
backtrack(result, board, row + 1, n);
board[row][col] = '.'; // 撤销放置（回溯）
}
}
}

/**
* 检查在 (row, col) 位置放置皇后是否合法
* 只需要检查上方（因为下方还没放）
*/
private static boolean isValid(char[][] board, int row, int col, int n) {
// 检查列
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') return false;
}

// 检查左上对角线
for (int i = row – 1, j = col – 1; i >= 0 && j >= 0; i—, j—) {
if (board[i][j] == 'Q') return false;
}

// 检查右上对角线
for (int i = row – 1, j = col + 1; i >= 0 && j < n; i—, j++) {
if (board[i][j] == 'Q') return false;
}

return true;
}

/**
* 简化版：只求N皇后的解法数量（考试更常考）
*/
public static int totalNQueens(int n) {
solutionCount = 0;
boolean[] cols = new boolean[n]; // 列是否被占用
boolean[] diag1 = new boolean[2 * n]; // 主对角线 (row – col + n)
boolean[] diag2 = new boolean[2 * n]; // 副对角线 (row + col)
backtrackCount(0, n, cols, diag1, diag2);
return solutionCount;
}

private static void backtrackCount(int row, int n, boolean[] cols,
boolean[] diag1, boolean[] diag2) {
if (row == n) {
solutionCount++;
return;
}

for (int col = 0; col < n; col++) {
int d1 = row – col + n;
int d2 = row + col;

if (cols[col] || diag1[d1] || diag2[d2]) continue; // 剪枝

cols[col] = true; diag1[d1] = true; diag2[d2] = true;
backtrackCount(row + 1, n, cols, diag1, diag2);
cols[col] = false; diag1[d1] = false; diag2[d2] = false; // 回溯
}
}

public static void main(String[] args) {
int n = 4;
System.out.println(n + "皇后的解法数量: " + totalNQueens(n));
// 输出: 2

List<List<String>> solutions = solveNQueens(n);
System.out.println("具体解法:");
for (List<String> sol : solutions) {
for (String row : sol) {
System.out.println(" " + row);
}
System.out.println();
}
}
}

4.6 组合求和

import java.util.*;

public class CombinationSum {

/**
* 组合求和 – 元素可重复选
* 给定候选数组和目标值，找出所有和为target的组合（元素可重复使用）
* 时间复杂度：取决于解的数量
*/
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates); // 排序有利于剪枝
backtrack(result, new ArrayList<>(), candidates, target, 0);
return result;
}

private static void backtrack(List<List<Integer>> result, List<Integer> path,
int[] candidates, int remain, int startIndex) {
if (remain < 0) return; // 剪枝
if (remain == 0) {
result.add(new ArrayList<>(path));
return;
}

for (int i = startIndex; i < candidates.length; i++) {
// 剪枝优化：如果当前元素已经大于剩余值，后面更大的也不用试了
if (candidates[i] > remain) break;

path.add(candidates[i]);
// 注意：startIndex传i（不是i+1），因为元素可以重复选
backtrack(result, path, candidates, remain – candidates[i], i);
path.remove(path.size() – 1);
}
}

/**
* 组合求和II – 元素不可重复选，数组可能有重复元素
*/
public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
backtrack2(result, new ArrayList<>(), candidates, target, 0);
return result;
}

private static void backtrack2(List<List<Integer>> result, List<Integer> path,
int[] candidates, int remain, int startIndex) {
if (remain == 0) {
result.add(new ArrayList<>(path));
return;
}

for (int i = startIndex; i < candidates.length; i++) {
if (candidates[i] > remain) break; // 剪枝
// 去重：同一层中跳过重复元素
if (i > startIndex && candidates[i] == candidates[i – 1]) continue;

path.add(candidates[i]);
backtrack2(result, path, candidates, remain – candidates[i], i + 1); // i+1: 不可重复选
path.remove(path.size() – 1);
}
}

public static void main(String[] args) {
int[] candidates = {2, 3, 6, 7};
System.out.println("组合求和(target=7): " + combinationSum(candidates, 7));
// 输出: [[2,2,3], [7]]

int[] candidates2 = {10, 1, 2, 7, 6, 1, 5};
System.out.println("组合求和II(target=8): " + combinationSum2(candidates2, 8));
// 输出: [[1,1,6], [1,2,5], [1,7], [2,6]]
}
}

回溯部分小结：回溯算法是期末考试中非常高频的代码题。记住通用模板（做选择→递归→撤销选择），注意结果集中要 new ArrayList<>(path) 做深拷贝。去重剪枝是加分项，先排序再去重是固定套路。

五、图算法（代码大题，中高概率）

5.1 图的存储

import java.util.*;

public class GraphRepresentation {

/**
* 邻接矩阵表示（适合稠密图）
* adjMatrix[i][j] = 1 表示存在边 i->j（有权图则存权重）
*/
public static int[][] createAdjMatrix(int n, int[][] edges) {
int[][] adjMatrix = new int[n][n];
for (int[] edge : edges) {
adjMatrix[edge[0]][edge[1]] = 1;
// adjMatrix[edge[1]][edge[0]] = 1; // 无向图需要双向设置
}
return adjMatrix;
}

/**
* 邻接表表示（适合稀疏图，Java中推荐）
* 使用 List<List<Integer>> 实现
*/
public static List<List<Integer>> createAdjList(int n, int[][] edges) {
List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < n; i++) {
adjList.add(new ArrayList<>());
}
for (int[] edge : edges) {
adjList.get(edge[0]).add(edge[1]);
// adjList.get(edge[1]).add(edge[0]); // 无向图
}
return adjList;
}
}

5.2 DFS和BFS遍历

import java.util.*;

public class GraphTraversal {

/**
* DFS深度优先遍历（递归版）
* 时间复杂度：O(V + E)
* 空间复杂度：O(V)
*/
public static void dfs(List<List<Integer>> adj, int node, boolean[] visited, List<Integer> result) {
visited[node] = true;
result.add(node);

for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
dfs(adj, neighbor, visited, result);
}
}
}

/**
* BFS广度优先遍历
* 时间复杂度：O(V + E)
* 空间复杂度：O(V)
*/
public static List<Integer> bfs(List<List<Integer>> adj, int start) {
List<Integer> result = new ArrayList<>();
boolean[] visited = new boolean[adj.size()];
Queue<Integer> queue = new LinkedList<>();

visited[start] = true;
queue.offer(start);

while (!queue.isEmpty()) {
int node = queue.poll();
result.add(node);

for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}

return result;
}

/**
* 求连通分量数量（DFS应用）
*/
public static int countComponents(int n, List<List<Integer>> adj) {
boolean[] visited = new boolean[n];
int count = 0;

for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(adj, i, visited, new ArrayList<>());
count++;
}
}

return count;
}

public static void main(String[] args) {
int n = 5;
int[][] edges = {{0,1}, {0,2}, {1,3}, {2,4}};
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}