蓝桥杯基础算法笔记（Java 实现）
一维前缀和
✅ 作用
用于快速计算数组任意区间 [l, r] 的和。
✅ Java 实现（含注释）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// 构建前缀和数组
int[] buildPrefixSum(int[] nums) {
int n = nums.length;
int[] prefix = new int[n + 1];
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + nums[i - 1]; // 累加前缀和
}
return prefix;
}
// 查询区间 [l, r] 的和
int rangeSum(int[] prefix, int l, int r) {
return prefix[r + 1] - prefix[l];
}
|
📘 使用场景
多次查询数组某一段的区间和，复杂度从 O(n) 降为 O(1)。
二维前缀和
✅ 作用
用于快速求二维矩阵子矩阵的和。
✅ Java 实现（含注释）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N], s[N][N];
int n, m, q;
int main() {
scanf("%d%d%d", &n, &m, &q);
// 读入矩阵并构建二维前缀和
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
}
}
// 处理 q 次询问
for (int i = 1; i <= q; i++) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);
}
return 0;
}
|
📘 使用场景
需要高频查询子矩阵和的问题，例如地图资源统计等。
一维差分
✅ 作用
对一个数组进行多次区间加法修改，将复杂度从 O(n) 降为 O(1)。
✅ Java 实现（含注释）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
// 构建差分数组
int[] buildDiff(int[] nums) {
int n = nums.length;
int[] diff = new int[n + 1];
diff[0] = nums[0];
for (int i = 1; i < n; i++) {
diff[i] = nums[i] - nums[i - 1];
}
return diff;
}
// 区间 [l, r] 增加 val
void rangeAdd(int[] diff, int l, int r, int val) {
diff[l] += val;
if (r + 1 < diff.length) diff[r + 1] -= val;
}
// 还原原数组
int[] restore(int[] diff) {
int[] res = new int[diff.length - 1];
res[0] = diff[0];
for (int i = 1; i < res.length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
|
二维差分
✅ 作用
对一个矩阵进行多次子矩阵加法修改，复杂度降为 O(1)。
✅ Java 实现（含注释）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
// 对子矩阵 [(x1,y1), (x2,y2)] 增加 c
void insert(int[][] diff, int x1, int y1, int x2, int y2, int c) {
diff[x1][y1] += c;
diff[x2 + 1][y1] -= c;
diff[x1][y2 + 1] -= c;
diff[x2 + 1][y2 + 1] += c;
}
// 还原矩阵
int[][] restore(int[][] diff) {
int n = diff.length - 1, m = diff[0].length - 1;
int[][] res = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int a = diff[i][j];
if (i > 0) a += res[i - 1][j];
if (j > 0) a += res[i][j - 1];
if (i > 0 && j > 0) a -= res[i - 1][j - 1];
res[i][j] = a;
}
}
return res;
}
|
最大公约数 GCD
✅ 作用
用于约分、判断整除性、数论题基础。
✅ Java 实现（含注释）
1
2
3
4
|
// 欧几里得算法（辗转相除法）
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
|
最小公倍数 LCM
✅ 作用
用于周期性建模、最小公共时间点等。
✅ Java 实现（含注释）
1
2
3
4
|
// 最小公倍数 = a * b / gcd(a, b)
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
|
DFS（深度优先搜索）
✅ 作用
用于遍历图、树、矩阵搜索等问题。
✅ Java 示例（含注释）
1
2
3
4
5
6
7
8
9
|
// 深度优先搜索图
void dfs(int u, boolean[] visited, List<List<Integer>> graph) {
visited[u] = true; // 标记当前节点已访问
for (int v : graph.get(u)) {
if (!visited[v]) {
dfs(v, visited, graph); // 递归访问相邻节点
}
}
}
|
📘 使用场景
图搜索、迷宫路径、连通分量统计等。
递归
✅ 作用
通过函数自身调用自身，实现重复结构或树形问题求解。
✅ Java 示例（含注释）
1
2
3
4
5
|
// 递归实现斐波那契数列
int fib(int n) {
if (n <= 1) return n; // 基础情况
return fib(n - 1) + fib(n - 2); // 递归定义
}
|
📘 使用场景
树结构、数学函数、回溯算法等。
动态规划（DP）
✅ 作用
解决有重叠子问题、最优子结构的问题。
✅ Java 示例（含注释）
1
2
3
4
5
6
7
8
9
10
11
|
// 0-1 背包问题：给定物品重量 w、价值 v 和容量 C，求最大价值
int knapsack(int[] w, int[] v, int C) {
int n = w.length;
int[] dp = new int[C + 1]; // dp[i] 表示容量为 i 时的最大价值
for (int i = 0; i < n; i++) {
for (int j = C; j >= w[i]; j--) { // 倒序遍历防止重复使用物品
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}
return dp[C];
}
|
📘 使用场景
背包问题、序列编辑、路径计数等。
二分算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public class BinarySearchTemplate {
public int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1; // 左闭右闭区间 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (nums[mid] == target) {
return mid; // 找到目标值
} else if (nums[mid] < target) {
left = mid + 1; // 去右半部分查找
} else {
right = mid - 1; // 去左半部分查找
}
}
return -1; // 未找到目标值
}
}
|
快速求回文数
1
2
3
4
5
6
7
8
9
10
|
public static Boolean IsPalindrome(int x) {
if(x < 0) return false;
int t = x,c = 0;
while(t>0)
{
c = c*10 + t%10;
t /= 10;
}
return c == x;
}
|
