蓝桥杯知识总结

---

1.常用的数学方法

方法	返回值	功能描述
max (double a,double b)	double	取a与b之间的最大值
min (int a,int b)	int	取a与b之间的最小值
abs (int a)	int	返回整数参数的绝对值
sqrt (double a)	double	用于取a的平方根，其中a不能为负值
cbrt (double a)	double	用于取a的立方根
pow(double a,double b)	double	用于取a的b次方
round()		四舍五入

---

2.大小写转换

📕转换方法
String类的toLowerCase()方法将字符串中的字母全部转换为小写
String类的toUpperCase()方法将字符串中的字母全部转换为大写

📕异或转换
如果要将字符串内某个英文大写字符转换为小写，或小写转为大写，更简便的方法就是异或转换了，方法如下：

一个字符a异或数字32就可以完成大小写转换

实例：

char A='a'^32;
char a='A'^32;

是不是有人跟我一样，疑问为什么要异或32，这是因为啊，在ASCII表里，第一个大写字母与第一个小写字母之间的ASCII值刚好相差32，而不是26

3.数组和集合排序

数组排序

• 方法一：升序

Arrays.sort(int[] a)：对一个数组所有元素进行从小到大排序

import java.util.Arrays;public class Main {public static void main(String[] args) {int[] a={9,8,7,5,3,6,2,1,0};Arrays.sort(a);for(int i=0;i<a.length;i++){System.out.print(a[i]+" ");}}
}

• 方法二：用Comparator接口实现自定义排序规则

例如降序

import java.util.Arrays;
import java.util.Comparator;public class Main {public static void main(String[] args) {//不能使用基本类型intInteger[] a={9,8,7,5,3,6,2,1,0};//降序Arrays.sort(a, new Comparator<Integer>() {//重写compare方法@Overridepublic int compare(Integer o1, Integer o2) {//返回值>0交换//如果我们要升序排序，下面return写o1-o2就行return o2-o1;}});System.out.println(Arrays.toString(a));}
}

• 方法三：用lambda实现升序或降序

例如升序

import java.util.Arrays;public class Main {public static void main(String[] args) {//不能使用基本类型intInteger[] a={9,8,7,5,3,6,2,1,0};//如果降序的话，下面就是o2-o1//升序Arrays.sort(a,(o1,o2)->o1-o2);for(int i=0;i<a.length;i++){System.out.print(a[i]+" ");}}
}

集合排序

• 方法一：升序

Collections.sort(List<> a)：对一个集合所有元素进行从小到大排序

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class Main {public static void main(String[] args) {List<Integer> list=new ArrayList<>();list.add(5);list.add(9);list.add(4);list.add(8);list.add(2);list.add(1);list.add(7);Collections.sort(list);for(int i=0;i<list.size();i++){System.out.print(list.get(i)+" ");}}
}

• 方法二：用Comparator接口实现自定义排序规则

例如降序

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;public class Main {public static void main(String[] args) {List<Integer> list=new ArrayList<>();list.add(5);list.add(9);list.add(4);list.add(8);list.add(2);list.add(1);list.add(7);Collections.sort(list, new Comparator<Integer>() {//重写compare方法@Overridepublic int compare(Integer o1, Integer o2) {//返回值>0交换//如果我们要升序排序，下面return写o1-o2就行return o2-o1;}});for(int i=0;i<list.size();i++){System.out.print(list.get(i)+" ");}}
}

• 方法三：用lambda实现升序或降序

例如降序

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class Main {public static void main(String[] args) {List<Integer> list=new ArrayList<>();list.add(5);list.add(9);list.add(4);list.add(8);list.add(2);list.add(1);list.add(7);Collections.sort(list,(o1,o2)->o2-o1);for(int i=0;i<list.size();i++){System.out.print(list.get(i)+" ");}}
}

4.控制小数位数

在Java中，可以使用 String.format()方法来控制输出的小数位数
例如：保留两位小数

public class GDPComparison {public static void main(String[] args) {double growthRate = 0.07; // 年增长率为7%int years = 10; // 年数为10年double comparison = Math.pow(1 + growthRate, years);double percentageIncrease = (comparison - 1) * 100; // 计算增长百分比// 格式化输出保留两位小数String formattedPercentage = String.format("%.2f", percentageIncrease);String formattedComparison = String.format("%.2f", comparison);System.out.println("10年后国民生产总值与现在相比增长了 " + formattedPercentage + "%");System.out.println("10年后国民生产总值与现在相比的倍数为 " + formattedComparison);}
}

5.栈

Stack实例化步骤
1.导包，导入import java.util.*
2.实例化对象Stack<引用数据类型> stack=new Stack<>();

对于Stack存储数据，是先进后出.比如1，2，3依次入栈，出栈顺序是3，2，1

📕常用方法
Object push(Object element)把对象压入堆栈顶部
Object pop()移除堆栈顶部的对象，并作为此函数的值返回该对象
Object peek()查看堆栈顶部的对象，但不从堆栈中移除它
boolean isEmpty()测试堆栈是否为空

6.队列

Queue实例化步骤
1.导包，导入import java.util.*
2.通过LinkedList类创建对象，Queue<引用数据类型> queue=new LinkedList<>();

对于Queue存储数据，是先进先出.比如1，2，3依次入栈，出栈顺序是1，2，3

📕常用方法
boolean add(Object element)从队尾压入元素，返回是否压入成功
Object poll()删除并返回队头被删除的那个元素
Object peek()返回队头元素，但是不删除
boolean isEmpty()测试队列是否为空

7.字符串相关方法

🍓转化为字符数组

 String s="ffffewgweegewr32d";char[] ch = s.toCharArray();

8.十进制转n进制模板

	public static String con(int x,int n){StringBuilder str1=new StringBuilder();while(x>0){str1.append(x%n);//获取每一位的值x/=n;}return str1.reverse().toString();//返回反转字符串}

字符转为十进制

public class Main {public static void main(String[] args) {String input = "*+";int codePoint = input.codePointAt(0);// 获取字符串中第一个字符的 Unicode 码点int codePoint1 = input.codePointAt(1);// 获取字符串中第一个字符的 Unicode 码点System.out.println("字符： " + input.charAt(0) + ", 十进制值： " + codePoint);System.out.println("字符： " + input.charAt(1) + ", 十进制值： " + codePoint1);}
}

某进制转化为十进制

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);String rs="2022";System.out.println(Integer.parseInt(rs,某进制));scan.close();}
}

9.前缀和

前缀和作用：在O(1)的时间求出数组任意区间的区间和

🍓算法模板

		int n=10;int[] arr=new int[n];long[] sum=new long[n+1];for (int i = 1; i <=n; i++) {sum[i]=sum[i-1]+arr[i-1];}

10.差分

差分的用处主要在于：快速将数组A的区间[l,r]加d（即把Al，A(l+1)…Ar这几个元素各加上d）

🍓算法模板

public static void chaifen1(int[] arr,int l,int r,int d) {arr[l]+=d;arr[r+1]-=d;//对差分数组求前缀和，还原序列for(int i=1;i<n;i++) {diff[i]+=diff[i-1];}}

11.离散化

🍓例题

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n = sc.nextInt();int []arr=new int[n];int []a=new int[n];Set<Integer> set=new HashSet<>();for (int i = 0; i <n; i++) {arr[i]=sc.nextInt();a[i]=arr[i];}Arrays.sort(a);Map<Integer,Integer>map=new HashMap<>();for (int i = 0; i < n; i++) {set.add(a[i]);map.put(a[i], set.size());}for (int i = 0; i < n; i++) {System.out.print(map.get(arr[i])+" ");}}
}

12.双指针

双指针通常用于在数组或字符串中进行快速查找、匹配、排序或移动操作。
双指针并非真的用指针实现，一般用两个变量来表示下标（在后面都用指针来表示），双指针算法使用两个指针在数据结构上进行迭代，并根据问题的要求移动这些指针。
双指针往往也和单调性、排序联系在一起，在数组的区间问题上，暴力法的时间复杂度往往是O(n^2)的，但双指针利用单调性可以优化到O(n)
🍌常见的双指针模型有：
（1）对撞指针
（2）快慢指针

• 对撞指针
  指的是两个指针left、right(简写为l, r)分别指向序列第一个元素和最后一个元素，然后l指针不断递增, r不断递减，直到两个指针的值相撞或错开（即l >=r)，或者满足其他要求的特殊条件为止。
  对撞指针一般用来解决有序数组或者字符串问题（常见于区间问题):
  查找有序数组中满足某些约束条件的一组元素问题:比如二分查找、数字之和等问题，字符串反转问题:反转字符串、回文数等问题。

• 快慢指针
  快慢指针一般比对撞指针更难想，也更难写。
  指的是两个指针从同一侧开始遍历序列，且移动的步长一个快一个慢。移动快的指针被称为快指针，移动慢的指针被称为慢指针。
  为了方便理解，我们称快指针为r，慢指针为l，这样慢指针和快指针构成区间[l,r]
  两个指针以不同速度、不同策略移动，直到快指针移动到数组尾端，或者两指针相交，或者满足其他特殊条件时为止。

13.二分

二分算法：是用来在一个有序数组中查找某一元素的算法，时间复杂度O(log n)
在数学上的解释：对于区间[a, b]上单调的函数y=f(x)，通过不断地把函数f(x)的区间一分为二，使区间的两个端点逐步逼近,进而得到近似值的方法叫二分法

🍓二分的模板（一）

查找当前有序数组中大于等于x的第一个数

		int[] arr={1,2,3,4,5};int l=0,r=arr.length-1;int x=2;while (l<r){int mid=(l+r)/2;//取区间中间位置靠左的值if(arr[mid]>=x)r=mid;//区间向左缩短一半else l=mid+1;//区间向右缩短一半}

🍓二分的模板（二）

查找当前有序数组中小于等于x的最后一个数

		int[] arr={1,2,3,4,5};int l=0,r=arr.length-1;int x=2;while (l<r){int mid=(l+r+1)/2;//取区间中间位置靠右的值if(arr[mid]>x)r=mid-1;//区间向左缩短一半else l=mid;//区间向右缩短一半}

🍓整数二分法常用模板

// 在单调递增序列a中查找>=x的数中最小的一个（即x或x的后继）
while (low < high) {int mid = (low + high) / 2;if (a[mid] >= x)high= mid;elselow = mid + 1;
}// 在单调递增序列a中查找<=x的数中最大的一个（即x或x的前驱）
while (low < high) {int mid = (low + high + 1) / 2;if (a[mid] <= x)low = mid;elsehigh = mid - 1;}

14.枚举模板

组合型枚举模板

组合型枚举则是在n个元素中随机选出 m个元素的问题。对于每一种可能的选择方案，我们需要确定选择了哪m个元素，这就是组合型枚举，即从n个元素中选择m个元素的组合数量。
🍓Python

chosen = []
n = 0
m = 0def calc(x):if len(chosen) > m:returnif len(chosen) + n - x + 1 < m:returnif x == n + 1:for i in chosen:print(i,end=' ')print('')returnchosen.append(x)calc(x + 1)chosen.pop()calc(x + 1)if __name__ == '__main__':tem = input().split()n = int(tem[0])m = int(tem[1])calc(1)

🍓java

import java.util.Scanner;
import java.util.Vector;
public class Main {static  int n;static int m;//选m个数static Vector<Integer> chosen = new Vector<Integer>();static  void calc(int x) {if (chosen.size() > m || chosen.size() + (n - x + 1) < m) //剪枝return;if (x == n + 1) { //选够了m个数输出String ansTem = "";for (int i = 0; i < chosen.size(); i++)System.out.print(chosen.get(i)+" ");System.out.println("");return;}chosen.addElement(x);calc(x + 1);chosen.remove((Object)x);calc(x + 1);}public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();m = in.nextInt();calc(1);}
}

🍓c语言

#include<bits/stdc++.h>
using namespace std;
int n;//共计N个数
int m;//选m个数
vector<int> chosen;
string s[1000];
void calc(int x) {if (chosen.size() > m || chosen.size() + (n - x + 1) < m) //剪枝return;if (x == n + 1) { //选够了m个数输出for (int i = 0; i < chosen.size(); i++)cout<< s[chosen[i]]<<" ";//也可以不输出，存放起来也是可以的，主要是看题目。puts("");return;}chosen.push_back(x);calc(x + 1);chosen.pop_back();//消除痕迹calc(x + 1);
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i];}calc(1);
}

排列型枚举模板

🍓Python

order = [0] * 20
chosen = [0] * 20
n = 0
def calc(x):if x == n + 1:ansTem = ''for i in range(1, n + 1):print(order[i],end=' ')print('')returnfor i in range(1,n+1):if(chosen[i]==1) :continueorder[x]=ichosen[i]=1calc(x+1)chosen[i]=0order[x]=0
if __name__ == '__main__':n = int(input())# print(name)calc(1)

🍓C语言

int n; //共计N个数
int order[20];
bool chosen[20];
void calc(int k)
{if (k == n + 1){for (int i = 1; i <= n; i++)cout << order[i] << " ";puts("");return;}for (int i = 1; i <= n; i++){if (chosen[i])continue;order[k] = i;chosen[i] = 1;calc(k + 1);chosen[i] = 0;order[k] = 0;}
}
int main()
{cin >> n;calc(1);
}

🍓java

  static  int n;static int[] order =new int[20];static boolean[] chosen =new boolean[20];static Vector<String> name=new Vector<>();static <object> void calc(int x) {if (x == n + 1) { //选够了m个数输出String ansTem = "";for (int i = 1; i <=n ; i++)System.out.println(order[i]);return;}for (int i = 1; i <= n; i++) {if (chosen[i]) continue;order[x] = i;chosen[i] =true;calc(x + 1);chosen[i] = false;order[x] = 0;}}public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();for (int i = 0; i < n; i++) {String s;s=in.next();name.addElement(s);}calc(1);}

15.搜索算法

BFS

宽度优先搜索（广度优先搜索）

DFS

深度优先搜索

16.快速幂

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);long b=scanner.nextLong(),p=scanner.nextLong(),k=scanner.nextLong();System.out.println(fastPow(b,p,k));scanner.close();}public static long fastPow(long a,long n,long mod) {long ans=1;a%=mod;//重要，防止下面的ans*a越界while(n>0) {if((n&1)==1) {ans=(ans*a)%mod;//取模}a=(a*a)%mod;//取模n>>=1;}return ans;}
}

17.小结论总结

🍓例题
对于互质的两个数a和b，其不能组成的最大整数为a*b-a-b

🍓同余定理
同余定理——想要 b - a为 k 的倍数，只需要确保 b 和 a 模 k 相同即可