微风撞见云的算法小笔记
前言
本篇内容是我学了一段时间算法以后，自己总结的心得，**（主要是以前记录给自己看的笔记）**可能有些地方没写的太好，请大家见谅！如有想深入了解的地方，直接搜索相关内容学习即可！
刚接触算法的时候没人带，大二参加过蓝桥杯，硬是用语法硬顶，拿了个省二。后来学了一段时间算法，参加“计算机能力挑战赛java程序设计”获得决赛一等奖。虽然这些比赛含金量不高，但我还是想把我辛苦记录的笔记分享给大家！如果对你有帮助，希望可以点个赞支持一下~
刷题的话，看你是哪种比赛了，蓝桥杯那种建议你先刷蓝桥里面的题试试，因为leetcode上面不会要求你输入数据来使用，都是直接给你数据，让你写出方法即可，但是蓝桥杯那一类的OI需要你对输入的数据有一定的处理能力，这点很重要。并且不要盲目刷题、不要盲目刷题、不要盲目刷题！！！ 重要的事情说三遍！正确的做法是学一类刷一类，比如我最近两天刷dfs的，感觉差不多了再刷dp的，以此类推。
正片开始 ↓
🍏一、命题范围
#🍏 二、注意事项
🍏三、快捷键系列
Idea快捷键
public class 快捷键 { /** * ctrl+shift+enter 代码结尾补全 * ctrl+shift+Alt+J 修改同名变量 * Alt + Enter 引入类 * Ctrl+F 和 Ctrl + R 查找和替换 * ctrl + Alt + L 代码格式格式换 * ctrl + D 复制本代码到下一行 * shift + Alt + ↑或↓ 代码上下移动 * 数组名.for 快速遍历数组 * Alt + Insert set/get; 构造方法; toString; 重写方法。。。 * Ctrl+Alt+T 将代码包在一个块中，例如 while, if, try/catch等 * psvm 主函数 * sout 输出语句 * 给一小段代码添加() {} [],只需要选中该部分代码，然后按( { [ 即可。 * 在()内直接按;可以在代码末尾添加; */ }
Eclipse快捷键
public class Zfast { /** * alt + ctrl + ↓ 复制当前行到下一行 * alt + ↓ 移动当前行到下一行 * ctrl + shift +f 格式化 * alt + shift + a 块选择 * ctrl + 1 创建对象等补全提示 new ArrayList<>();在这里按ctrl + 1 */ }
🍏四、常用知识点、代码工具、思想套路（重点一）
提取方法时注意参数的传递，思考是否是地址传递，改变该变量后会不会改变其他地方的同名变量。
StreamTokenizer(推荐快读)
StreamTokenizer 不要和 BufferedReader 混用！！！ 如果是读取纯字母或纯数字，那就用StreamTokenizer， 否则别用，return null; 稳定快读 注意：StreamTokenizer 需要先“获取下一组标记”，才能读到内容 --> in.nextToken(); 读数值类型：in.nval; 【默认解析为double类型】 读String类型：in.sval;
基本用法： StreamTokenizer in =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); // 获取下一组标记 默认是按照空格分割的 回车，tab是结束符 int i=(int) in.nval; //st.navl默认解析出的格式是double in.nextToken(); double j=in.nval; in.nextToken(); String s=in.sval;
demo： public class Main{ static int n, m; static String[][] a = new String[2][2]; static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); public static void main(String[] args) throws IOException { in.nextToken(); n = (int) in.nval; in.nextToken(); m = (int) in.nval; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { in.nextToken(); a[i][j] = in.sval; } } for (String[] ints : a) { for (String anInt : ints) { System.out.print(anInt + " "); } System.out.println(); } } } 输入： 2 2 a b c d 或 2 2 a b c d 输出： a b c d
BufferedReader
//②BufferedReader------>推荐使用！！！！！ static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); bw.write(String.valueOf(i + " ")); bw.flush(); bw.close(); br.close(); public static void main(String[] args) throws IOException { String s[] = br.readLine().split(" "); int a = Integer.valueOf(s[0]),b = Integer.valueOf(s[1]); char c = Character.valueOf(s[2].charAt(0)); System.out.println(c); bw.flush();//把缓冲区的内容强制的写出。 bf.close(); bw.close();
Scanner
0、无限输入，回车结束
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (true) { String next = scanner.nextLine(); if (!next.equals("")) System.out.println("有效"); else break; } }
1、输入整数、字符串数组
第一行输入n, m
第二行输入n个整数
第三行输入m个字符串
//导入包 import java.util.Scanner; import java.util.Arrays; public class MyScanner { public static void main(String[] args) { //创建对象 Scanner sc = new Scanner(System.in); System.out.println("输入数据:"); //多行输入 int n = sc.nextInt(); int m = sc.nextInt(); int[] arr = new int[n]; String[] str = new String[m]; //int等基本数据类型的数组,用nextInt()，同行或不同都可以 for(int i=0; i<n; i++) { arr[i] = sc.nextInt(); } //String字符串数组, 读取用next()，以空格划分 for(int i=0; i<m; i++) { str[i] = sc.next(); } //调用方法进行操作 TestSc(n, m, arr); TestStr(str); System.out.println("Test01 End"); //关闭 sc.close(); } public static void TestSc(int n, int m, int[] arr) { System.out.println("数据n：" + n + ", 数据m：" + m); System.out.println(Arrays.toString(arr)); } public static void TestStr(String[] str) { System.out.println(Arrays.toString(str)); } }
若输入的字符串中想要包含空格，使用scanner.nextLine()换行后用scanner.nextLine()进行读入，见情形7.
2、输入二维数组
第一行输入n, m
第二行开始输入二维数组。
import java.util.Arrays; import java.util.Scanner; public class MyScanner2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("输入数据:"); //二维数组 int n = sc.nextInt(); int m = sc.nextInt(); int[][] arr2 = new int[n][m]; System.out.println("Test02 输入二维数组数据："); //可以直接读入 for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { arr2[i][j] = sc.nextInt(); } } TestSc(n, m, arr2); //关闭 sc.close(); } public static void TestSc(int n, int m, int[][] arr) { System.out.println("数据n：" + n + ", 数据m：" + m); for(int i=0; i<n; i++) { System.out.println(Arrays.toString(arr[i])); } System.out.println("数组行数： arr.length= "+ arr.length); System.out.println("数组列数： arr[0].length= "+ arr[0].length); } }
3、输入字符串
输入字符串，用空格隔开。
next()和nextLine()区别。
import java.util.Scanner; /* *next()读取到空白停止，在读取输入后将光标放在同一行中。 *nextLine()读取到回车停止 ，在读取输入后将光标放在下一行。 */ public class MyScanner3 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("输入字符串:"); //next():只读取输入直到空格。 String str = sc.next(); //nextLine():读取输入，包括单词之间的空格和除回车以外的所有符号 String str2 = sc.nextLine(); System.out.println("str：" + str); System.out.println("str2：" + str2); //关闭 sc.close(); } }
4、输入字符串分割为数组
先用scanner.nextLine()读入字符串，再将字符串分割为字符数组或字符串数组。
import java.util.*; public class MyScanner4 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("输入字符串数组："); String str; str = sc.nextLine(); char[] ch = new char[str.length()]; for(int i=0; i<str.length(); i++) { //用charAt();进行定位分隔 ch[i] = str.charAt(i); System.out.println(ch[i] + " "); } System.out.println("END"); //读入字符串后,用空格分隔为数组 String[] strs = str.split(" "); System.out.println(Arrays.toString(strs)); } }
5、连续输入数字和字符串
区别于情形1，对于不能采用for循环的方式获取String。采用情形5,6用来处理。
采用while(scanner.hasNext()) 循环，实现连续输入。
格式：数字，空格，字符串。
或： 数字，回车，字符串
import java.util.Scanner; public class MyScanner5 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int n = sc.nextInt(); String str = sc.next(); Tes(n, str); } sc.close(); } public static void Tes(int n, String str) { System.out.println("n = " + n); System.out.println("str = " + str); System.out.println("str.length = " + str.length()); } }
6、换行输入数字和字符串
也采用scanner.nextLine()，将光标移到下一行。再继续读入字符串。
第一行输入整数n，m，第二行开始输入字符串。或第一行输入整数n，第二行输入m，第三行开始输入字符串。
import java.util.*; public class MyScanner6 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); //注意！！！光标换到下一行 sc.nextLine(); String s = sc.nextLine(); String str = sc.nextLine(); System.out.println("n = " + n + " , m = " + m); System.out.println("s = " + s); System.out.println("str = " + str); sc.close(); } }
7、换行输入数字和字符串(需要包含空格)
采用scanner.nextLine()，将光标移到下一行。再继续读入字符串。
第一行输入n，
第二行开始输入n行字符串，字符串中包含空格。
import java.util.Scanner; public class MyScanner7 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String[] strs = new String[n]; sc.nextLine(); for(int i=0; i<n; i++) { String str = sc.nextLine(); strs[i] = str; } Tes2(strs); System.out.println("End"); sc.close(); } public static void Tes2(String[] strs) { for(int i=0; i<strs.length; i++) { String str = strs[i]; System.out.println(str); } } }
日期类Date（时间戳）
//抛出异常：throws ParseException
//Date类型转换成字符串 SimpleDateFormat format = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); Date date = new Date(); String nowTime = format.format(date); System.out.println("当前的时间：："+nowTime);//2022-11-13 10:19:06 SimpleDateFormat format2 = new SimpleDateFormat("yyyy年MM月dd日"); String nowTime2 = format2.format(date); System.out.println("当前的时间：："+nowTime2);//2022年11月13日 SimpleDateFormat format3 = new SimpleDateFormat("yyyy年MM月dd日HH时mm分ss秒"); String nowTime3 = format3.format(date); System.out.println("当前的时间：："+nowTime3);//2022年11月13日10时19分06秒 --------------------------------------------- 控制台： 当前的时间：：2022-11-13 10:19:06 当前的时间：：2022年11月13日 当前的时间：：2022年11月13日10时19分06秒
时间戳：
1、Date对象转换为时间戳 Date date = new Date(); long times = date.getTime(); System.out.println(times); 效果如下： 1508824283292 2、时间戳转换为Date日期对象 long times = System.currentTimeMillis(); Date date = new Date(times); System.out.println(date); 效果如下： Tue Oct 24 13:49:28 CST 2017 3、时间戳转换为指定日期格式 SimpleDateFormat format = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); long times = System.currentTimeMillis(); String str = format.format(times); System.out.println(str); 效果如下： 2017-10-24 13:50:46 4、时间字符串<年月日时分秒毫秒 >转为 时间戳 20180914150324转为1536908604990 代码： //大写HH：24小时制，小写hh：12小时制 //毫秒：SSS //指定转化前的格式 SimpleDateFormat sdf = new SimpleDateFormat("yyyyMMddHHmmssSSS"); //转化后为Date日期格式 Date date = sdf.parse(sb.toString()); //Date转为时间戳long long shootTime = date.getTime(); System.out.println(shootTime);
日历类Calendar
小贴士：
西方星期的开始为周日（1）周一（2），中国开始为周一，因此可以-1使用；注：需单独对0进行处理,0代表周日
int weekDay = calendar.get(Calendar.DAY_OF_WEEK) - 1; if (weekDay == 0) { System.out.println("7"); } else { System.out.println(weekDay); }
在Calendar类中，月份的表示是以0-11代表1-12月（可以+1使用）。
日期是有大小关系的，时间靠后，时间越大。
常用方法
根据Calendar类的API文档，常用方法有：
public int get(int field)：返回给定日历字段的值。
public void set(int field, int value)：将给定的日历字段设置为给定值。
public abstract void add(int field, int amount)：根据日历的规则，为给定的日历字段添加或减去指定的时间量。
public Date getTime()：返回一个表示此Calendar时间值（从历元到现在的毫秒偏移量）的Date对象。
// 创建Calendar对象 Calendar calendar = Calendar.getInstance(); // 获取年份 int year = calendar.get(Calendar.YEAR); // 获取月份（月份是从0开始编号的） int month = calendar.get(Calendar.MONTH) + 1; // 获取具体日期（月中的第几天） int dayOfMonth = calendar.get(Calendar.DAY_OF_MONTH); //获取星期（周日是第一天,周六是最后一天） int week = calendar.get(Calendar.DAY_OF_WEEK); System.out.println(calendar.get(Calendar.YEAR) + "年" + (calendar.get(Calendar.MONTH) + 1) + "月" + calendar.get(Calendar.DAY_OF_MONTH) + "日" +"week"+ calendar.get(Calendar.DAY_OF_WEEK) ); //设置——set(){calendar是可变性的} calendar.set(Calendar.DAY_OF_WEEK,2);//减1week System.out.println(calendar.get(Calendar.YEAR) + "年" + (calendar.get(Calendar.MONTH) + 1) + "月" + calendar.get(Calendar.DAY_OF_MONTH) + "日" +"week"+ calendar.get(Calendar.DAY_OF_WEEK) ); //添加——add() calendar.add(Calendar.DAY_OF_WEEK, 2);//加2week calendar.add(Calendar.YEAR, -3); // 减3年 System.out.println(calendar.get(Calendar.YEAR) + "年" + (calendar.get(Calendar.MONTH) + 1) + "月" + calendar.get(Calendar.DAY_OF_MONTH) + "日" +"week"+ calendar.get(Calendar.DAY_OF_WEEK) ); 控制台----------------------------- 2022年11月13日week1 2022年11月14日week2 2019年11月16日week7 ----------------------------- getTime方法：返回对应的Date对象 Calendar中的getTime方法并不是获取毫秒时刻，而是拿到对应的Date对象。 import java.util.Calendar; import java.util.Date; public class Demo { public static void main(String[] args) { Calendar cal = Calendar.getInstance(); Date date = cal.getTime(); System.out.println(date); } } 控制台----------------------------- Sun Sep 20 08:44:18 CST 2020
String
str.trim(); //去掉首尾空格
str.replace(" “,”“); //去除所有空格，包括首尾、中间
str.replaceAll(” “, “”); //去掉所有空格，包括首尾、中间
str.replaceAll(” +“,”“); //去掉所有空格，包括首尾、中间 str.replaceAll(”\s*“, “”); //可以替换大部分空白字符， 不限于空格 ；
replace和replaceAll是JAVA中常用的替换字符的方法,它们的区别是:
（1） replace的参数是char和CharSequence,即可以支持字符的替换,也支持字符串的替换(CharSequence即字符串序列的意>思,说白了也就是字符串);
（2） replaceAll的参数是regex,即基于规则表达式的替换,比如,可以通过replaceAll(”\d", “*”)把一个字符串所有的数字字符都换>成星号;
相同点：都是全部替换,即把源字符串中的某一字符或字符串全部换成指定的字符或字符串,如果只想替换第一次出现的,可以使用 >。
replaceFirst(),这个方法也是基于规则表达式的替换,但与replaceAll()不同的时,只替换第一次出现的字符串。
length()返回字符串的长度 charAt(index)返回索引值的字符
concat(s1)字符串的拼接 trim()去掉字符串头和尾的空格
toUpperCase() toLowerCase()字符串的大小写转换
//str.startsWith(“s”)函数是用于判断str是否以“s”开头，返回一个布尔值
//str.substring(n1,n2) --> 包括头但不包括尾
例：discount = discount.substring(0, discount.length() - 1);
“88折”.substring(0, 3-1) returns “88” 截取，含头不含尾
Str.toCharArray(); 将字符串转换为字符数组；
int i = 123; String str =i+“”; char [] s = str.toCharArray(); 将数字拆分成字符数组
Math
Math.sqrt()//计算平方根 Math.cbrt()//计算立方根
Math.pow(底数，几次方) --> int c=(int)Math.pow(a,b)中添加了一个(int),这是强制类型转换,因为Math.pow(a,b) 的计算结果返回是double类型，double类型转换为int类型就需要用到。
Math.random()是令系统随机选取大于等于 0.0 且小于 1.0 的伪随机 double 值
// 由控制台接收两个整数作为范围，产生一个整数。Math.random()随机产生一个0-1之间的浮点数。
int r = a + (int)(Math.random()*(b-a+1));
//圆面积：double s = Math.PI * r * r;
next()
next()方法在读取内容时，会过滤掉有效字符前面的无效字符，对输入有效字符之前遇到的空格键、Tab键或Enter键等结束符，next()方法会自动将其过滤掉；只有在读取到有效字符之后，next()方法才将其后的空格键、Tab键或Enter键等视为结束符；所以next()方法不能得到带空格的字符串。
nextLine()方法字面上有扫描一整行的意思，它的结束符只能是Enter键，即nextLine()方法返回的是Enter键之前没有被读取的所有字符，它是可以得到带空格的字符串的。
对任何数x，都有xx=0,x0=x。
打印不换行，System.out.print();
位运算
如果要判断一个数的二进制中某一位（假设是第五位）是1还是0，将1左移四位，与该数进行&运算后，再右移四位，判断最终结果。
代码实现： (((num>>4)&1)==0?“第五位是0”:“第五位是1”);
用二进制的思想交换两个数：x=x^y; y=x^y ; x=x^y;
1.什么是位运算
位运算又称为位操作，指的是直接对二进制位进行的一系列操作。
2.位运算有哪些
AND( & ) 按位与 1 & 1 = 1 1 & 0 = 0 0 & 0 = 0 1101 & 1100 = 1100 OR( | ) 按位或 1 | 1 = 1 1 | 0 = 1 0 | 0 = 0 1001 | 1010 = 1011 XOR( ^ ) 按位异或 1 ^ 1 = 0 0 ^ 0 = 0 1 ^ 0 = 1 0 ^ 1 = 1 1101 ^ 1100 = 0001 NOT( ~ ) 取反 ~1 = 0 ~0 = 1 ~0111 = 1000 另：& | ^ ~ 是c或类c的编程语言中所用的位操作符。 除了~是单目运算符 其余的三个都是双目运算符。 移位运算 左移运算符: << 在二进制表示下把数字同时向左移， 低位以0填充， 高位越界后舍弃。 右移运算符: >> 右移运算又分为算术右移和逻辑右移。 算术右移： 在二进制补码表示下，把数字同时向右移位，高位以符号位填充，低位越界后舍弃。 对于 n >> 1 在C/C++中相当于 n/2 下取整。 逻辑右移： 在二进制补码表示下把数字同时向右移动，高位以0填充，低位越界后舍弃。 C++并没有规定右移的方式，所以编译器不同，可能实现的方式也不一样。 不过说了这么多，总结下来其实就是: 00001 << 2 = 00100 00100 >> 2 = 00001
3.常用的位运算操作
1. (n>>k) &1 取出整数n在二进制表示下的第k位 2. n & ((1 << k) - 1) 取出整数n在二进制表示下的第0~k-1位(后k位) 3. n ^ (1 << k) 把整数n在二进制表示下的第k位取反 4. n | (1 << k) 把整数n在二进制表示下的第k位赋值为1 5. n & (~(1 << k)) 把整数n在二进制表示下的第k位赋值为0 6. n ^ (1 << k) = n - (1<<k) 7. 除以2 a / 2 = a >> 1 (a + b) / 2 == a + b >> 1 ( + - 运算的优先级高于 <<, >> ) 8. 判断奇偶 一个数的二进制数的最低位如果是1 则该数一定是奇数 否则一定是偶数 所以 用 a & 1 检测最低为是否位1 if(a & 1) cout<<"奇数"; else cout<<"偶数" 9. 快速幂 10. 状态压缩 以一个二进制数表示一个状态集合。 如 n = 1100 S = {2, 3} S表示状态所有为1的集合。 11. 成对变换 当n 为偶数时 n ^ 1 = n + 1 当n为奇数时 n ^ 1 = n - 1 所以 (0,1) (2, 3) (4, 5)… 关于 ^1 运算 构成“成对变换” 这一性质常用于图论邻接表中边集的存储。在具有无向边（双向边）的图中把一对正反方向的边分别存储在邻接表数组中的第n和第n+1位置（n为偶数），就可以通过^1 的运算获得与当前边（x, y） 反向的边（y, x）的存储位置。 摘自<<算法竞赛进阶指南>> 12. lowbit运算 lowbit(n) 定义为非负整数n在二进制表示下"最低为1及其后边所有0"构成的数值. 例如 n = 10 的二进制表示为(1010)2, 则lowbit(n) = 2 = (10)2 . lowbit(n) = n & (~n + 1) = n&(-n) **摘自<<算法竞赛进阶指南>>**
循环
- 多重循环要学会，
外层循环控制行，内层循环控制列。 - 不确定次数、多个控制变量、控制变量的初始化必须放在循环外面的时候---->用while更合适
类型
byte、char、short型参与运算时自动提升为int型。
如果一个操作数为long、float、double型，则整个表达式提升为long、float、double型
int result = 27/3; double result = 27/3.0;
long timeMillis = System.currentTimeMillis();
当接收到的数比如：52345678912（五百亿+），这时需要手动转为long类型，即在末尾加上L，表示是long类型
System.out.println((timeMillis/3600000)%24+8);//返回当前小时数
// 由控制台接收两个整数作为范围，产生一个整数。Math.random()随机产生一个0-1之间的浮点数。
int r = a + (int)(Math.random()*(b-a+1));
//圆面积：double s = Math.PI * r * r;
