文章目录
- 一、数据结构
- 1. 哈希表
- 2. 堆
- 二、对象数组排序
- 三、时间相关
- 1. String转Date
- 2. Date转String(标准格式化)
- 3. Calender类（日历，星期）
- 4. 计算时间间隔
- 四、字符串
- 1.int和String的互相转换
- 2.判断一个字符串是否是回文
- 五、 BigInteger与BigDecimal
- 1.BigInteger
- 2.BigDecimal
- 六 、质数和公约数
- 1.判断一个数是否是质数
- 2.求两个数的最大公约数
- 3.分解质因数
- 七 、BFS和回溯DFS框架
- 回溯DFS
- BFS
后天就是蓝桥杯国赛了，记录一下java可能会用到的基础知识，时间匆忙，如有错处，欢迎批评指正
蓝桥杯大赛历届真题
一、数据结构
栈和和队列可以用Linkedlist实现
1. 哈希表
分为HashSet和HashMap
Set<Integer> set=new HashSet<Integer>();set.add(1);//添加元素set.remove(1);//删除元素if(set.contains(1)) {...}//判断是否包含某个元素int len=set.size();//获得集合长度Map<Character,Integer> map=new HashMap<Character,Integer>();map.put('a', 1);int num1=map.get('a');int num2=map.getOrDefault('a',0);map.replace('a',2);map.remove('a');2. 堆
使用优先队列(PriorityQueue)实现，默认是小根堆
Queue<Integer> q=new PriorityQueue<Integer>();//创建一个小根堆Queue<Integer> q=new PriorityQueue<Integer>((e1,e2)->e2-e1);//创建一个大根堆//(e1,e2)->e2-e1代表升序，可以自定义其他排序规则二、对象数组排序
快速对对象数组进行升序排序，使用Arrays.sort()函数
Arrays.sort(Object[] a,Comparator<? super T> c);//使用该参数时，排序的只能是对象数组// 以第一列排序int[][] a = new int[][]{{2, 1}, {1, 2}};Arrays.sort(a, (e1, e2) -> e1[0] - e2[0]);Integer[] i=new Integer[]{1,3,2};Arrays.sort(i,(e1,e2)->e2-e1);//注意int数组只能转为Integer数组才能使用该表达式int[][] a=new int[][]{{3,1},{3,2},{1,2}};Arrays.sort(a,(e1,e2)->{ if(e1[0]==e2[0])return e2[1]-e2[1];//若第一列相同按第二列排序 return e1[0]-e2[0];//按第一列排序});三、时间相关
参考：https://blog.csdn.net/Mxeron/article/details/122798649
1. String转Date
import java.text.ParseException;import java.text.SimpleDateFormat;String s1 = "2021-7-24";String s2 = "2022-7-24";//yyyy-MM-dd，注意MM必须大写SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");// 转换成date1需要抛出异常try { Date date1 = sdf.parse(s1);} catch (ParseException e) { e.printStackTrace();}2. Date转String(标准格式化)
Date date = new Date(120000000);SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");System.out.println(sdf.format(date));3. Calender类（日历，星期）
Calender的月份MONTH是从0开始，也就是1-12月对应 0-11，但日期和年份是从1开始的。DAY_OF_WEEK从1开始，也就是周日到周六对应 1-7。
周日是1，周一是2，周六是7。1月是0，12月是11。
// 创建Calendar实例Calendar c = Calendar.getInstance();// 用日期赋值2021年7月1日，或者是用Date赋值c.setTime(Date date);c.set(2021, 7 - 1, 1);System.out.println(c.get(Calendar.YEAR));//年System.out.println(c.get(Calendar.MONTH) + 1);//月System.out.println(c.get(Calendar.DATE));//日System.out.println(c.get(Calendar.DAY_OF_WEEK));// 星期几，1是星期日// 这年的第几天，从1开始算System.out.println(c.get(Calendar.DAY_OF_YEAR));// 这个月的第几天，从1开始算System.out.println(c.get(Calendar.DAY_OF_MONTH));// 这个月的第几周，从1开始算System.out.println(c.get(Calendar.DAY_OF_WEEK_IN_MONTH));4. 计算时间间隔
主要是通过使用SimpleDateFormat，先把时间写成String，然后再转成Date， 用getTime函数转成毫秒，相减得到相差的毫秒数。注意1s = 1000ms，SimpleDateFormat中，HH代表24小时制，hh是12小时制，MM是月份，mm是分钟。
String start = "2021-7-13 13:14:20";String end = "2021-7-10 13:14:20";// 注意HH是24小时，hh是12小时SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");Date date1 = sdf.parse(start);Date date2 = sdf.parse(end);// 因为不知道谁大谁小，所以要用abslong diff = Math.abs(date1.getTime() - date2.getTime());System.out.println("相差" + diff + "毫米");// 注意1s = 1000mslong seconds = diff / 1000;//秒long minutes = diff / 1000 / 60;//分钟long hours = diff / 1000 / 60 / 60;//小时long day = diff / 1000 / 60 / 60 / 24;//天四、字符串
1.int和String的互相转换
//int转Stringint i=1; String s=""+i://String转intString s=”3”;int i=Integer.parseInt(s);2.判断一个字符串是否是回文
方法一：判断字符串的i到j位是否是回文
public static boolean isPalindrome(String s, int i, int j){ while(i<j){ if(s.charAt(i)!=s.charAt(j)){ return false; } i++;j--; } return true; }方法二：快速判断，一个数字是否是回文
class Solution { public boolean isPalindrome(int x) { StringBuffer s=new StringBuffer(Integer.toString(x)); String a=s.toString();//创建一个新字符串记录原来的值 return a.equals(s.reverse().toString())?true:false; }}五、 BigInteger与BigDecimal
大整数题目
1.BigInteger
import java.math.BigInteger;import java.util.Scanner;public class Main { public static void main(String[] args) { // 传入字符串才能形成大数，默认是把字符串当成十进制 BigInteger bs = new BigInteger("15666666666666666"); BigInteger bs1 = new BigInteger("100002123123123"); //加减乘除 bs.add(bs1);bs.subtract(bs1);bs.multiply(bs1);bs.divide(bs1);//取商 // 取余 bs.mod(bs1);bs.remainder(bs1); // 返回大整数的double、float类型 bs.doubleValue();bs.floatValue(); // 求最大公约数 bs.gcd(bs1); // 9、将当前大整数转成十进制字符串形式 System.out.println(bs.toString()); // 也可以把字符串当成二进制传入，生成十进制大数 BigInteger bs2 = new BigInteger("100000", 2); System.out.println(bs2); }}2.BigDecimal
对BigDecimal做加、减、乘时，精度不会丢失，但是做除法时，存在无法除尽的情况，这时，就必须指定精度以及如何进行截断。
package Chapter_5;import java.math.BigDecimal;import java.math.BigInteger;import java.math.RoundingMode;import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); // 大小数 BigDecimal bs = scan.nextBigDecimal(); // 获取小数位数，如果是整数则输出负数，表示末尾0的个数 System.out.println(bs.scale()); // 去掉小数末尾无用的0 System.out.println(bs.stripTrailingZeros()); // 设置小数位数，可以选择四舍五入或者直接截断 System.out.println(bs.setScale(4, RoundingMode.HALF_UP)); // 四舍五入 // 对BigDecimal做加、减、乘时，精度不会丢失，但是做除法时，存在无法除尽的情况，这时，就必须指定精度以及如何进行截断。 BigDecimal d1 = new BigDecimal("123.456"); BigDecimal d2 = new BigDecimal("23.456789"); BigDecimal d3 = d1.divide(d2, 10, RoundingMode.HALF_UP); //保留10位小数并四舍五入 BigDecimal d4 = d1.divide(d2); // 报错：ArithmeticException，因为除不尽 //比较两个BigDecimal，不能用equals()因为小数的个数问题，要用compareTo() //它根据两个值的大小分别返回负数、正数和0，分别表示小于、大于和等于 d1.compareTo(d2) }}六 、质数和公约数
参考
https://blog.csdn.net/GD_ONE/article/details/104579936
https://blog.csdn.net/Mxeron/article/details/122798649
1.判断一个数是否是质数
假设该数为n， 我们只需要判断[2,sqrt{n}]内是否有n的因子。如果有，则n为合数，否则，n为质数。这种方法被称为试除法， 即试着除一下所有可能的因子。
public static Boolean isprime(int n){ if(n == 1) return false; for(int i = 2; i<= n/i ; i++){ if(n % i == 0){ return false; } } return true;}2.求两个数的最大公约数
//递归（返回最大公约数）int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}3.分解质因数
设一个质数为p.如果n%p == 0，那么p就是n的一个质因数，接下来就是求p的指数，我们让n = n/p, 这样就从n中剔除了一个p,接着重复上述两步，直到n%p ！= 0
public static void prime(int n){ for(int i = 2; i <= n/i ; i++){//判断条件用n/i，以防i*i<=n发生溢出 int a = 0;//每次循环都要清零 while(n % i == 0){ n /= i; a++; } if(a > 0) System.out.println(i + "" + a);//i的a次方 } //若该数是质数，那么应该将自身(n)也加入 if(n > 1) System.out.println(n + " " + 1);}七 、BFS和回溯DFS框架
回溯DFS
回溯算法框架。解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
代码方面，回溯算法的框架：result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择BFS
本质上就是一幅「图」，让你从一个起点，走到终点，问最短路径，这就是 BFS 的本质。
图可能会走回头路，所以要用visited数组存储已经访问过的节点。
/ 计算从起点 start 到终点 target 的最近距离int BFS(Node start, Node target) { Queue q; // 核心数据结构 HashSet visited; // 保存已经访问过的节点，避免走回头路 q.offer(start); // 将起点加入队列 visited.add(start); int step = 0; // 记录扩散的步数 while (!q.isEmpty) { int sz = q.size(); /* 将当前队列中的所有节点向四周扩散 */ for (int i = 0; i < sz; i++) { Node cur = q.poll(); /* 划重点：这里判断是否到达终点 */ if (cur is target) return step; /* 将 cur 的相邻节点加入队列 */ for (Node x : cur.adj()) if (x not in visited) { q.offer(x); visited.add(x); } } /* 划重点：更新步数在这里 */ step++; }}