2025年4月蓝桥杯练习
发布时间
阅读量：
阅读量
刷题
题型
滑动窗口与双指针（定长/不定长/单序列/双序列/三指针）
二分算法（二分答案/最小化最大值/最大化最小值/第K小）
单调栈（基础/矩形面积/贡献法/最小字典序）
网格图（DFS/BFS/综合应用）
位运算（基础/性质/拆位/试填/恒等式/思维）
图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
链表、二叉树与一般树（前后指针/快慢指针/DFS/BFS/直径/LCA）
字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
洛谷题目
1P1094 [NOIP2007 普及组] 纪念品分组
知识点:1贪心配对 ： 当前最小价格（prices[left]）和最大价格（prices[right]）之和不超过上限w，则它们组成一组，同时移动双指针。若超过上限，则仅将最大价格的物品单独成组，移动右指针。
2双指针优化 ：通过左右指针逼近中间，快速遍历所有可能配对。
import java.util.Arrays;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 每组纪念品价格之和的上限
int w = scanner.nextInt();
// 纪念品的总件数
int n = scanner.nextInt();
int[] prices = new int[n];
for (int i = 0; i < n; i++) {
prices[i] = scanner.nextInt();
}
Arrays.sort(prices);
int left = 0;
int right = n - 1;
int groupCount = 0;
while (left <= right) {
if (left == right) {
// 只剩下一个纪念品，自成一组
groupCount++;
break;
}
if (prices[left] + prices[right] <= w) {
left++;
right--;
groupCount++;
} else {
// 如果两件纪念品价格和超过上限，单独把价格高的作为一组
right--;
groupCount++;
}
}
System.out.println(groupCount);
scanner.close();
}
}
//利用双指针
2P1515 旅行
动态规划（结果变化的统计）
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Main
{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 每天至少行驶的距离
int A = scanner.nextInt();
// 每天最多行驶的距离
int B = scanner.nextInt();
// 新增旅馆数量
int N = scanner.nextInt();
List<Integer> hotelList = new ArrayList<>();
//Arrays.asList()返回的List是固定大小的，不支持像常规的java.util.ArrayList那样的添
//加、删除元素的操作（调用add()、remove()等改变列表大小
hotelList.addAll(Arrays.asList(0, 990, 1010, 1970, 2030, 2940, 3060, 3930, 4060, 4970, 5030, 5990, 6010, 7000));
for (int i = 0; i < N; i++) {
hotelList.add(scanner.nextInt());
}
// 对旅馆位置列表进行排序
hotelList.sort(Integer::compareTo);
int[] dp = new int[hotelList.size()];
dp[0] = 1;
for (int i = 0; i < hotelList.size(); i++) {
for (int j = 0; j < i; j++) {
int distance = hotelList.get(i) - hotelList.get(j);
if (distance >= A && distance <= B) {
dp[i] += dp[j];//到第i个点的方法
}
}
}
System.out.println(dp[hotelList.size() - 1]);
scanner.close();
}
}
3 P1589泥泞路
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 泥泞路的段数
int L = scanner.nextInt(); // 木板的长度
int[][] muddyRoads = new int[n][2];
for (int i = 0; i < n; i++) {
muddyRoads[i][0] = scanner.nextInt();
muddyRoads[i][1] = scanner.nextInt();
}
Arrays.sort(muddyRoads, (a, b) -> a[0] - b[0]); // 按照起点对泥泞路信息排序
int count = 0; // 记录木板数量
int currentEnd = muddyRoads[0][0]-1;
for (int[] road : muddyRoads) {
// 当前已覆盖到的位置，初始化为第一段泥泞路起点前一个位置
// System.out.println(road[0]);
if (currentEnd<road[0]-1){
currentEnd=road[0]-1;
}
while (currentEnd < road[1]-1) {
currentEnd += L;
count++;
}
}
System.out.println(count);
scanner.close();
}
}
知识点：动态规划；lambda表达式
4 P1031 [NOIP2002 提高组] 均分纸牌
知识点：一 贪心算法:一旦记录了一次移动次数，后续步骤不会修改之前的决策。这种“一步一记录”的方式是贪心算法的典型特征。
二 、在遍历时，i的范围是0到N-1，但是移动次数的统计只考虑前N-1个元素的前缀和，因为最后一个堆（i=N-1）的sum必须为0（总和正确）。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int[] cards = new int[N];
int total = 0;
for (int i = 0; i < N; i++) {
cards[i] = scanner.nextInt();
total += cards[i];
}
int avg = total / N;
int currentSum = 0;
int moveCount = 0;
for (int i = 0; i < N; i++) {
//1，8，25，6
currentSum += cards[i] - avg;
// 前 N-1 堆中，若当前累积和不为零，则必须有一次移动
if (i < N - 1 && currentSum != 0) {
moveCount++;
}
}
System.out.println(moveCount);
}
}
5P1181 数列分段 Section I
知识点：贪心算法
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int M = scanner.nextInt();
int[] A = new int[N];
for (int i = 0; i < N; i++) {
A[i] = scanner.nextInt();
if (A[i] > M) { // 处理无法分割的情况
System.out.println(-1);
return;
}
}
int currentSum = 0;
int count = 0;
for (int i = 0; i < N; i++) {
if (currentSum + A[i] > M) {
count++;
currentSum = A[i];
} else {
currentSum += A[i];
}
}
count++; // 加上最后一段
System.out.println(count);
}
}
P9853方程求解
- 处理函数
- Set与List区别是是否可以存储重复的元素
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取方程数 n 和询问次数 Q
int n = scanner.nextInt();
int Q = scanner.nextInt();
scanner.nextLine(); // 消耗掉换行符
// 存储每个方程的解
Set<Integer> solutions = new HashSet<>();
// 解析每个方程并求解
for (int i = 0; i < n; i++) {
String equation = scanner.nextLine();
int solution = solveEquation(equation);
if (solution > 0) {
solutions.add(solution);
}
}
// 处理每次询问
for (int i = 0; i < Q; i++) {
int L = scanner.nextInt();
int R = scanner.nextInt();
int count = countSolutionsInRange(solutions, L, R);
System.out.println(count);
}
scanner.close();
}
// 求解单个方程
public static int solveEquation(String equation) {
// 去除空格
equation = equation.replaceAll("\ s", "");
// 找到等号位置
int equalIndex = equation.indexOf('=');
String left = equation.substring(0, equalIndex);
String right = equation.substring(equalIndex + 1);
// 解析方程左边的系数和常数
int a = 0, b = 0;
int index = 0;
boolean isNegative = false;
while (index < left.length()) {
if (left.charAt(index) == '-') {
isNegative = true;
index++;
} else if (left.charAt(index) == '+') {
isNegative = false;
index++;
}
if (left.charAt(index) == 'x') {
if (index == 0 || left.charAt(index - 1) == '+' || left.charAt(index - 1) == '-') {
a += (isNegative ? -1 : 1);
}
index++;
} else {
int numStart = index;
while (index < left.length() && Character.isDigit(left.charAt(index))) {
index++;
}
int num = Integer.parseInt(left.substring(numStart, index));
if (index < left.length() && left.charAt(index) == 'x') {
a += (isNegative ? -num : num);
index++;
} else {
b += (isNegative ? -num : num);
}
}
}
// 解析方程右边的常数
int c = Integer.parseInt(right);
// 求解方程 ax + b = c
if (a == 0) {
return -1; // 无解或无穷解
}
int x = (c - b) / a;
if ((c - b) % a != 0 || x <= 0) {
return -1; // 解不是正整数
}
return x;
}
// 计算在 [L, R] 范围内的解的数量
public static int countSolutionsInRange(Set<Integer> solutions, int L, int R) {
int count = 0;
for (int solution : solutions) {
if (solution >= L && solution <= R) {
count++;
}
}
return count;
}
}
力扣刷题
21.合并两个有序链表
知识点：递归
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null){
return l2;
}
if (l2 == null){
return l1;
}
if (l1.val> l2.val){
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}else {
l1.next = mergeTwoLists(l2,l1.next);
return l1;
}
}
26.删除有序数组中的重复项
知识点：双指针循环操作数组
public int removeDuplicates(int[] nums) {
int p = 0;
int q = 1;
while (q<nums.length){
if (nums[p]!=nums[q]){
nums[p+1] = nums[q];
p++;
}
q++;
}
return p+1;
}
67.二进制求和
知识点： 1通过减去字符'0'的 ASCII 码值来实现字符到数字的转换（活的ASCLL值的差）。2判断二进制是否进位
class Solution {
public String addBinary(String a, String b) {
StringBuilder ans = new StringBuilder();
int ca = 0; //是否进一位
for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
int sum = ca;
sum += (i >= 0 ? a.charAt(i) - '0' : 0); // 获取字符串a对应的某一位的值 当i<0是 sum+=0（向前补0） 否则取原值 ‘1’的char类型和‘0’的char类型刚好相差为1
sum +=( j >= 0 ? b.charAt(j) - '0' : 0);// 获取字符串a对应的某一位的值 当i<0是 sum+=0（向前补0） 否则取原值 ‘1’的char类型和‘0’的char类型刚好相差为1
ans.append(sum % 2); 如果二者都为1 那么sum%2应该刚好为0 否则为1
ca = sum / 2; //如果二者都为1 则用素描判断是否进位1 是则sum=2,不是则sum=1或者0
}
ans.append(ca == 1 ? ca : "");// 判断最后一次计算是否有进位 有则在最前面加上1 否则原样输出
return ans.reverse().toString();
}
}
69.x的平方根
知识点：
- 二分法,x≤2的32次方−1=2147483647
- 无符号右移运算符(>>>)当对一个整数进行
>>>操作时，它是将该整数的二进制表示向右移动指定的位数。例如，对于一个正整数n，n >>> 1的操作是将n的二进制位向右移动 1 位，左边空出来的位补 0。
class Solution {
public int mySqrt(int x) {
// 开区间 (left, right)
int left = 0;
int right = Math.min(x, 46340) + 1;
while (left + 1 < right) { // 开区间不为空
// 循环不变量：left^2 <= x
// 循环不变量：right^2 > x
int m = (left + right) >>> 1;
if (m * m <= x) {
left = m;
} else {
right = m;
}
}
// 循环结束时 left+1 == right
// 此时 left^2 <= x 且 right^2 > x
// 所以 left 最大的满足 m^2 <= x 的数
return left;
}
}
作者：灵茶山艾府
链接：https://leetcode.cn/problems/sqrtx/solutions/2942682/kai-qu-jian-er-fen-jian-ji-xie-fa-python-v4fb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
88.合并两个有序数组
思路：将数组二合并到数组一中从最后一个元素比较依次往前推，第一个while循环中因为数组二前面的元素较小导致大多数情况下会出现数组一大于数组二中元素与0的距离不会改变数组一的元素，所以再进行依次while数组循环将剩余的数组塞入数组一中。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int len1 = m - 1;
int len2 = n - 1;
int len = m + n - 1;
while (len1 >= 0 && len2 >= 0) {//判断两个都>=0作用防止数组溢出
if (nums1[len1] >= nums2[len2]) {
nums1[len] = nums1[len1];
len1--;
} else {
nums1[len] = nums2[len2];
len2--;
}
len--;
}
while (len2 >= 0) {
nums1[len] = nums2[len2];
len2--;
len--;
}//代码作用举例nums1[6,7,8,0,0,0],nums2[1,2,3]
}
}
//len*表示距离0下标的距离
94.二叉树中序遍历
知识点：深度有限搜索。从最深元素的开始加入数组。
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
dfs(list,res);
return list;`
}
void dfs(List<Integer> res,TreeNode root){
if(root == null){
return;
}
dfs(res,root.left);
res.add(root.val);
dfs(res,root.right);
}
}
100.相同的树
知识点：深度优先搜索；思路：先用条件判断，再深度循环下去
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p==null && q == null){
return true;
}
if (p==null || q==null){
return false;
}
if (p.val!=q.val){
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
101.对称二叉树
public boolean isSymmetric(TreeNode root) {
return isSameTree(root.left,root.right);
}
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p==null&&q==null){
return true;
}
if (p==null||q==null){
return false;
}
if (p.val!=q.val){
return false;
}
return isSameTree(p.left,q.right)&&isSameTree(p.right,q.left);
}
104.二叉树最大深度
public int maxDepth(TreeNode root) {
if (root==null){
return 0;
}
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
蓝桥杯官网题目
1029天干地支
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static String[] tg= {"jia","yi","bing","ding","wu","ji","geng","xin","ren","gui"};
static String[] dz= {"zi","chou","yin","mao","chen","si","wu","wei","shen","you","xu","hai"};
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n=scan.nextInt();
System.out.println(f(n));
scan.close();
}
static String f(int n) {
if (n==1960) {
return "gengzi";
}
int tgnum=6;
int dznum=0;
if (n>1960) {
for (int i = 1960; i <n; i++) {
if (tgnum==9)tgnum=0;
else tgnum++;
if(dznum==11)dznum=0;
else dznum++;
}
}else {
for (int i =n ; i <1960; i++) {
if (tgnum==0)tgnum=9;
else tgnum--;
if(dznum==0)dznum=11;
else dznum--;
}
}
return tg[tgnum]+dz[dznum];
}
}
2304X图形
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
char[][] chars = new char[n][m];
for (int i = 0;i<n;i++){
String str = scan.next();
char[] array = str.toCharArray();
for (int j = 0;j < m;j++){
chars[i][j] = array[j];
}
}
int sun = 0;
for (int i = 1;i < n-1;i++){
for (int j = 1;j<m-1;j++){
int k = 1;
while (i-k >= 0 && i+k <= n-1 && j-k >= 0 && j+k <= m-1){
if (chars[i][j] == chars[i-k][j-k] && chars[i][j] == chars[i-k][j+k]
&& chars[i][j] == chars[i+k][j-k] && chars[i][j] == chars[i+k][j+k]){
k++;
sun+=1;
}
else {
break;
}
}
}
}
System.out.println(sun);
}
}
显示时间
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
long tim = scan.nextLong();
long hh,mm,ss,h,m,s;
ss = tim/1000;
mm = ss/60;
hh = mm/60;
s = ss%60;
m = mm%60;
h = hh%24;
String date = String.format("%02d", h)+":"+String.format("%02d", m)+":"+String.format("%02d", s);
System.out.println(date);
scan.close();
}
540计算三角形面积
海伦公式
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
double a;
double b;
double c;
a = scan.nextDouble();
b = scan.nextDouble();
c = scan.nextDouble();
// System.out.printf("%f,%f,%f",a,b,c);
double p = (a+b+c)/2;
double S = Math.sqrt(p*(p-a)*(p-b)*(p-c));
System.out.printf("%.2f",S);
scan.close();
}
2406字母数
1452字母数
19933 赏花宴
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), q = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int[] quire = new int[q];
Integer[] idx = new Integer[q];
for (int i = 0; i < q; i++) {
quire[i] = sc.nextInt();
idx[i] = i;
}
Arrays.sort(a);
Arrays.sort(idx);
int[] ans = new int[q];//记录每个询问结果
for (int i = 0, j = 0, cnt = 0, x = 0; i < q; i++) {//cnt当前编号未出现数量,x 是当前遍历到的编号的前一个值
int id = idx[i], k = quire[id];//k获取当前查询的原始索引 id 和对应的 k 值。
while (j < n && cnt < k) {//内层循环用于计算未出现的编号数量，只要数组 a 还没遍历完且统计的未出现编号数量小于 k 就继续循环。
int v = Math.max(a[j] - (j - 1 >= 0 ? a[j - 1] : 0) - 1, 0);//计算当前编号和a[j]和前一个编号中间少多少个// 防止数组溢出
cnt += v;
x = a[j] - 1;
j++;
}
ans[id] = cnt >= k ? (x - (cnt - k)) : (x + (k - cnt) + 1);
}
for (int i = 0; i < q; i++) {
System.out.println(ans[i]);
}
}
4364 区间连续子字符串
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
scan.nextLine(); // 消耗换行符
String s = scan.nextLine();
char[] chars = s.toCharArray();
for (int i = 0; i < m; i++) {
int l = scan.nextInt() - 1; // 转换为0-based索引
int r = scan.nextInt() - 1; // 转换为0-based索引
char c = scan.next().charAt(0); // 正确读取字符
// 更新字符串的指定区间
for (int j = l; j <= r; j++) {
chars[j] = c;
}
// 计算最长连续子串长度
int maxLen = 1;
int currentLen = 1;
for (int j = 1; j < chars.length; j++) {
if (chars[j] == chars[j - 1]) {
currentLen++;
maxLen = Math.max(maxLen, currentLen);
} else {
currentLen = 1;
}
}
System.out.println(maxLen);
}
scan.close();
}
全部评论 (0)
还没有任何评论哟~