基础算法技巧总结2(算法技巧零碎点，基础数据结构，数论模板)
本文总结了算法和数据结构中的常用技巧，包括高精度运算、位运算、离散化、KMP字符串匹配、进制转换、时间处理等算法技巧，以及单/双链表、栈/队列、单调栈/队列、Trie树、哈希表等基础数据结构。还涵盖了数论相关算法如质数判定、分解质因数、筛质数、最大公约数、快速幂、组合数计算，以及博弈论中的Nim游戏。每种算法和数据结构都提供了C++和Java的代码实现示例，适合作为算法学习和竞赛参考。
·
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;
}
开源鸿蒙跨平台开发社区汇聚开发者与厂商，共建“一次开发，多端部署”的开源生态，致力于降低跨端开发门槛，推动万物智联创新。
更多推荐
20
0- 0
已为社区贡献1条内容
所有评论(0)