github点个star呗github会持续更新这里想到就更新ddbjiang/codeforces-algorithms-templatesmath BigIntegar arrarys数组方法 collection集合方法 集合通用方法 arraylist set map stack queue dueqe string stringbuilder import java.util.*;java万能头 import static java.lang.Math.*;静态导入math类 public static void main(String[] args)主类 输入 scanner类 while (sc.hasNextInt())处理不定行输入 Scanner innew Scanner(System.in); nextByte() nextShort() nextInt() nextLong() nextFloat() nextDouble() next()空格分割 nextLine()当前行 hasNext()检查输入 in.close 输出 System.out.println() printf%d整数 %.2f浮点数 %s字符串 .1lf四舍五入一位小数 %e科学记数法 %c字符 %b布尔 宽度%8d左边加空格负号就是右边加空格 printf(%8.2f,x)8个字符精度为2个字符 快读st br isr 快写pw osw import java.io.*; import java.util.*; public class Main { static PrintWriter pw new PrintWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws Exception { BufferedReader bf new BufferedReader(new InputStreamReader(System.in)); //int nInteger.parseInt(bf.readLine().trim()); //String sbf.readLine().trim(); Read in new Read(); pw.flush(); } public static class Read { StreamTokenizer st new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); public int nextInt() throws IOException { st.nextToken(); return (int) st.nval; } public long nextLong() throws IOException { st.nextToken(); return (long) st.nval; } public double nextDouble() throws IOException { st.nextToken(); return st.nval; } public String nextword() throws Exception{ st.nextToken(); return st.sval; } } } 基础算法备忘java特有 最大int 2147483647 最小int -2147483648 除法向上取整xy-1/y dfs收集答案 ListListInteger ans new ArrayList(); LinkedListInteger path new LinkedList(); set存字符串去重 标签搭配continue和break跳出多层循环java特有 Integer.parseInt可以进制转化 Map.EntryK, V当pair用 大整数类有自带的逆元 String.split(\\);转义 Arrays.asList(result)数组转list return Arrays.copyOf(ans, k); HashMapString, ListInteger map new HashMap();多重映射相当于c unordered_mapK, vectorV map.putIfAbsent(key, new ArrayList());map.get(key).add(value); queue.add(new int[] {j,dist[j]}); 二进制和位运算 按位与运算 |按位或运算 ^按位异或运算 ~取反运算 左移 右移 无符号右移空位补0 ^32大小写转化 0b开头表示二进制 0开头表示八进制 0x开头表示十六进制 int转二进制Integer.toBinaryString(int i)八进制Integer.toOctalString(int i)十六进使用Integer.toHexString(int i) Integer.bitCount(s)集合大小 32-Integer.numberOfLeadingZeros(s)二进制长度 31-Integer.numberOfLeadingZeros(s)集合最大元素 Integer.numberOfTrailingZeros(s)集合最小元素 Integer.lowestOneBit最低位1对应的数 Integer.highestOneBit最高位1对应的数(考虑0) 字符串哈希掩码添加mask|1(c-a); 删除mask~(1(c-a)) 删除mask^1(c-a); 位运算去掉最后1 s(s−1) 属于(s i) 11 不属于(s i) 10 枚举集合 for (int i 0; i (1 l); i) for (int j 0; j l; j) if ((i (1 j)) ! 0) {} javapair类是下标也可以用数组存 java自定义哈希 public class Student { int id; String name; public Student(int id, String name) { this.id id; this.name name; } Override public int hashCode() { return id; } Override public boolean equals(Object obj) { return this.id ((Student)obj).id; } } 排序 sortv或sort(v,(a,b)-a-b)升序 sortCollections.reverseOrder()或sort(v,(a,b)-b-a)降序 Arrays.sort(v,(a,b)-{ if(a[0]b[0])return a[1]-b[1]; return b[0]-a[0]; })二维比较Lambda表达式写法 Arrays.sort(points, (a, b) - Integer.compare(a[0], b[0]));比较器写法 防int溢出 给map排序 ListMap.EntryString, Integerlistnew ArrayList(map.entrySet()); Collections.sort(list,(a,b)-{ int tInteger.compare(a.getValue(), b.getValue()); if(t0) { return a.getKey().compareTo(b.getKey()); } return t; }); list.forEach(a-ans.add(a.getKey())); math类 abs max min pow sqrt random sin cos tan log random ceil向上 floor向下 round四舍五入 rinta返回最接近a的整数 BigInteger类BigDecimal高精度小数类 Biginteger(string)构造 add subtract multiply divide modremainder可为负数模 abs绝对值 negate返回负数 gcd最大公约数 lcm最小公倍数 pow幂 compareTo比较 shiftLeft左移n位 shiftRight右移n位 and与 or或 xor异或 not取反 isProbablePrime20以上置信度判素数 toString(toString(int radix)指定radix进制 modInverse(BigInteger m)模逆元当 m 是质数时有效 modPow(BigInteger exponent, BigInteger m)快速幂 数组方法arrarys sort(array)升序 fill(array, value)填充元素 equals(array1, array2)如长度相同包含相同的顺序和元素返回true。 binarySearch(array, key)在已排序的数组中查找值。找到该值返回其索引否则返回-i-1下标表示应该插入的位置 toString(array)打印数组 deepToString(Object[] a)打印多维数组 ans.add(Arrays.asList(i, j));构建链表添加 集合方法collections sort(List list)升序 fill(List list, T obj)填充元素 binarySearch(List list, Object key)二分查找 reverse(List list)反转列表中元素的顺序 max min 集合通用方法 IteratorStringitList.iterator()迭代器 whileit.hasNext()String nameit.next()迭代器遍历 add() 添加元素 remove() 移除第一个符合元素 clear() 清空集合 size() 返回集合元素数量 contains() 判断包含元素 isEmpty() 集合判空 equals(Object o) 判断集合相等 addAll(集合) 添加另一个集合的所有元素 containsAll(集合) 判断集合是否包含指定集合中的所有元素 removeAll(集合) 移除与指定集合共有的元素取差集 retainAll(集合) 保留与指定集合共有的元素取交集 Arrays.setAll(lists, i-new ArrayList()); vec.toArray(new int[vec.size()][]);返回特定类型数组 clone克隆 List列表ArrayList或LinkedList add(元素)添加到末尾 add(int index, 元素)在指定位置插入元素。 get(int index)返回索引的元素 set(int index, 元素)用元素替换指定位置的元素。 remove(int index)移除并返回指定位置的元素 remove(元素)移除列表中首次出现的指定元素 removeLast移除最后一个元素 indexOf(Object o)返回此列表中首次出现指定元素的位置不包含该元素则返回 -1 lastIndexOf(Object o)返回此列表中最后一次出现指定元素的位置不包含该元素则返回 -1 ListInteger[]listsnew List[n]; for(int i0;in;i) { lists[i]new ArrayList(); }声明list数组 Set集合(HashSet)还有LinkedHashSet TreeSet add(E e)如果此集合中尚未包含指定元素则将其添加 remove(Object o)从该集合中移除指定元素 contains(Object o)判断集合中是否包含指定元素 TreeSet ceiling(E e) 返回大于等于 e 的最小元素 floor(E e) 返回小于等于 e 的最大元素 higher(E e) 返回严格大于 e 的最小元素 lower(E e) 返回严格小于 e 的最大元素 subSet(E fromElement, E toElement) 返回从 fromElement包含到 toElement不包含之间的子集 headSet(E toElement) 返回小于 toElement 的所有元素的子集 tailSet(E fromElement) 返回大于等于 fromElement 的所有元素的子集 可以当队列用 Map映射(HashMap)还有LinkedHashMap TreeMap MapString, String m new HashMap(){{ put(Jan, 01);}}可以初始化两个括号里填put put(K key, V value)将指定值与此映射中的指定键关联。 replace(K key, V value)存在key就更新不存在忽略 get(Object key)返回指定键映射到的值如果此映射不包含该键的映射关系则返回 null。 getOrDefault(key, defaultValue)带默认值 remove(Object key)从此映射中移除指定键的映射关系 keySet()返回映射中所有键的集合视图。 values()返回映射中所有值的集合视图。 entrySet()返回映射中所有键值对的集合set视图。 mp.forEach((x,y)-{});遍历 for(Map.EntryInteger,Integeri:mp.entrySet())遍历 containKey判断是否包含健 containValue判断是否包含值 map.merge(t, 1, Integer::sum);等价于map.put(t, map.getOrDefault(t, 0)1); map.computeIfAbsent(t, k-new ArrayListInteger());如果不存在键时创建值可以用ifelse替代 TreeMap ceilingKey(K key) 返回大于等于 key 的最小键 floorKey(K key) 返回小于等于 key 的最大键 higherKey(K key) - 返回严格大于 key 的最小键 lowerKey(K key) 返回严格小于 key 的最大键 subMap(K fromKey, K toKey) - 返回从 fromKey包含到 toKey不包含之间的键值对映射 headMap(K toKey) - 返回小于 toKey 的所有键值对映射 tailMap(K fromKey) - 返回大于等于 fromKey 的所有键值对映射 firstKey() lastKey() Stack栈Deque或Stack push(元素)元素压入栈顶 pop()移除并返回栈顶元素 peek()返回栈顶元素 search(元素)返回对象在栈中的位置以1为基数。如果找不则返回 -1。 Queue队列(LinkedList或ArrayDeque或PriorityQueue) 优先队列创建PriorityQueueInteger q new PriorityQueue((o1, o2) - o2 - o1); offer(元素)将元素插入队列的尾部 poll()获取并移除队列的头部元素 peek()获取队列的头部元素 Deque双端队列LinkedList或ArrayDeque addFirst(元素)开头插入指定元素 addLast(元素)末尾插入指定元素 相当于 add(E e) getFirst() 返回此第一个元素 getLast() 返回最后一个元素。 removeFirst()移除并返回第一个元素 removeLast()移除并返回最后一个元素 peekFirst()返回第一个元素 peekLast()返回最后一个元素 pollFirst() pollLast()不抛异常 String类 创建字符串String s1 连接字符串使用 或者 concat() 方法 charAt(int index)获取字符 substring(int beginIndex) / substring(int beginIndex, int endIndex)子串 indexOf(String str) / lastIndexOf(String str)查找子串首次或最后一次出现的位置 startsWith(String prefix) / endsWith(String suffix)判断字符串是否以特定前缀开始/结束 contains(CharSequence s)判断是否包含某子串 replace(CharSequence target, CharSequence replacement)修改 toUpperCase() / toLowerCase()转为大写/小写 trim()删除两端空格 split(String regex)分割字符串 join(CharSequence delimiter, CharSequence... elements)使用指定的分隔符连接多个字符串元素 compareTo(String anotherString) 字典顺序比较equalsIgnoreCase(String anotherString)忽略大小写的比较 toCharArray()字符串转字符数组 new String(charArray, startIndex, length)字符数组转字符串 Integer.parseInt(String s)字符串转int Integer.valueOf(String s)字符串转int String.valueOf(int i)int转字符串 Integer.toString()int转字符串 Stringbuilder类和StringBuffer类 Stringbuilder sb new Stringbuilder(); new Stringbuilder(int capacity) new Stringbuilder(String str) append(String str)添加字符 insert(int offset, String str)插入字符串到指定位置 delete(int start, int end)删除指定范围内的子串 deleteCharAt(int index)删除某个位置的字符 replace(int start, int end, String str)替换内容 reverse()反转字符串 toString()获取可读字符串 char charAt(int index)获取字符 setCharAt(int index, char ch)设置字符 String substring(int start) 或 String substring(int start, int end) 截取子串 insert位置字符指定位置插入 sb.setLength(0);清空 StringJonier new StringJonier(间隔符号); new StringJonier(间隔符号,开始符号,结束符号); add() toString() 二维差分不需要显式初始化 void insert(int x1, int y1 , int x2 , int y2 , int c){ b[x1][y1] c; b[x2 1][y1] - c; b[x1][y2 1] - c; b[x2 1][y2 1] c; }差分数组插入 for(int i 1 ; i n ; i ){ for(int j 1 ; j m ; j ){ b[i][j] b[i-1][j] b[i][j - 1] - b[i - 1][j - 1]; } }前缀和复原差分数组 ST表区间最大小值 gcd lcm || 布尔 存在某值 int maxlog(int) ((Math.log(n)/Math.log(2))1); stnew int[n1][maxlog]; for(int i1;in;i) st[i][0]in.nextInt(); for(int j1;jmaxlog;j) { for(int i1;in-(1j)1;i) { st[i][j]Math.max(st[i][j-1], st[i(1(j-1))][j-1]); } } while(m--0) { int lin.nextInt(); int rin.nextInt(); pw.println(query(l, r)); } pw.flush(); } public static int query(int l,int r) { int j(int) (Math.log(r-l1)/Math.log(2)); return Math.max(st[l][j], st[r-(1j)1][j]); } 树状数组前缀和 区间和 单点更新 区间更新 class Treea { int n; int[] tree; Treea(int n) { this.n n; tree new int[n 1]; } void update(int i, int t) { while (i n) { tree[i] t; i i -i; } } int sum(int i) { int sum 0; while (i 0) { sum tree[i]; i - i -i; } return sum; } } 素数筛埃氏筛法 boolean a[]new boolean[n1]; for(int i2;in;i) a[i]true; for(int i2;i*in;i) { if(a[i]) { for(int ji*i;jn;ji) { a[j]false;}}} 素数筛欧拉筛法 线性筛 boolean a[]new boolean[n1]; ListIntegerpsnew ArrayList(); Arrays.fill(a, true);a[0]a[1]false; for(int i2;in;i) { if(a[i]) ps.add(i); for(int j:ps) { if(j*in)break; a[j*i]false; if(j%i0)break;}} 组合数 a[0]1; for(int i1;ik;i) for(int ji;j1;j--) a[j](a[j-1]a[j])%mod; 错排1, 0, 1, 2, 9, 44, 265 cp[0]1;cp[1]0; for(int i2;in;i) cp[i](i-1)*(cp[i-1]cp[i-2]); 快速幂 public static long quickPow(long a, long n) { long ans 1; while (n 0) { if ((n 1) 1) { // 如果该二进制位存在 ans ans * a % MOD; } a a * a % MOD; n 1; // n除以2,判断下一个二进制位 } return ans; } 逆元表 inv[1] 1; for (int i 2; i MAXN; i) { inv[i] mod - mod / i * inv[mod % i] % mod; } 并查集 int[] fa new int[n1]; int[] nums new int[n1]; static int find(int x) { if(fa[x] x) return x; return fa[x] find(fa[x]);} static void union(int a, int b) { int rootA find(a);int rootB find(b); if(rootA rootB) return; if(nums[rootA] nums[rootB]) fa[rootB] rootA; else if(nums[rootA] nums[rootB]) fa[rootA] rootB; else { fa[rootB] rootA; nums[rootA];}} 区间dp int[][] dp new int[n 1][n 1]; int[] arr new int[n 1]; for (int len 2; len n; len) { for (int i 1; i n - len 1; i) { int j i len - 1; for (int k i; k j; k) { dp[i][j] Math.min(dp[i][j], dp[i][k] dp[k 1][j] cost(i, k, j));}}} 01背包可以转二进制拆分优化 for(int i1;in;i) { for(int jm;jw[i];j--){ dp[j]Math.max(dp[j], dp[j-w[i]]v[i]);}} 完全背包 for(int i1;in;i) { for (int j w[i]; j m; j) { dp[j] Math.max(dp[j], dp[j - w[i]] v[i]);}} 多重背包 for(int i1;in;i) { for(int jm;jw[i];j--) { for(int k1;ks[i]k*w[i]j;k) { dp[j]Math.max(dp[j], dp[j-k*w[i]]k*v[i]);}}} 二维费用背包 for(int i1;in;i) { for(int jv;jv1[i];j--) { for(int km;km1[i];k--) { dp[j][k]Math.max(dp[j][k], dp[j-v1[i]][k-m1[i]]w1[i]);}}} 分组背包 for (int i 1; i n; i) { for (int j m; j 1; j--) { for (int k 1; k s[i]; k) { if (j w[i][k]) { dp[j] Math.max(dp[j], dp[j - w[i][k]] v[i][k]);}}}} 边集建立邻接表 ListInteger[]listsnew List[n]; for(int i0;in;i) { lists[i]new ArrayList(); } for(int[]i:edges) { lists[i[0]].add(i[1]); lists[i[1]].add(i[0]); } int v[]new int[n]; 最短路d算法稠密图 class Solution { public int networkDelayTime(int[][] times, int n, int k) { int max(int) (1e97); int[][]gnew int[n][n]; int[]distnew int[n]; boolean[]fnew boolean[n]; for(int[]i:g)Arrays.fill(i, max); Arrays.fill(dist, max); for(int[]i:times) { g[i[0]-1][i[1]-1]i[2]; } dist[k-1]0; for(int i0;in;i) { int x-1; for(int j0;jn;j) { if(!f[j](x0||dist[x]dist[j])) { xj; } } f[x]true; for(int j0;jn;j) { dist[j]Math.min(dist[j], dist[x]g[x][j]); } } int maxd0; for(int i:dist)maxdMath.max(maxd, i); return maxdmax?-1:maxd; } } 稀疏图堆优化 class Solution { public int networkDelayTime(int[][] times, int n, int k) { int max(int) (1e97); Listint[]g[]new List[n]; Arrays.setAll(g, i-new ArrayList()); int[]distnew int[n]; Arrays.fill(dist, max); for(int[]i:times) { g[i[0]-1].add(new int[] {i[1]-1,i[2]}); } dist[k-1]0; PriorityQueueint[]queuenew PriorityQueue((a,b)-a[1]-b[1]); queue.add(new int[] {k-1,0}); while(!queue.isEmpty()) { int[]nowqueue.poll(); int inow[0]; int dnow[1]; if(ddist[i])continue; for(int[]next:g[i]) { int jnext[0],ddnext[1]; if(dist[j]dist[i]dd) { dist[j]dist[i]dd; queue.add(new int[] {j,dist[j]}); } } } int maxd0; for(int i:dist)maxdMath.max(maxd, i); return maxdmax?-1:maxd; } } 最短路Floyd算法 int[][] d new int[n][n]; for (int i 0; i n; i) Arrays.fill(d[i], (int)1e9); for (int i 0; i n; i) d[i][i] 0; for (int[] edge : edges) { d[edge[0]][edge[1]] edge[2]; d[edge[1]][edge[0]] edge[2]; } for (int k 0; k n; k) { for (int i 0; i n; i) { for (int j 0; j n; j) { d[i][j] Math.min(d[i][j], d[i][k] d[k][j]); } } } 最小生成树k套用并查集稀疏图 Listint[]listsnew ArrayList(); for(int i0;in;i) { for(int ji1;jn;j) { int tMath.abs(points[i][0]-points[j][0])Math.abs(points[i][1]-points[j][1]); lists.add(new int[] {t,i,j}); } } Collections.sort(lists,(a,b)-a[0]-b[0]); int ans0,cnt1; for(int[]i:lists) { int leni[0],xi[1],yi[2]; int xxfind(x);int yyfind(y); if(xx!yy) { f[xx]yy; anslen; cnt; if(cntn)break; } } 最小生成树prim算法 稀疏图堆优化版 Listint[][]gnew List[n]; Arrays.setAll(g, i-new ArrayList()); for(int i0;in;i) { for(int j0;jn;j) { int tMath.abs(points[i][0]-points[j][0])Math.abs(points[i][1]-points[j][1]); g[i].add(new int[] {j,t}); g[j].add(new int[] {i,t}); } } PriorityQueueint[]pqnew PriorityQueue((a,b)-a[1]-b[1]); boolean[]vnew boolean[n]; pq.add(new int[] {0,0}); int ans0;int cnt0; while(!pq.isEmpty()) { int[]nowpq.poll(); int inow[0]; int dnow[1]; if(v[i])continue; v[i]true; ansd; cnt; if(cntn)break; for(int[]next:g[i]) { int jnext[0]; int ddnext[1]; if(!v[j]) { pq.add(new int[] {j,dd}); } } } 字典树 class Trie { private class Node{ Node[] sonnew Node[26]; boolean end; } private final Node rootnew Node(); public void insert(String word) { Node curroot; for(char c:word.toCharArray()) { c-a; if(cur.son[c]null) { cur.son[c]new Node(); } curcur.son[c]; } cur.endtrue; } public boolean search(String word) { return find(word)2; } public boolean startsWith(String prefix) { return find(prefix)!0; } private int find(String word) { Node curroot; for(char c:word.toCharArray()) { c-a; if(cur.son[c]null) { return 0; } curcur.son[c]; } return cur.end?2:1; } } 线段树 public class SegmentTree { int[] tree; int n; public SegmentTree(int[] arr) { n arr.length; tree new int[4 * n]; build(arr, 1, 0, n - 1); } void build(int[] arr, int node, int start, int end) { if (start end) { tree[node] arr[start]; } else { int mid (start end) / 2; build(arr, node*2, start, mid); build(arr, node*21, mid1, end); tree[node] Math.min(tree[node*2], tree[node*21]); // 合并 } } int query(int node, int start, int end, int l, int r) { if (r start || end l) return Integer.MAX_VALUE; if (l start end r) return tree[node]; int mid (start end) / 2; int leftQ query(node*2, start, mid, l, r); int rightQ query(node*21, mid1, end, l, r); return Math.min(leftQ, rightQ); } void update(int node, int start, int end, int idx, int val) { if (start end) { tree[node] val; } else { int mid (start end) / 2; if (idx mid) update(node*2, start, mid, idx, val); else update(node*21, mid1, end, idx, val); tree[node] Math.min(tree[node*2], tree[node*21]); } } } LocalDate now()获取当前日期。 of(int year, Month month, int dayOfMonth)创建指定的日期对象。 of(int year, int month, int dayOfMonth)创建指定的日期对象。 getYear(), getMonthValue(), getDayOfMonth()分别获取年、月、日。 plusDays(long daysToAdd), minusDays(long daysToSubtract)增加或减少天数。 equal判断日期相等 isAfter(LocalDate other), isBefore(LocalDate other)比较日期先后。 LocalTime now()获取当前时间。 of(int hour, int minute) 或 of(int hour, int minute, int second)创建指定的时间对象。 getHour(), getMinute(), getSecond()分别获取小时、分钟、秒。 plusHours(long hoursToAdd), minusHours(long hoursToSubtract)增加或减少小时数。 withHour(int hour) 设置特定字段的值。 LocalDateTime now()获取当前的日期和时间。 of(LocalDate date, LocalTime time) 或 of(int year, Month month, int dayOfMonth, int hour, int minute)创建指定的日期时间对象。 toLocalDate(), toLocalTime()分别提取日期和时间部分 plusDays(long daysToAdd), minusMonths(long monthsToSubtract)增加或减少不同单位的时间。 for(LocalDate id1;!i.isAfter(d2);ii.plusDays(1)) { int yi.getYear(); int mi.getMonthValue(); int di.getDayOfMonth(); pw.println(y m d); ans; }遍历日期
