蓝桥杯API准备——Java板块
·
目录
🧮 一、数学相关类（Math / BigInteger / BigDecimal）
1. StringBuilder（拼接字符串比String快）
🧮 一、数学相关类（Math / BigInteger / BigDecimal）
1. Math 类（基础数学）
-
Math.abs(x)：取绝对值 -
Math.max(a, b)/Math.min(a, b) -
Math.pow(a, b)：a 的 b 次方 -
Math.sqrt(x)：平方根 -
Math.ceil(x)/Math.floor(x)/Math.round(x) -
Math.log(x)/Math.log10(x)：自然对数 / 以10为底 -
Math.random()：返回 [0,1) 的 double 随机数
2. BigInteger（超大整数，必会！）
BigInteger a = new BigInteger("123456789");
BigInteger b = new BigInteger("987654321");
a.add(b); // 加法
a.subtract(b); // 减法
a.multiply(b); // 乘法
a.divide(b); // 除法
a.mod(b); // 取模
a.pow(n); // 幂次
a.gcd(b); // 最大公约数
a.isProbablePrime(10); // 判断质数
3. BigDecimal（高精度小数）
-
.add().subtract().multiply().divide() -
.compareTo(BigDecimal.ZERO)判断大小
🔢 二、数组/排序/查找
1. Arrays 工具类
Arrays.sort(array); // 排序
Arrays.binarySearch(array, x) // 二分查找（需排序）
Arrays.fill(array, x); // 填充数组
Arrays.copyOf(arr, len); // 复制数组
2. Collections 工具类（用于集合操作）
Collections.sort(list); // 排序
Collections.reverse(list); // 反转
Collections.max(list); // 最大值
Collections.min(list); // 最小值
Collections.frequency(list, x); // 出现次数
🔁 三、集合框架（必备！）
1. List/ArrayList/LinkedList
List<Integer> list = new ArrayList<>();
list.add(x); list.get(i); list.size(); list.remove(i);
2. Set/HashSet/TreeSet（去重/排序）
Set<Integer> set = new HashSet<>();
set.add(x); set.contains(x); set.remove(x);
Set<Integer> set = new TreeSet<>(); // 自动排序
3. Map/HashMap/TreeMap（键值对）
Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.get("a"); map.containsKey("a"); map.remove("a");
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
📅 四、时间相关
System.currentTimeMillis(); // 毫秒时间戳（常用于计时）
🧵 五、String 相关常用操作（高频！）
str.length();
str.charAt(i);
str.indexOf("abc");
str.contains("abc");
str.startsWith("pre");
str.endsWith("suf");
str.substring(start, end);
str.split(" ");
str.toCharArray();
String.valueOf(x); // 其他类型转字符串
Integer.parseInt(str); // 字符串转数字
🧠 六、队列 / 堆 / 栈（数据结构类）
1. 栈 Stack
Stack<Integer> stack = new Stack<>();
stack.push(x); stack.pop(); stack.peek(); stack.isEmpty();
2. 队列 Queue
Queue<Integer> queue = new LinkedList<>();
queue.offer(x); queue.poll(); queue.peek(); queue.isEmpty();
3. 优先队列 PriorityQueue（堆）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
🔄 七、其他常用类
1. StringBuilder（拼接字符串比String快）
StringBuilder sb = new StringBuilder();
sb.append("a");
sb.toString(); // 取结果
2. Comparator（自定义排序）
list.sort((a, b) -> a - b); // 升序
list.sort((a, b) -> b - a); // 降序
3. Character 类
Character.isDigit(c);
Character.isLetter(c);
Character.isLowerCase(c);
Character.toLowerCase(c);
填空题
一、动态规划（DP）核心模板
1. 背包问题（01背包）
常用于求最大价值或组合数：
// 物品体积为v[], 价值为w[], 背包容量为capacity
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
for (int j = capacity; j >= v[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
System.out.println(dp[capacity]);2. 最长递增子序列（LIS）
int[] nums = {3,1,4,1,5,9,2,6};
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int maxLen = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
System.out.println(maxLen); // 输出最长递增子序列长度二、找规律题型
1. 递推公式（斐波那契变形）
例如：f(n) = f(n-1) + 2*f(n-2)
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + 2 * dp[i-2];
}
System.out.println(dp[n]);2. 杨辉三角规律
求第 n 行第 m 列的值（组合数）：
int[][] c = new int[n+1][n+1];
for (int i = 0; i <= n; i++) {
c[i][0] = 1;
for (int j = 1; j <= i; j++) {
c[i][j] = c[i-1][j-1] + c[i-1][j];
}
}
System.out.println(c[n][m]); // 输出组合数C(n,m)三、数论核心模板
1. 快速幂（求a^b mod p）
public static long fastPower(long a, long b, long p) {
long res = 1;
while (b > 0) {
if ((b & 1) == 1) {
res = (res * a) % p;
}
a = (a * a) % p;
b >>= 1;
}
return res;
}2. 欧拉函数（求1~n中与n互质的数的个数）
public static int euler(int n) {
int res = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
res = res / i * (i - 1);
while (n % i == 0) n /= i;
}
}
if (n > 1) res = res / n * (n - 1);
return res;
}四、日期处理模板
1. 闰年判断与日期差值
public static boolean isLeapYear(int year) {
return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}
// 计算两个日期的天数差（假设y1/m1/d1 <= y2/m2/d2）
public static int dayDiff(int y1, int m1, int d1, int y2, int m2, int d2) {
int[] monthDays = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int days = 0;
while (y1 < y2 || m1 < m2 || d1 < d2) {
d1++;
int maxDay = monthDays[m1];
if (m1 == 2 && isLeapYear(y1)) maxDay = 29;
if (d1 > maxDay) {
d1 = 1;
m1++;
if (m1 > 12) {
m1 = 1;
y1++;
}
}
days++;
}
return days;
}2. 计算某一天是星期几（基姆拉尔森公式）
// 公式：0=星期日, 1=星期一, ..., 6=星期六
public static int getWeek(int year, int month, int day) {
if (month < 3) {
month += 12;
year--;
}
int c = year / 100;
year = year % 100;
int week = (c / 4 - 2 * c + year + year / 4 + 13 * (month + 1) / 5 + day - 1) % 7;
return (week + 7) % 7;
}五、进制转换模板
1. 十进制转任意进制（2~36进制）
public static String decimalToBase(int num, int base) {
if (num == 0) return "0";
StringBuilder sb = new StringBuilder();
String chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
while (num > 0) {
sb.append(chars.charAt(num % base));
num /= base;
}
return sb.reverse().toString();
}2. 其他进制转十进制
public static int baseToDecimal(String s, int base) {
int res = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
int val = (c >= 'A') ? (c - 'A' + 10) : (c - '0');
res = res * base + val;
}
return res;
}六、高频数学公式
1. 组合数公式
-
递推公式：
C(n, k) = C(n-1, k-1) + C(n-1, k) -
直接计算：
C(n, k) = n! / (k! * (n-k)!)
2. 快速幂模运算
-
求
(a^b) % p：使用上述快速幂模板。
3. 等差数列与等比数列求和
-
等差数列和：
S = n*(a1 + an)/2 -
等比数列和：
S = a1*(q^n - 1)/(q - 1)（当q ≠ 1）
总结
-
填空题特点：答案唯一，无需考虑代码效率，但需注意边界条件（如闰年、0值处理）。
-
调试技巧：手动模拟小数据，验证代码逻辑。
-
必练题型：日期差值、质数筛法、动态规划递推式、进制转换回文数。
大题
🧮 一、数学与数论类
1. 最大公约数（GCD）与最小公倍数（LCM）
最大公约数（GCD）：使用欧几里得算法（辗转相除法）计算两个整数的最大公约数。
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
最小公倍数（LCM）：利用最大公约数计算两个整数的最小公倍数。
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
2. 快速幂（取模）
用于高效计算 $a^b \mod m$，常用于大数取模运算。
long powMod(long a, long b, long mod) {
long res = 1;
a %= mod;
while (b > 0) {
if ((b & 1) == 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
3. 素数筛法（埃拉托色尼筛法）
用于在一定范围内快速找出所有素数。
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
4. 组合数计算（杨辉三角）
用于计算组合数 $C(n, k)$，即从 $n$ 个元素中选出 $k$ 个的组合数。
int[][] C = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
🔍 二、搜索与图论
1. 深度优先搜索（DFS）与广度优先搜索（BFS）
DFS：用于遍历或搜索树或图的节点。
void dfs(int x, int y) {
visited[x][y] = true;
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir], ny = y + dy[dir];
if (inBounds(nx, ny) && !visited[nx][ny]) {
dfs(nx, ny);
}
}
}
BFS：用于在图中寻找最短路径或层次遍历。
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{startX, startY});
visited[startX][startY] = true;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
for (int dir = 0; dir < 4; dir++) {
int nx = curr[0] + dx[dir], ny = curr[1] + dy[dir];
if (inBounds(nx, ny) && !visited[nx][ny]) {
visited[nx][ny] = true;
queue.offer(new int[]{nx, ny});
}
}
}
2. 并查集（Union-Find）
用于处理不交集的合并及查询操作，常用于判断图中节点的连通性。
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void union(int x, int y) {
parent[find(x)] = find(y);
}
3. 最短路径算法（Dijkstra）
用于计算从起点到其他所有点的最短路径，适用于边权为非负的图。
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int u = curr[0], d = curr[1];
if (d > dist[u]) continue;
for (Edge e : graph[u]) {
int v = e.to, w = e.weight;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.offer(new int[]{v, dist[v]});
}
}
}
🎯 三、动态规划（DP）
1. 0-1 背包问题
问题描述：给定 n 个物品，每个物品有重量 weights[i] 和价值 values[i]，在总容量为 capacity 的背包中，选择若干物品使得总价值最大，且每个物品最多选一次。
代码模板：
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
for (int j = capacity; j >= weights[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
解释：dp[j] 表示容量为 j 的背包所能获得的最大价值。对于每个物品，从后向前遍历容量，更新 dp[j] 的值，确保每个物品只被考虑一次。
2. 最长上升子序列（LIS）
问题描述：在一个整数序列中，找到最长的严格递增子序列的长度。
代码模板：
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int lis = Arrays.stream(dp).max().getAsInt();
解释：dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度。通过遍历之前的元素，更新 dp[i] 的值，最终取 dp 数组中的最大值作为结果。
3. 最长公共子序列（LCS）
问题描述：给定两个字符串 A 和 B，求它们的最长公共子序列的长度。
代码模板：
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (A.charAt(i - 1) == B.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]);
}
}
}
解释：dp[i][j] 表示 A 的前 i 个字符与 B 的前 j 个字符的最长公共子序列长度。通过比较当前字符是否相等，更新 dp[i][j] 的值。
4. 数字三角形路径和
问题描述：给定一个数字三角形，从顶部到底部，每次只能移动到下一行中相邻的数字，求从顶部到底部的路径和的最小值。
代码模板：
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
}
}
int minTotal = triangle[0][0];
解释：从倒数第二行开始，逐行向上更新每个位置的值为其下方两个相邻位置的最小路径和，最终顶部的值即为最小路径和。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
22
0- 0
已为社区贡献6条内容
所有评论(0)