基础算法技巧总结：数据结构与数论模板

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 的个数

代码实现 (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 区间和

代码实现 (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

代码实现 (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 单链表

代码实现 (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!=-;i=ne[i]){ System.out.print(e[i]+); } }     { head=-; idx=; }     { e[idx]=x; ne[idx]=head; head=idx++; }    { ne[k]=ne[ne[k]]; }    { e[idx]=x; ne[idx]=ne[k]; ne[k]=idx++; } }

2.2 双链表

代码实现 (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 模拟栈

代码实现 (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 模拟队列

代码实现 (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 模板

代码实现 (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 滑动窗口

代码实现 (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 字符串统计

代码实现 (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++){  x=s.charAt(i)-; (son[p][x]==){ son[p][x]=++idx; } p=son[p][x]; } cnt[p]++; }    {  p=; ( i=;i<s.length();i++){  x=s.charAt(i)-; (son[p][x]==)  ; p=son[p][x]; }  cnt[p]; } }

2.7.2 最大异或对

代码实现 (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( i=;i>=;i--){  u=(x>>i)&; (son[p][u]==){ son[p][u]=++idx; } p=son[p][u]; } }    {  p=,res=; ( i=;i>=;i--){  u=(x>>i)&;  flag; (u==) flag=;  flag=; (son[p][flag]!=){ p=son[p][flag]; res=res*+flag; }  { p=son[p][u]; res=res*+u; } }  res; } }

3.哈希表与 Set

3.1 模拟散列表

代码实现 (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=; }  t; } }

3.2 字符串哈希

代码实现 (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"); }  { System.out.println(); } } }    {  h[r]-h[l-]*p[r-l+]; } }

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 找出字符串中所有字母异位词

代码实现 (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 试除法求质数

代码实现 (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 分解质因数

代码实现 (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 筛质数

代码实现 (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 试除法求约数

代码实现 (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 最大公约数

代码实现 (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 模板

代码实现 (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 快速幂求逆元

代码实现 (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 求组合数

代码实现 (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-])%MOD; } } } }

4.5 博弈论

4.5.1 Nim 博弈

代码实现 (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; }

基础算法技巧总结：数据结构与数论模板

1.算法技巧零碎点

1.1 高精度算法

1.2 位运算

1.2.1 统计二进制中 1 的个数

1.3 离散化

1.3.1 区间和

1.4 KMP

1.5 进制转化

1.6 时间转化

2.基础数据结构

2.1 单链表

2.2 双链表

2.3 模拟栈

2.4 模拟队列

2.5 单调栈

2.5.1 模板

2.5.2 每日温度

2.6 单调队列

2.6.1 滑动窗口

2.7 Tire 树

2.7.1 Tire 字符串统计

2.7.2 最大异或对

3.哈希表与 Set

3.1 模拟散列表

3.2 字符串哈希

3.3 有效的字母异位词

3.4 赎金信

3.5 两个数组的交集

3.6 快乐数

3.7 最长连续序列

3.8 两数之和

3.9 四数相加 2

3.10 字母异位词分组

3.11 找出字符串中所有字母异位词

4.数论

4.1 质数

4.1.1 试除法求质数

4.1.2 分解质因数

4.1.3 筛质数

4.2 约数

4.2.1 试除法求约数

4.2.2 最大公约数

4.3 快速幂

4.3.1 模板

4.3.2 快速幂求逆元

4.4 求组合数

4.5 博弈论

4.5.1 Nim 博弈

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具