基础算法技巧总结2(算法技巧零碎点，基础数据结构，数论模板)
1.算法技巧零碎点
1.1 高精度算法
Java提供BigInteger与BigDecimal两个类实现高精度运算
import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String n1=sc.next(); String n2=sc.next(); BigInteger b1=new BigInteger(n1); BigInteger b2=new BigInteger(n2); BigInteger sum=b1.add(b2);//加 BigInteger diff=b1.subtract(b2);//减 BigInteger product=b1.multiply(b2);//乘 BigInteger quotient=b1.divide(b2);//除 BigInteger remainder=b1.remainder(b2);//取余 } } import java.math.BigDecimal; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String n1=sc.next(); String n2=sc.next(); BigDecimal b1=new BigDecimal(n1); BigDecimal b2=new BigDecimal(n2); BigDecimal sum=b1.add(b2);//加 BigDecimal diff=b1.subtract(b2);//减 BigDecimal product=b1.multiply(b2);//乘 BigDecimal quotient=b1.divide(b2);//除 BigDecimal remainder=b1.remainder(b2);//取余 //返回一个长度为 2 的数组，第一个元素是商（整数部分），第二个元素是余数 BigDecimal[] arr = b1.divideAndRemainder(b2); } }1.2 位运算
1.2.1 统计二进制中1的个数
https://www.acwing.com/problem/content/803/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int arr[N]; int n; //最低位1对应的十进制数 int lowBit(int x){ return x&-x; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>arr[i]; int cnt=0; while(arr[i]!=0){ arr[i]-=lowBit(arr[i]); cnt++; } cout<<cnt<<" "; } return 0; } import java.util.Scanner; public class Main { public static final int N= (int) (1e6+10); public static int n; public static int []arr=new int[N]; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); for(int i=1;i<=n;i++) arr[i]=sc.nextInt(); for(int i=1;i<=n;i++){ int cnt=0; while(arr[i]!=0){ arr[i]-=lowBit(arr[i]); cnt++; } System.out.print(cnt+" "); } } private static int lowBit(int x) { return x&-x; } } 1.3 离散化
1.3.1 区间和
https://www.acwing.com/problem/content/804/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; const int N=3e5+10; typedef pair<int,int> PII; int n,m; int arr[N],preSum[N]; vector<int> alls; //坐标 vector<PII> add,query;//操作 int find(int x){ int l=0,r=alls.size()-1; while(r>l){ int mid=(l+r)>>1; if(alls[mid]>=x){ r=mid; } else { l=mid+1; } } return r+1; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=0;i<n;i++){ int x,c; cin>>x>>c; add.push_back({x,c}); alls.push_back(x); } for(int i=0;i<m;i++){ int l,r; cin>>l>>r; query.push_back({l,r}); alls.push_back(l); alls.push_back(r); } sort(alls.begin(),alls.end()); alls.erase(unique(alls.begin(),alls.end()),alls.end()); for(auto t:add){ int x=find(t.first); arr[x]+=t.second; } for(int i=1;i<=alls.size();i++){ preSum[i]=preSum[i-1]+arr[i]; } for(auto t:query){ int l=find(t.first); int r=find(t.second); cout<<preSum[r]-preSum[l-1]<<endl; } return 0; } import java.util.*; class Node{ int x,y; public Node(int x,int y){ this.x=x; this.y=y; } } public class Main { public static final int N= (int) (3e5+10); public static int n,m; public static int []arr=new int[N]; public static int []preSum=new int[N]; public static Set<Integer> set=new TreeSet<>();//自动去重＋排序 public static ArrayList<Integer> alls;//坐标 public static ArrayList<Node> add=new ArrayList<>(),query=new ArrayList<>();//操作 public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt(); for(int i=0;i<n;i++){ int x=sc.nextInt(); int c=sc.nextInt(); add.add(new Node(x,c)); set.add(x); } for(int i=0;i<m;i++){ int l=sc.nextInt(); int r=sc.nextInt(); query.add(new Node(l,r)); set.add(l); set.add(r); } alls=new ArrayList<>(set);//数据迁移 for(Node t:add){ int x=find(t.x); arr[x]+=t.y; } for(int i=1;i<=alls.size();i++){ preSum[i]=preSum[i-1]+arr[i]; } for(Node t:query){ int l=find(t.x),r=find(t.y); System.out.println(preSum[r]-preSum[l-1]); } } public static int find(int x){ int l=0,r=alls.size()-1; while (r>l){ int mid=(l+r)>>1; if(alls.get(mid)>=x){ r=mid; } else { l=mid+1; } } return r+1; } } 1.4 KMP
https://www.acwing.com/problem/content/833/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int n,m; char p[N];//模式串 char s[N];//母串 int ne[N];//前缀数组 int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n>>p>>m>>s; int j=0; ne[0]=0; //求前缀数组 for(int i=1;i<n;i++){ //匹配失败 while(j>0 && p[i]!=p[j]){ j=ne[j-1]; } //匹配成功 if(p[i]==p[j]) j++; ne[i]=j; } //字符串匹配 j=0;//模式串指针 for(int i=0;i<m;i++){ //匹配失败 while(j>0 && p[j]!=s[i]){ j=ne[j-1]; } //匹配成功 if(p[j]==s[i]) j++; if(j==n) cout<<i-n+1<<" "; } return 0; } import java.util.*; public class Main { public static final int N = (int) (1e6 + 10); public static int n, m; public static char[] p, s; // 改为char[]数组类型 public static int[] ne = new int[N]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); // 读取字符串后直接转为char[]数组 p = sc.next().toCharArray(); m = sc.nextInt(); s = sc.next().toCharArray(); int j = 0; ne[0] = 0; for (int i = 1; i < n; i++) { // 匹配失败：直接访问数组下标p[i]、p[j] while (j > 0 && p[i] != p[j]) { j = ne[j - 1]; } // 匹配成功：直接访问数组下标p[i]、p[j] if (p[i] == p[j]) j++; ne[i] = j; } // 字符串匹配 j = 0;// 模式串指针 for (int i = 0; i < m; i++) { // 匹配失败：直接访问数组下标p[j]、s[i] while (j > 0 && p[j] != s[i]) { j = ne[j - 1]; } // 匹配成功：直接访问数组下标p[j]、s[i] if (p[j] == s[i]) j++; if (j == n) { System.out.print(i - n + 1 + " "); // 核心回退：避免后续下标越界，同时支持继续匹配 j = ne[j - 1]; } } } }1.5 进制转化
Java提供进制转化API
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s1=sc.next();//1010 int origin=sc.nextInt();//2 //将origin进制数s1转化为十进制数 int tenValue=Integer.parseInt(s1,origin); System.out.println(tenValue);//10 int target=16; //将十进制数tenValue转为target进制数 String res=Integer.toString(tenValue,target); String s=res.toUpperCase();//转为大写字母（可选） System.out.println(res); } } 1.6 时间转化
代码实现(C++/Java)
import java.text.ParseException; import java.text.SimpleDateFormat; import java.util.*; public class Main { public static void main(String[] args) throws ParseException { Scanner sc = new Scanner(System.in); SimpleDateFormat sdf=new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); sdf.setTimeZone(TimeZone.getTimeZone("UTC"));//设置标准时间 int t=sc.nextInt(); sc.nextLine(); for (int i = 0; i < t; i++) { String s=sc.nextLine(); String[] part=s.split(" "); String s1=part[0]+" "+part[1]; int x= Integer.parseInt(part[2]); Date date=sdf.parse(s1); long time=date.getTime()/1000; long gap=x*60; long res=(time/gap)*gap; Date date1=new Date(res*1000); System.out.println(sdf.format(date1)); } } } 2.基础数据结构
2.1 单链表
https://www.acwing.com/problem/content/828/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int head,e[N],ne[N],idx; void init(){ head=-1; idx=0; } void add_to_head(int x){ e[idx]=x; ne[idx]=head; head=idx++; } void del(int k){ ne[k]=ne[ne[k]]; } void insert(int k,int x){ e[idx]=x; ne[idx]=ne[k]; ne[k]=idx++; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int m; cin>>m; init();//初始化链表 for(int i=1;i<=m;i++){ int k,x; char op; cin>>op; if(op=='H'){ cin>>x; add_to_head(x); } else if(op=='D'){ cin>>k; if(k==0) head=ne[head]; else del(k-1); } else { cin>>k>>x; insert(k-1,x); } } for(int i=head;i!=-1;i=ne[i]){ cout<<e[i]<<" "; } cout<<endl; return 0; } import java.util.*; public class Main { public static final int N= (int) (1e6+10); public static int m; public static int head,idx; public static int []e=new int[N]; public static int []ne=new int[N]; public static void main(String[] args) { Scanner sc=new Scanner(System.in); m=sc.nextInt(); init(); for(int i=1;i<=m;i++){ char op; op=sc.next().charAt(0); if(op=='H'){ int x=sc.nextInt(); addToHead(x); } else if(op=='D'){ int k=sc.nextInt(); if(k==0) head=ne[head]; else del(k-1); } else { int k=sc.nextInt(); int x=sc.nextInt(); insert(k-1,x); } } for(int i=head;i!=-1;i=ne[i]){ System.out.print(e[i]+" "); } } private static void init() { head=-1; idx=0; } private static void addToHead(int x) { e[idx]=x; ne[idx]=head; head=idx++; } private static void del(int k){ ne[k]=ne[ne[k]]; } private static void insert(int k,int x){ e[idx]=x; ne[idx]=ne[k]; ne[k]=idx++; } } 2.2 双链表
https://www.acwing.com/problem/content/829/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int m; int e[N],l[N],r[N],idx; //在节点a右边插入一个数 void insert(int a,int x){ e[idx]=x; l[idx]=a; r[idx]=r[a]; l[r[a]]=idx; r[a]=idx++; } //删除节点a void remove(int a){ l[r[a]]=l[a]; r[l[a]]=r[a]; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>m; //初始化链表(0为左端点，1为右端点) r[0]=1,l[1]=0; idx=2; for(int i=1;i<=m;i++){ string op; int k,x; cin>>op; if(op=="L"){ cin>>x; insert(0,x); }else if(op=="R"){ cin>>x; insert(l[1],x); }else if(op=="D"){ cin>>k; remove(k+1); }else if(op=="IL"){ cin>>k>>x; insert(l[k+1],x); }else{ cin>>k>>x; insert(k+1,x); } } for(int i=r[0];i!=1;i=r[i]){ cout<<e[i]<<" "; } cout<<endl; return 0; }2.3 模拟栈
https://www.acwing.com/problem/content/830/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int m; int stk[N]; int top; int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>m; for(int i=1;i<=m;i++){ string op; cin>>op; if(op=="push"){ int x; cin>>x; stk[++top]=x; } else if(op=="pop"){ top--; } else if(op=="empty"){ if(top==0) cout<<"YES"<<endl; else cout<<"NO"<<endl; } else { cout<<stk[top]<<endl; } } return 0; }import java.util.*; public class Main { public static final int N= (int) (1e6+10); public static int m; public static int []stack=new int[N]; public static int top; public static void main(String[] args) { Scanner sc = new Scanner(System.in); m=sc.nextInt(); for(int i=1;i<=m;i++){ String op=sc.next(); if(op.equals("push")){ int x=sc.nextInt(); stack[++top]=x; } else if(op.equals("pop")){ top--; } else if(op.equals("empty")){ if(top==0) System.out.println("YES"); else System.out.println("NO"); } else { System.out.println(stack[top]); } } } } 2.4 模拟队列
https://www.acwing.com/problem/content/831/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int m; int q[N]; int l=0,r=-1; int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>m; for(int i=1;i<=m;i++){ string op; cin>>op; if(op=="push"){ int x; cin>>x; q[++r]=x; } else if(op=="pop"){ l++; } else if(op=="empty"){ if(l>r) cout<<"YES"<<endl; else cout<<"NO"<<endl; } else { cout<<q[l]<<endl; } } return 0; }import java.util.*; public class Main { public static final int N= (int) (1e6+10); public static int m; public static int []q=new int[N]; public static int r=-1,l=0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); m=sc.nextInt(); for(int i=1;i<=m;i++){ String op=sc.next(); if(op.equals("push")){ int x=sc.nextInt(); q[++r]=x; } else if (op.equals("pop")) { l++; } else if(op.equals("empty")){ if(l>r) System.out.println("YES"); else System.out.println("NO"); }else { System.out.println(q[l]); } } } } 2.5 单调栈
2.5.1 模板
https://www.acwing.com/problem/content/832/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n; int stk[N]; int top; int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ int x; cin>>x; while(top!=0 && stk[top]>=x){ top--; } if(top==0) cout<<"-1"<<" "; else cout<<stk[top]<<" "; stk[++top]=x; } return 0; }import java.util.*; public class Main { public static final int N= (int) (1e5+10); public static int n; public static int[] stack=new int[N]; public static int top; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n=sc.nextInt(); for(int i=1;i<=n;i++){ int x=sc.nextInt(); while (top!=0 && stack[top]>=x){ top--; } if(top==0) System.out.print("-1"+" "); else System.out.print(stack[top]+" "); stack[++top]=x; } } } 2.5.2 每日温度
代码实现(C++/Java)
class Solution { public: //下一个更大元素 vector<int> dailyTemperatures(vector<int>& temperatures) { int n=temperatures.size(); int stk[n]; int top=0; vector<int> res(n,0); for(int i=0;i<n;i++){ int t=temperatures[i]; while(top!=0 && t>temperatures[stk[top]]){ int idx=stk[top--]; res[idx]=i-idx; } stk[++top]=i; } return res; } };class Solution { public static int[] stk; public static int[] res; public int[] dailyTemperatures(int[] temperatures) { int n=temperatures.length; int top=0; stk=new int[n]; res=new int[n]; for(int i=0;i<n;i++){ int t=temperatures[i]; while(top!=0 && t>temperatures[stk[top]]){ int idx=stk[top--]; res[idx]=i-idx; } stk[++top]=i; } return res; } }2.6 单调队列
2.6.1 滑动窗口
https://www.acwing.com/problem/content/156/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int n,k; int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n>>k; vector<int> arr(n); for(int i=0;i<n;i++) cin>>arr[i]; deque<int> q;//双端队列 //求最小值 for(int i=0;i<n;i++){ //队头是否划出窗口 if(!q.empty() && q.front()<=i-k){ q.pop_front(); } //单调性维护：队尾>=当前元素 弹出 while(!q.empty() && arr[q.back()]>=arr[i]){ q.pop_back(); } //入队 q.push_back(i); if(i>=k-1) cout<<arr[q.front()]<<" "; } cout<<endl; q.clear(); //最大值 for(int i=0;i<n;i++){ if(!q.empty() && q.front()<=i-k){ q.pop_front(); } while(!q.empty() && arr[q.back()]<=arr[i]){ q.pop_back(); } q.push_back(i); if(i>=k-1) cout<<arr[q.front()]<<" "; } cout<<endl; return 0; } import java.util.*; public class Main { public static int n,k; public static int[]arr; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n=sc.nextInt(); k=sc.nextInt(); arr=new int[n+10]; for(int i=0;i<n;i++) arr[i]=sc.nextInt(); ArrayDeque<Integer> q=new ArrayDeque<>(); //最小值 for(int i=0;i<n;i++){ if(!q.isEmpty() && q.peekFirst()<=i-k){ q.pollFirst();//弹出首元素 } while(!q.isEmpty() && arr[q.peekLast()]>=arr[i]){ q.pollLast(); } q.addLast(i); if(i>=k-1){ System.out.print(arr[q.peekFirst()]+" "); } } System.out.println(); q.clear(); //最大值 for(int i=0;i<n;i++){ if(!q.isEmpty() && q.peekFirst()<=i-k){ q.pollFirst(); } while (!q.isEmpty() && arr[q.peekLast()]<=arr[i]){ q.pollLast(); } q.addLast(i); if(i>=k-1){ System.out.print(arr[q.peekFirst()]+" "); } } System.out.println(); } } 2.7 Tire树
2.7.1 Tire字符串统计
https://www.acwing.com/problem/content/837/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int idx; int son[N][26];//节点编号 int cnt[N];//该节点结尾出现的次数 void insert(string s){ int p=0; for(int i=0;s[i];i++){ int x=s[i]-'a'; if(!son[p][x]){ son[p][x]=++idx; } p=son[p][x]; } cnt[p]++; } int query(string s){ int p=0; for(int i=0;s[i];i++){ int x=s[i]-'a'; if(!son[p][x]) return 0; p=son[p][x]; } return cnt[p]; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ char c; char s[N]; cin>>c>>s; if(c=='I') insert(s); else cout<<query(s)<<endl; } return 0; }import java.util.*; public class Main { public static final int N= (int) (1e5+10); public static int n,m; public static int[][]son=new int[N][26]; public static int []cnt=new int[N]; public static int idx; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n=sc.nextInt(); for(int i=0;i<n;i++){ char c; String s; c=sc.next().charAt(0); s=sc.next(); if(c=='I') insert(s); else System.out.println(query(s)); } } public static void insert(String s){ int p=0; for(int i=0;i<s.length();i++){ int x=s.charAt(i)-'a'; if(son[p][x]==0){ son[p][x]=++idx; } p=son[p][x]; } cnt[p]++; } public static int query(String s){ int p=0; for(int i=0;i<s.length();i++){ int x=s.charAt(i)-'a'; if(son[p][x]==0) return 0; p=son[p][x]; } return cnt[p]; } }2.7.2 最大异或对
https://www.acwing.com/problem/content/145/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; const int M=N*31;//N个数，每个数占31位，共M节点 int n; int arr[N]; int son[M][2]; int idx; void insert(int x){ int p=0; //从最高位开始 for(int i=30;i>=0;i--){ //取出x的第i位 int u=x>>i&1; if(!son[p][u]){ son[p][u]=++idx; } p=son[p][u]; } } int query(int x){ int p=0,res=0; for(int i=30;i>=0;i--){ int u=x>>i&1; //尝试走相反方向 if(son[p][!u]){ p=son[p][!u]; res=res*2+!u; } else { p=son[p][u]; res=res*2+u; } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n; for(int i=0;i<n;i++) cin>>arr[i]; int res=0; for(int i=0;i<n;i++){ insert(arr[i]); int t=query(arr[i]);//在已有树中查找最佳匹配项 res=max(res,arr[i]^t); } cout<<res<<endl; return 0; } import java.util.*; public class Main { public static final int N= (int) (1e5+10),M=N*31; public static int n; public static int []arr=new int[N]; public static int[][]son=new int[M][2]; public static int idx; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n=sc.nextInt(); for(int i=0;i<n;i++){ arr[i]=sc.nextInt(); } int res=0; for(int i=0;i<n;i++){ insert(arr[i]); int t=query(arr[i]); res=Math.max(res,t^arr[i]); } System.out.println(res); } public static void insert(int x){ int p=0; for(int i=30;i>=0;i--){ int u=(x>>i)&1; if(son[p][u]==0){ son[p][u]=++idx; } p=son[p][u]; } } public static int query(int x){ int p=0,res=0; for(int i=30;i>=0;i--){ int u=(x>>i)&1; int flag; if(u==1) flag=0; else flag=1; if(son[p][flag]!=0){ p=son[p][flag]; res=res*2+flag; } else { p=son[p][u]; res=res*2+u; } } return res; } } 3.哈希表与Set
3.1 模拟散列表
https://www.acwing.com/problem/content/842/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; const int N=3e5+10; const int MAX=0x3f3f3f3f; int h[N]; int n; int find(int x){ int t=(x%N+N)%N;//防止负数 while(h[t]!=MAX && h[t]!=x){ t++; if(t==N) t=0; } return t; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); memset(h,MAX,sizeof(h)); cin>>n; for(int i=0;i<n;i++){ char op; int x; cin>>op>>x; if(op=='I'){ h[find(x)]=x; } else { if(h[find(x)]!=MAX) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } return 0; } import java.util.*; public class Main { public static final int MAX=0x3f3f3f3f; public static final int N= (int) (3e5+10); public static int []h=new int[N]; public static int n; public static void main(String[] args) { Scanner sc = new Scanner(System.in); Arrays.fill(h,MAX); n=sc.nextInt(); for(int i=0;i<n;i++){ char op=sc.next().charAt(0); int x=sc.nextInt(); if(op=='I'){ h[find(x)]=x; } else { if(h[find(x)]!=MAX) System.out.println("Yes"); else System.out.println("No"); } } } public static int find(int x){ int t=(x%N+N)%N; while(h[t]!=MAX && h[t]!=x){ t++; if(t==N) t=0; } return t; } } 3.2 字符串哈希
https://www.acwing.com/problem/content/843/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; typedef long long ll; int n,m; ll P=131; ll p[N]; ll h[N]; ll get(int l,int r){ return h[r]-h[l-1]*p[r-l+1]; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n>>m; string s; cin>>s; p[0]=1; for(int i=1;i<=n;i++){ p[i]=p[i-1]*P; h[i]=h[i-1]*P+s[i-1]; } for(int i=0;i<m;i++){ int l1,r1,l2,r2; cin>>l1>>r1>>l2>>r2; if(get(l1,r1)==get(l2,r2)){ cout<<"Yes"<<endl; } else { cout<<"No"<<endl; } } return 0; } import java.util.*; public class Main { public static final int N= (int) (1e5+10); public static int n,m; public static long P=131L; public static long[] p=new long[N]; public static long[] h=new long[N]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt(); String s=sc.next(); p[0]=1; for(int i=1;i<=n;i++){ p[i]=p[i-1]*P; h[i]=h[i-1]*P+s.charAt(i-1); } for(int i=0;i<m;i++){ int l1=sc.nextInt(); int r1=sc.nextInt(); int l2=sc.nextInt(); int r2=sc.nextInt(); if(get(l1,r1)==get(l2,r2)){ System.out.println("Yes"); } else { System.out.println("No"); } } } public static long get(int l,int r){ return h[r]-h[l-1]*p[r-l+1]; } } 3.3 有效的字母异位词
代码实现(C++/Java)
class Solution { public: bool isAnagram(string s, string t) { int hash1[26]; int hash2[26]; for(int i=0;i<s.size();i++) hash1[s[i]-'a']++; for(int i=0;i<t.size();i++) hash2[t[i]-'a']++; for(int i=0;i<=25;i++){ if(hash1[i]!=hash2[i]) return false; } return true; } };3.4 赎金信
代码实现(C++/Java)
class Solution { public: bool canConstruct(string s, string t) { int hash1[26]; int hash2[26]; for(int i=0;i<s.size();i++) hash1[s[i]-'a']++; for(int i=0;i<t.size();i++) hash2[t[i]-'a']++; for(int i=0;i<=25;i++){ if(hash1[i]>hash2[i]) return false; } return true; } };3.5 两个数组的交集
代码实现(C++/Java)
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> set1,set2; for(int i=0;i<nums1.size();i++) set1.insert(nums1[i]); for(int i=0;i<nums2.size();i++){ if(set1.contains(nums2[i])){ set2.insert(nums2[i]); } } return vector<int>(set2.begin(),set2.end()); } };class Solution { public int[] intersection(int[] nums1, int[] nums2) { //HashSet乱序，TreeSet自动排序 Set<Integer> set1=new TreeSet<>(); Set<Integer> set2=new TreeSet<>(); for(int i=0;i<nums1.length;i++){ set1.add(nums1[i]); } for(int i=0;i<nums2.length;i++){ if(set1.contains(nums2[i])){ set2.add(nums2[i]); } } int []res=new int[set2.size()]; int cnt=0; for(int s:set2){ res[cnt++]=s; } return res; } }3.6 快乐数
代码实现(C++/Java)
class Solution { public: int getSum(int n){ int sum=0; while(n>0){ int t=n%10; sum+=t*t; n/=10; } return sum; } bool isHappy(int n) { set<int> set; while(true){ int sum=getSum(n); if(sum==1) return true; if(set.contains(sum)) return false; set.insert(sum); n=sum; } } };class Solution { public boolean isHappy(int n) { Set<Integer> set=new TreeSet<>(); while(true){ int sum=getSum(n); if(sum==1) return true; if(set.contains(sum)) return false; set.add(sum); n=sum; } } public static int getSum(int n){ int sum=0; while(n>0){ int t=n%10; sum+=t*t; n/=10; } return sum; } }3.7 最长连续序列
代码实现(C++/Java)
class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> set;//哈希Set for(int i=0;i<nums.size();i++) set.insert(nums[i]); int res=0; for(int s:set){ if(!set.contains(s-1)){ int cur=s; int len=1; while(set.contains(cur+1)){ cur++; len++; } res=max(len,res); } } return res; } };class Solution { public int longestConsecutive(int[] nums) { //HashSet(O(n)),TreeSet(nlogn) HashSet<Integer> set=new HashSet<>(); for(int i=0;i<nums.length;i++) set.add(nums[i]); int res=0; for(int s:set){ if(!set.contains(s-1)){ int len=1; int cur=s; while(set.contains(cur+1)){ cur++; len++; } res=Math.max(res,len); } } return res; } }3.8 两数之和
代码实现(C++/Java)
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> map; for(int i=0;i<nums.size();i++){ if(map.count(target-nums[i])){ return {i,map[target-nums[i]]}; }else{ map[nums[i]]=i; } } return {}; } };class Solution { public int[] twoSum(int[] nums, int target) { HashMap<Integer,Integer> map=new HashMap<>(); for(int i=0;i<nums.length;i++){ if(map.containsKey(target-nums[i])){ return new int[]{i,map.get(target-nums[i])}; }else { map.put(nums[i],i); } } return new int[]{}; } }3.9 四数相加2
代码实现(C++/Java)
class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int,int> map; for(int a:nums1){ for(int b:nums2){ int s=a+b; map[s]++; } } int cnt=0; for(int c:nums3){ for(int d:nums4){ int s=-(c+d); if(map.count(s)){ cnt+=map[s]; } } } return cnt; } };class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { HashMap<Integer,Integer> map=new HashMap<>(); for(int i=0;i<nums1.length;i++){ for(int j=0;j<nums2.length;j++){ int s=nums1[i]+nums2[j]; map.put(s,map.getOrDefault(s,0)+1); } } int cnt=0; for(int i=0;i<nums3.length;i++){ for(int j=0;j<nums4.length;j++){ int s=-(nums3[i]+nums4[j]); if(map.containsKey(s)){ cnt+=map.get(s); } } } return cnt; } }3.10 字母异位词分组
代码实现(C++/Java)
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<vector<string>> res; unordered_map<string,vector<string>> map; for(string s:strs){ string key=s; sort(key.begin(),key.end()); //key不存在，会创建vector map[key].push_back(s); } for(auto t:map){ res.push_back(t.second); } return res; } };class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String,List<String>> map=new HashMap<>(); for(String s:strs){ char[]ch=s.toCharArray(); Arrays.sort(ch); String key=new String(ch); map.computeIfAbsent(key,k->new ArrayList<>()).add(s); } return new ArrayList<>(map.values()); } }3.11 找出字符串中所有字母异位词
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
代码实现(C++/Java)
class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> res; int h[27]; int w[27]; int n=s.size(); int m=p.size(); if(m>n) return res; for(int i=0;i<m;i++) h[p[i]-'a']++; for(int i=0;i<n;i++){ w[s[i]-'a']++; if(i>=m) w[s[i-m]-'a']--; if(i>=m-1 && fun(h,w)) res.push_back(i-m+1); } return res; } bool fun(int h[],int w[]){ for(int i=0;i<=25;i++){ if(h[i]!=w[i]) return false; } return true; } };class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> res=new ArrayList<>(); int []h=new int[27]; int []w=new int[27]; int n=s.length(); int m=p.length(); if(n<m) return res; for(int i=0;i<m;i++){ h[p.charAt(i)-'a']++; } for(int i=0;i<n;i++){ w[s.charAt(i)-'a']++; if(i>=m) w[s.charAt(i-m)-'a']--; if(i>=m-1 && fun(h,w)) res.add(i-m+1); } return res; } public static boolean fun(int[]h,int[] w){ for(int i=0;i<=25;i++){ if(h[i]!=w[i]) return false; } return true; } }4.数论
4.1 质数
4.1.1 试除法求质数
https://www.acwing.com/problem/content/868/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; const int N=110; int n; int arr[N]; bool isPrimer(int x){ if(x<=1) return false; for(int i=2;i<=x/i;i++){ if(x%i==0) return false; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n; for(int i=0;i<n;i++) cin>>arr[i]; for(int i=0;i<n;i++){ if(isPrimer(arr[i])) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }import java.util.*; public class Main { public static final int N=110; public static int n; public static int[] arr=new int[N]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n=sc.nextInt(); for(int i=0;i<n;i++) arr[i]=sc.nextInt(); for(int i=0;i<n;i++){ if(isPrimer(arr[i])) System.out.println("Yes"); else System.out.println("No"); } } public static boolean isPrimer(int x){ if(x<=1) return false; for(int i=2;i<=x/i;i++){ if(x%i==0) return false; } return true; } }4.1.2 分解质因数
https://www.acwing.com/problem/content/869/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; //质因数：一个数分解成乘法时，所有的乘数必须是质数 //底数：不断重复地质数，底数：这个质数的重复次数 const int N=110; int n; int arr[N]; void fun(int x){ for(int i=2;i<=x/i;i++){ if(x%i==0){ int s=0; while(x%i==0){ x/=i; s++; } cout<<i<<" "<<s<<endl; } } if(x>1) cout<<x<<" "<<1<<endl; cout<<endl; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n; for(int i=0;i<n;i++) cin>>arr[i]; for(int i=0;i<n;i++) fun(arr[i]); return 0; } import java.util.*; public class Main { public static final int N=110; public static int n; public static int[]arr=new int[N]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n=sc.nextInt(); for(int i=0;i<n;i++){ arr[i]=sc.nextInt(); } for(int i=0;i<n;i++){ fun(arr[i]); } } public static void fun(int x){ for(int i=2;i<=x/i;i++){ if(x%i==0){ int s=0; while(x%i==0){ x/=i; s++; } System.out.println(i+" "+s); } } if(x>1) System.out.println(x+" "+1); System.out.println(); } }4.1.3 筛质数
https://www.acwing.com/problem/content/870/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; //线性筛质数:所有合数都删掉，剩下的自然就是质数。 //只要把所有质数的倍数都标记为“非质数”，剩下的就是质数。 const int N=1e6+10; int n; bool status[N];//标记 i 是否是合数 int primes[N];//找到的所有质数 int cnt; int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n; for(int i=2;i<=n;i++){ //i没有被筛掉，它就是质数 if(!status[i]){ primes[cnt++]=i; } //用当前质数筛掉合数 for(int j=0;primes[j]<=n/i;j++){ status[primes[j]*i]=true; //把 primes[j] 的 i 倍标记为合数 //primes[j] 已经是 i 的因子了 if(i%primes[j]==0) break; } } cout<<cnt<<endl; return 0; }import java.util.*; public class Main { public static final int N= (int) (1e6+10); public static int n; public static int cnt; public static int[]primes=new int[N]; public static boolean[]status=new boolean[N]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n=sc.nextInt(); for(int i=2;i<=n;i++){ //i没有被筛掉 if(!status[i]){ primes[cnt++]=i; } //用当前质数筛掉合数 for(int j=0;primes[j]<=n/i;j++){ status[primes[j]*i]=true; if(i%primes[j]==0) break; } } System.out.println(cnt); } } 4.2 约数
4.2.1 试除法求约数
https://www.acwing.com/problem/content/871/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; //约数：如果一个整数 a 除以另一个整数 b（b ≠ 0），得到的商正好是整数而没有余数，我们就说 b 是 a 的约数。 const int N=110; int n; vector<int> fun(int x){ vector<int> res; for(int i=1;i<=x/i;i++){ if(x%i==0){ res.push_back(i); if(i!=x/i){ res.push_back(x/i); } } } sort(res.begin(),res.end()); return res; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n; for(int i=0;i<n;i++){ int x; cin>>x; vector<int> res=fun(x); for(int r:res){ cout<<r<<" "; } cout<<endl; } return 0; }import java.util.*; public class Main { public static int n; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n=sc.nextInt(); for(int i=0;i<n;i++){ int x=sc.nextInt(); ArrayList<Integer> res=fun(x); for(int r:res){ System.out.print(r+" "); } System.out.println(); } } private static ArrayList<Integer> fun(int x) { ArrayList<Integer> res=new ArrayList<>(); for(int i=1;i<=x/i;i++){ if(x%i==0){ res.add(i); if(i!=x/i){ res.add(x/i); } } } Collections.sort(res); return res; } } 4.2.2 最大公约数
https://www.acwing.com/problem/content/874/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; int n; //最小公倍数：a*b/gcd(a,b) int gcd(int a,int b){ return b!=0?gcd(b,a%b):a; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n; for(int i=0;i<n;i++){ int a,b; cin>>a>>b; cout<<gcd(a,b)<<endl; } return 0; } import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n=sc.nextInt(); for(int i=0;i<n;i++){ int a=sc.nextInt(); int b=sc.nextInt(); System.out.println(gcd(a,b)); } } private static int gcd(int a, int b) { return b!=0?gcd(b,a%b):a; } } 4.3 快速幂
4.3.1 模板
https://www.acwing.com/problem/content/877/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll qmi(ll a,ll b,ll p){ ll res=1%p; while (b!=0){ if((b&1)!=0){ res=res*a%p; } a=a*a%p; b>>=1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ int a,b,p; cin>>a>>b>>p; ll res=qmi(a,b,p); cout<<res<<endl; } return 0; }import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n=sc.nextInt(); for(int i=0;i<n;i++){ int a=sc.nextInt(); int b=sc.nextInt(); int p=sc.nextInt(); System.out.println(qmi(a,b,p)); } } private static long qmi(long a, long b, long p) { long res=1%p; while (b!=0){ if((b&1)!=0){ res=res*a%p; } a=a*a%p; b>>=1; } return res; } } 4.3.2 快速幂求逆元
https://www.acwing.com/problem/content/878/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll qmi(ll a,ll b,ll p){ ll res=1%p; while (b!=0){ if((b&1)!=0){ res=res*a%p; } a=a*a%p; b>>=1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ int a,p; cin>>a>>p; if(a%p==0){ cout<<"impossible"<<endl; }else { cout<<qmi(a,p-2,p)<<endl; } } return 0; }4.4 求组合数
https://www.acwing.com/problem/content/887/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; const int MOD=1e9+7; const int N=2020; int n; int arr[N][N]; void init(){ for(int i=0;i<N;i++){ for(int j=0;j<=i;j++){ if(j==0) arr[i][j]=1; else arr[i][j]=(arr[i-1][j]+arr[i-1][j-1])%MOD; } } } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); init(); cin>>n; for(int i=0;i<n;i++){ int a,b; cin>>a>>b; cout<<arr[a][b]<<endl; } return 0; } import java.util.*; public class Main{ public static final int MOD= (int) (1e9+7); public static int N=2010; public static int n; public static int[][]arr=new int[N][N]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); init(); n=sc.nextInt(); for (int i = 0; i < n; i++) { int a=sc.nextInt(); int b=sc.nextInt(); System.out.println(arr[a][b]); } } public static void init(){ for(int i=0;i<N;i++){ for(int j=0;j<=i;j++){ if(j==0) arr[i][j]=1; else arr[i][j]=(arr[i-1][j]+arr[i-1][j-1])%MOD; } } } } 4.5 博弈论
4.5.1 Nim博弈
https://www.acwing.com/problem/content/893/
代码实现(C++/Java)
#include<bits/stdc++.h> using namespace std; //异或和为零，先手必输；不为零，先手必赢。 int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n; cin>>n; int res=0; for(int i=0;i<n;i++){ int x; cin>>x; res^=x; } if(res!=0) cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }
