蓝桥杯java算法例题
一、经典数学问题
1. 约瑟夫问题
问题描述：N 个人围成一圈，从第一个人开始报数，报数到 M 的人出圈，剩下的人继续从 1 开始报数，直到所有人出圈，输出出圈顺序。
核心思路：用队列模拟环形结构，依次弹出元素并计数，计数到 M 时输出该元素，否则重新入队。
package test; import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner; public class Main { public static void main(String[] args) { Queue<Integer> queue = new LinkedList<>(); Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); // 总人数 int m = scanner.nextInt(); // 报数阈值 for (int i = 0; i < n; i++) { queue.add(i); // 初始化队列（0~n-1编号） } int res = 0; while (!queue.isEmpty()) { int x = queue.poll(); res++; if (res == m) { // 达到阈值，输出并重置计数 System.out.print(x + " "); res = 0; } else { queue.add(x); // 未达阈值，重新入队 } } }
}
2. 最大公约数（辗转相除法）
问题描述：求两个数的最大公约数（GCD）。
核心思路：利用递归，用较大数除以较小数取余数，重复此过程直到余数为 0，此时的除数即为最大公约数。
// 递归实现辗转相除法
public static int gcdRecursive(int a, int b) { if (b == 0) { // 终止条件：当b为0时，a即为最大公约数 return a; } return gcdRecursive(b, a % b); // 递归调用：用b和a%b继续计算
}
3. 奇妙数字
问题描述：找到一个数字，其平方和立方恰好包含 0~9 这 10 个数字各一次。
核心思路：枚举数字，计算其平方和立方，拼接后检查是否包含所有数字且无重复。
package test; import java.util.HashSet; public class Main { public static void main(String[] args) { int num = 1; while (true) { HashSet<Character> set = new HashSet<>(); long square = (long) num * num; long cube = (long) num * num * num; String s = square + "" + cube; if (s.length() == 10) { // 总长度需为10（0~9共10个数字） for (char c : s.toCharArray()) { set.add(c); } if (set.size() == 10) { // 包含所有数字且无重复 System.out.println(num); // 答案：69 break; } } num++; } }
}
二、字符串处理问题
1. ABC 问题
问题描述：输入三个整数和一个由 A、B、C 组成的字符串，按字符串中字母的顺序输出排序后的三个整数（A 对应最小，B 对应中间，C 对应最大）。
核心思路：先排序整数，再根据字符串中字母与索引的映射（A→0，B→1，C→2）输出对应值。
package test; import java.util.Arrays;
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int[] a = new int[3]; for (int i = 0; i < 3; i++) { a[i] = scanner.nextInt(); } Arrays.sort(a); // 排序数组（升序） char[] c = scanner.next().toCharArray(); for (char ch : c) { System.out.print(a[ch - 'A'] + " "); // 映射字母到索引（A→0，B→1，C→2） } }
}
2. 字符串压缩
问题描述：将连续重复的字符压缩为 “字符 + 重复次数”（如 “aaabbb”→“a3b3”），若压缩后长度未缩短则输出原字符串。
核心思路：遍历字符串，计数连续重复字符，拼接字符和次数。
import java.util.Scanner; public class StringCompression { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String input = scanner.nextLine(); String compressed = compress(input); if (compressed.length() < input.length()) { System.out.println(compressed); } else { System.out.println(input); } } public static String compress(String s) { StringBuilder sb = new StringBuilder(); int count = 1; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == s.charAt(i - 1)) { count++; } else { sb.append(s.charAt(i - 1)); if (count > 1) sb.append(count); count = 1; } } // 处理最后一个字符 sb.append(s.charAt(s.length() - 1)); if (count > 1) sb.append(count); return sb.toString(); }
}
3. 自定义字符串排序（拼接最大数）
问题描述：将一组整数拼接为最大的数（如 [3, 30]→“330”）。
核心思路：将整数转为字符串，按 “b+a” 与 “a+b” 的字典序排序（确保大的组合在前）。
import java.util.Arrays;
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); String[] strArr = new String[n]; for (int i = 0; i < n; i++) { strArr[i] = String.valueOf(scan.nextInt()); } // 排序规则：b+a 比 a+b 大则 b 在前 Arrays.sort(strArr, (a, b) -> (b + a).compareTo(a + b)); StringBuilder result = new StringBuilder(); for (String s : strArr) { result.append(s); } System.out.println(result); }
}
三、数字特征问题
1. 包含特定数字的和
问题描述：计算 1~n 中包含数字 2、0、1、9 的所有数的和。
核心思路：两种方法：①逐位拆解数字检查；②转为字符串检查是否包含目标字符。
// 方法1：逐位检查
package test; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int sum = 0; for (int i = 1; i <= n; i++) { if (containsSpecialDigit(i)) { sum += i; } } System.out.println(sum); } private static boolean containsSpecialDigit(int num) { while (num > 0) { int digit = num % 10; if (digit == 2 || digit == 0 || digit == 1 || digit == 9) { return true; } num /= 10; } return false; }
}// 方法2：字符串检查
public static boolean contains(int num) { String s = String.valueOf(num); return s.contains("2") || s.contains("0") || s.contains("1") || s.contains("9");
}
2. 立方数末尾为自身
问题描述：找到 1~10000 中所有满足 “n 的立方的末尾几位等于 n” 的数（如 4³=64，末尾 1 位是 4）。
核心思路：计算 n 的立方，转为字符串后检查是否以 n 为后缀。
package test; public class Main { public static void main(String[] args) { int count = 0; for (int n = 1; n <= 10000; n++) { long cube = (long) n * n * n; if (String.valueOf(cube).endsWith(String.valueOf(n))) { count++; } } System.out.println(count); // 答案：25 }
}
四、其他经典问题
1. 切割长方形（求正方形数量）
问题描述：将长方形切割为若干正方形，每次从最长边切割，求总数量。
核心思路：类似辗转相除法，用长边除以短边得正方形数量，剩余部分继续切割。
public class Main { public static void main(String[] args) { int length = 2019, width = 324; int count = 0; while (length > 0 && width > 0) { count += length / width; // 当前长边可切出的正方形数量 int temp = length % width; length = width; width = temp; // 交换继续切割剩余部分 } System.out.println(count); // 答案：21 }
}
2. 第 N 个质数
问题描述：找到第 2019 个质数（质数：大于 1 的自然数，除了 1 和自身无其他因数）。
核心思路：从 2 开始枚举，判断每个数是否为质数，累计到第 2019 个时输出。
package test; import java.util.ArrayList; public class Main { public static void main(String[] args) { ArrayList<Integer> primes = new ArrayList<>(); int num = 2; while (primes.size() < 2019) { if (isPrime(num)) { primes.add(num); } num++; } System.out.println(primes.get(2018)); // 第2019个（索引2018） } private static boolean isPrime(int n) { if (n < 2) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; }
}
五、逻辑推理问题
谁做了作业
问题描述：5 个学生（A、B、C、D、E）中，根据条件推断谁做了作业：
- A 和 B 要么都做，要么都不做；
- B 和 C 只有一人做；
- D 没做；
- C 和 E 最多一人做。
核心思路：枚举所有可能（0 = 没做，1 = 做了），筛选符合条件的组合。
package test; public class Main { public static void main(String[] args) { for (int a = 0; a <= 1; a++) { for (int b = 0; b <= 1; b++) { for (int c = 0; c <= 1; c++) { for (int d = 0; d <= 1; d++) { for (int e = 0; e <= 1; e++) { // 检查条件 if (a == b // A和B一致 && (b + c) == 1 // B和C仅一人做 && d == 0 // D没做 && (c + e) <= 1) { // C和E最多一人做 // 输出做了作业的人 System.out.println("做了作业的学生："); if (a == 1) System.out.print("A "); if (b == 1) System.out.print("B "); if (c == 1) System.out.print("C "); if (e == 1) System.out.print("E "); } } } } } } }
}