代码片段1
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main {
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter cout = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
public static void main(String[] args)throws Exception{
}
public static int cin() throws IOException {
in.nextToken();
return (int) in.nval;
}
}
代码片段2
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;
public class Main {
static int N = 100010;
static Scanner cin = new Scanner(System.in);
static PrintWriter cout = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
public static void main(String[] args) throws Exception {
cout.close();
}
}
排序
自定义结构体排序
在类里面实现排序方法即可，注意引用Comparable接口
static public class Node implements Comparable<Node>{
int num = 0;
long k = 0,b = 0;
public Node(){}
public Node(int _num,long _k,long _b){
this.num = _num;
this.k = _k;
this.b = _b;
}
public int compareTo(Node o) {
long cost1 = (this.num + 1) * Math.max(0, k * (num + 1) + b) - num * Math.max(0, k * num + b);
long cost2 = (o.num + 1) * Math.max(0, o.k * (o.num + 1) + o.b) - o.num * Math.max(0, o.k * o.num + o.b);
return cost1 < cost2 ? 1 : -1;
}
}
Arrays.sort
实现Comparator接口实现降序
import java.util.*;
public class Main {
public static void main(String[] args){
//不能使用基本数据类型
Integer[] arr = {5,4,7,9,2,12,54,21,1};
//降序
Arrays.sort(arr, new Comparator<Integer>() {
//重写compare方法，最好加注解，不加也没事
public int compare(Integer a, Integer b) {
//返回值>0交换
return b-a;
}
});
System.out.println(Arrays.toString(arr));
}
}
等价于：
import java.util.*;
public class Main {
public static void main(String[] args){
//不能使用基本数据类型
Integer[] arr = {5,4,7,9,2,12,54,21,1};
//降序
Arrays.sort(arr, (a, b) -> {
//返回值>0交换
return b-a;
});
System.out.println(Arrays.toString(arr));
}
}
还可以：
import java.util.*;
public class Main {
public static void main(String[] args){
Integer[] arr = {5,4,7,9,2,12,54,21,1};
//降序
//重新实现Comparator接口
Arrays.sort(arr, new compa());
System.out.println(Arrays.toString(arr));
}
}
class compa implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
// A.compareTo(B) A>B 返回1，A=B 返回0，A<B 返回-1
// compareTo()返回值>0就交换
// 如果02 > o1 就交换 =>降序
return o2.compareTo(o1);
}
}
Collections.sort
Collections.sort用与于集合的排序，比如linked，下面给出排序的形式
Collections.sort(S, new Comparator<Student>(){
public int compare(Student stu1, Student stu2) {
return stu2.getg()-stu1.getg();
}
浮点数保留2位小数
一、String类的方式
double testDounle_01 = 123.456;
System.out.println(String.format("%.2f", testDounle_01));
二、BigDecimal类进行数据处理
double testDounle_01 = 123.456;
float testFloat_01 = 456.125f;
/**
* BigDecimal类进行数据处理
* */
BigDecimal bigDecimal = new BigDecimal(testDounle_01);
double ans_2 = bigDecimal.setScale(2, BigDecimal.ROUND_HALF_UP).doubleValue();
System.out.println(ans_2);
1.数学
任意进制转换
// 如果题目要进行转化的进制在2~36之间的话直接调用库函数就行了。
String s = in.readLine();
int a = Integer.parseInt(s, 16); // 将16进制的字符串转化十进制数
//BigInteger a = new BigInteger(s, 16);// 高精度数
out.write(Integer.toString(a, 8)); // 转化为8进制输出
快速幂
static long qmi(long a,long b,long mod){
long ans = 1 % mod;
while(b != 0)
{
if((b & 1) != 0)ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
gcd
static long gcd(long a,long b)
{
return b == 0 ? a : gcd(b,a%b);
}
线性筛
static boolean[] is_pri = new boolean[100000010];
static int[] pri = new int[6000010];
static int cnt;
static void init(int n) {
Arrays.fill(is_pri, true);
is_pri[1] = false;
cnt = 0;
for (int i = 2; i <= n; i++) {
if (cnt >= 6000000) {
break;
}
if (is_pri[i]) {
pri[++cnt] = i;
}
for (int j = 1; j <= cnt && (long)i * pri[j] <= n; j++) {
is_pri[i * pri[j]] = false;
if (i % pri[j] == 0) break;
}
}
}
组合数(\(O(N^2\))
static int n;
static int c[][];
public static void init(int n,int mod)
{
for(int i = 0;i <= n; i++)
{
for(int j = 0;j <= i; j++)
{
if(j==0) c[i][j] = 1;
else c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;
}
}
}
2.图论
链式前向星存图
//java版本
static int[] head,next,ends;
static long[]weights,dist;
static int n, m, total = 0//++total：记录从第一条边到最后一条边
public static void add(int start, int end, long weight) {//链式前向星的创建方法
ends[total] = end;
weights[total] = weight;
next[total] = head[start];//以start为起点的上一条边的编号，即：与这个边起点相同的上一条边的编号
head[start] = total++;//更新以start为起点的上一条边的编号
}
dijkatra
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
static int[] head,next,ends;
static long[]weights,dist;
static int n, m, tot = 0;
static int st,ed;
static class Node{
int id;
long dis;
public Node(int _id,long _dis){
this.id = _id;
this.dis = _dis;
}
}
public static void add(int u,int v,long w){
ends[tot] = v;
weights[tot] = w;
next[tot] = head[u];
head[u] = tot++;
}
public static void dijkstra(int start) {
for(int i = 1;i <= n; i++){
dist[i] = Long.MAX_VALUE;
}
Queue<Node> q = new PriorityQueue<>((o1, o2) -> (int) (o1.dis - o2.dis));
q.offer(new Node(start,0));
dist[start] = 0;
while(!q.isEmpty()){
Node u = q.poll();
//遍历以当前节点为起点的所有边
for(int i = head[u.id];i != -1;i = next[i]){
int v = ends[i];
if(dist[v] > dist[u.id] + weights[i]){
dist[v] = dist[u.id] + weights[i];
q.offer(new Node(v,dist[v]));
}
}
}
}
public static void main(String[] args) throws Exception{
Scanner cin = new Scanner(System.in);
BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
n = cin.nextInt(); m = cin.nextInt();
st = cin.nextInt(); ed = cin.nextInt();
head = new int[m*2 + 1];
next = new int[m*2 + 1];
ends = new int[m*2 + 1];
weights = new long[m*2 + 1];
dist = new long[n + 1];
Arrays.fill(head,-1);
for(int i = 1;i <= m; i++){
int u, v; long w;
u = cin.nextInt(); v = cin.nextInt();w = cin.nextLong();
add(u,v,w);
add(v,u,w);
}
dijkstra(st);
// for(int i = 1;i <= n; i++)
// {
// if(dist[i] == Long.MAX_VALUE)
// cout.write("-1 ");
// else cout.write(dist[i] + " ");
// }
cout.write(dist[ed]+"\n");
cout.close();
}
}
Floyd
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;
public class Main {
static int N = 100010;
static Scanner cin = new Scanner(System.in);
static PrintWriter cout = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int[][] d;
static int n, m;
public static void floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
public static void main(String[] args) throws Exception {
n = cin.nextInt();
m = cin.nextInt();
d = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j)
d[i][j] = 0;
else
d[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 1; i <= m; i++) {
int u, v, w;
u = cin.nextInt();
v = cin.nextInt();
w = cin.nextInt();
d[u][v] = Math.min(d[u][v], w);
}
floyd();
cout.close();
}
}
3. 数据结构
java自带数据结构
①List
ArrayList(推荐)
虽然空间开销变大，但是时间复杂度小，类似静态数组空间翻倍
- 初始化
List<Integer>arr = new ArrayList<>();
- 尾部增加数据：
arr.add(Integer);
- 第 \(i\)个位置插入元素，剩下元素右移：
arr.add(pos,Integer);
- 修改第\(i\)个位置的值
arr.set(pos,Integer);
- 链表元素个数
arr.size();
- 获取pos位置的值
arr.get(pos);
- 排序
使用 Collections.sort 对链表排序：
List<Integer>arr = new ArrayList<>();//创建一个空数组(默认长度是10)
for(int i = 1;i <= 10; i++)
{
arr.add(i);
}
Collections.sort(arr, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
for(int i = 0;i < 10; i++)
{
int t = arr.get(i);
cout.print(t+" ");
}
输出：
10 9 8 7 6 5 4 3 2 1
②Queue
ArrayDeque(基于数组实现)
- 插入删除复杂度\(O(1)\)
- 内部是一个循环数组
- 初始化
Deque<Integer>q =new ArrayDeque<>();
- 获取元素个数
q.size();
- 判断队列是否为空
q.isEmpty()
- 插入元素
q.offer(Integer);
- 观察元素
q.peek();
- 取出元素
q.poll();
③PriorityQueue
默认是小顶堆，若要改成大顶堆：
PriorityQueue<Integer>q = new PriorityQueue<>((x,y)->{return y-x;});
方法和上面一样。
④Deque
ArrayDeque(基于数组实现)
- 插入删除复杂度\(O(1)\)
- 内部是一个循环数组
- 初始化
Deque<Integer>q =new ArrayDeque<>();
- 获取元素个数
q.size();
- 判断队列是否为空
q.isEmpty()
- 头部插入元素
q.offerFirst(Integer);
- 尾部插入元素
q.offerLast(Integer);
- 头部取出元素
q.pollFirst(Integer);
- 尾部取出元素
q.pollLast(Integer);
- 头部观察元素
q.peekFirst(Integer);
- 尾部观察元素
q.peekLast(Integer);
④Stack
Javad堆栈Stack类已经过时，Java官方推荐使用Deque替代Stack使用
Deque堆栈操作方法：push()、pop()、peek()。
- 插入元素
st.push(Integer);
- 观察元素
st.peek();
- 取出元素
st.pop();
⑤Set
HashSet
HashSet是基于散列表实现的，它不保证元素的顺序。
- 初始化
Set<Integer>s = new HashSet<>();
TreeSet
TreeSet是基于红黑树实现的，它可以保证元素处于有序状态（默认升序）。
若要改为降序：
Set<Integer>s = new TreeSet<>((x,y)->{return y-x;});
- 返回元素个数
s.size();
- 插入元素
s.add(Integer);
- 判断元素是否存在
s.contains(Integer);
- 遍历
for(Integer x : s){}
⑥Map
HashMap
- 初始化
Map<Integer,Integer>mp = new HashMap<>();
TreeMap
- 初始化
TreeMap<Key, Value> numbers = new TreeMap<>((x,y)->{return y-x;});
- 返回元素个数
mp.size();
- 键值对插入
mp.put(key,val);
对Map集合中的同一键值key重复赋值会覆盖之前的结果。
- 判断键是否存在（不存在的话会是null，不能之间加）
mp.containKey(key);
for(int i = 0;i < s.length(); i++)
{
if(mp.containsKey(ch[i])){
int t = mp.get(ch[i]) + 1;
mp.put(ch[i],t);
if(t > mx)mx = t;
}else{
mp.put(ch[i],1);
}
}
- 获取键值
mp.get(key);
- 替换
replace(key, value)-用key新的替换指定映射的值value
replace(key, old, new) -仅当旧值已与指定键关联时，才用新值替换旧值
遍历方法：
- 按键值遍历
mp.forEach((key,val)->{cout.println(key+" "+val);});
- 按键遍历
for(char c : mp.keySet()){
}
- 按值遍历
for(int c : mp.values()){
}
特别的
- 返回最小的大于或等于指定Key的Key，如果没有，则返回null
mp.ceilingKey();
- 返回最大的小于等于指定Key的Key
mp.floorKey();
自定义数据结构
①并查集
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.lang.reflect.Member;
import java.util.Scanner;
public class Main {
public static class DSU {
int[] fa, siz;
void init(int n) {
fa = new int[n + 10];
siz = new int[n + 10];
for (int i = 0; i <= n; i++) {
fa[i] = i;
siz[i] = 1;
}
}
int find(int x) {
if (fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
boolean same(int x, int y) {
return find(x) == find(y);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
siz[x] += siz[y];
fa[y] = x;
}
int size(int x) {
return siz[find(x)];
}
}
public static void main(String[] args) throws Exception {
Scanner cin = new Scanner(System.in);
BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
int n, m;
n = cin.nextInt();
m = cin.nextInt();
DSU d = new DSU();
d.init(n);
for(int i = 1;i <= m; i++){
int op,x,y;
op = cin.nextInt();
x = cin.nextInt();
y = cin.nextInt();
if(op==1){
d.merge(x,y);
}else{
cout.write(d.same(x,y)?"Y\n":"N\n");
}
}
cout.close();
}
}
②树状数组
import javax.xml.transform.Templates;
import java.awt.event.MouseEvent;
import java.io.*;
import java.util.*;
public class Main {
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter cout = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N = 500010;
static int[] a = new int[N];
static public class BIT{
long []c = new long[N];
int size;
void resize(int s){size = s;}
void init(){
for(int i = 0;i <= N; i++)
c[i] = 0;
}
long quary(int x){//1...x
assert(x <= size);
long s = 0;
for(;x != 0;x -= x & (-x)){
s += c[x];
}
return s;
}
void modify(int x,long s){//a[x] += s
assert(x != 0);
for(;x <= size; x += x & (-x)){
c[x] += s;
}
}
}
public static void main(String[] args) throws Exception {
int n,m;
n = cin(); m = cin();
BIT tr = new BIT();
tr.resize(n+1);
for(int i = 1;i <= n; i++){
a[i] = cin();
tr.modify(i,a[i]);
}
for(int i = 1;i <= m;i++)
{
int op; op = cin();
if(op == 1){
int x,k;
x = cin();k = cin();
tr.modify(x,k);
}else{
int x,y;
x = cin();y = cin();
cout.println(tr.quary(y)-tr.quary(x-1));
}
}
cout.flush();
}
public static int cin() throws IOException {
in.nextToken();
return (int) in.nval;
}
}
③LCA
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N = 1000001;
static int LOGN = 20;
static int n, m, root;
static int[] dep = new int[N];
static int[][] fa = new int[N][LOGN + 5];
static Scanner cin = new Scanner(System.in);
static PrintWriter cout = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int[] head, next, ends;
static int tot = 0;
public static void add(int u, int v) {
ends[tot] = v;
next[tot] = head[u];
head[u] = tot++;
}
public static void dfs(int u, int from) {
dep[u] = dep[from] + 1;
for (int i = head[u]; i != -1; i = next[i]) {
int v = ends[i];
if (v == from)
continue;
fa[v][0] = u;
dfs(v, u);
}
}
public static void lca_init() {
for (int j = 1; j <= LOGN; j++)
for (int i = 1; i <= n; i++)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
public static int lca_query(int u, int v) {
if (dep[u] < dep[v]) {
int t = u;
u = v;
v = t;
}
int d = dep[u] - dep[v];
for (int j = LOGN; j >= 0; j--)
if ((d & (1 << j)) != 0)
u = fa[u][j];
if (u == v)
return u;
for (int j = LOGN; j >= 0; j--)
if (fa[u][j] != fa[v][j]) {
u = fa[u][j];
v = fa[v][j];
}
return fa[u][0];
}
public static void main(String[] args) throws Exception {
n = cin.nextInt();
m = cin.nextInt();
root = cin.nextInt();
head = new int[N * 2 + 1];
next = new int[N * 2 + 1];
ends = new int[N * 2 + 1];
Arrays.fill(head, -1);
for (int i = 1; i < n; i++) {
int u, v;
u = cin.nextInt();
v = cin.nextInt();
add(u, v);
add(v, u);
}
dfs(root, 0);
lca_init();
while (m-- > 0) {
int u, v;
u = cin.nextInt();
v = cin.nextInt();
cout.println(lca_query(u, v));
}
cout.close();
}
}
4.DP
背包
1.01背包
for(int i = 1; i <= n; i++)
for(int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
2.完全背包
for(int i = 1; i <= n; i++)
for(int j = v[i]; j <= m; j++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
3.多重背包(\(O(NMS)\))
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
for(int k = 0; k <= s[i] && k * v[i] <= j; k++)
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
4.分组背包
const int N = 110;
int n, m;
int f[N], w[N][N], v[N][N], s[N];
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
cin>>s[i];
for(int j = 0; j < s[i]; j++)
cin>>v[i][j]>>w[i][j];
}
for(int i = 1; i <= n; i++)
for(int j = m; j >= 0; j--)
for(int k = 0; k < s[i]; k++)
if(v[i][k] <= j)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
cout<<f[m];
}
LCS
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if(a[i] == b[j])
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
LIS
\(O(N^2)\)
for(int i = 1; i <= n; i++)
{
f[i] = 1;
for(int j = 1; j < i; j++)
if(a[i] > a[j])
f[i] = max(f[i], f[j] + 1);
}
ans = f[1];
for(int i = 1; i <= n;i++)
ans = max(ans, f[i]);
\(O(N\log N)\)
int len = 0;
for (int i = 0; i < n; i++)
{
int l = 0, r = len;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (a[i] > q[mid]) l=mid;
else r = mid-1;
}
len = max(len, r + 1);
q[r + 1] = a[i];
}
cout << len << endl;