单调栈
给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1
import java.util.*;
import java.io.*;
public class Main {
static final int N = 100010, MOD = 1000000007;
static int[] stk = new int[N]; //单调栈中存储的是下标
static int[] a = new int[N];
static int[] l = new int[N];//存储答案的数组
static int top; //模拟栈的栈顶指针
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
//BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
//BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = sc.nextInt();
for(int i = 1; i <= n; i ++)
a[i] = sc.nextInt();
for(int i = 1; i <= n; i ++)
{
while(top > 0 && a[stk[top]] >= a[i]) top --;
if(top > 0) l[i] = stk[top];
else l[i] = -1;
stk[++ top] = i;
}
for(int i = 1; i <= n; i ++)
if(l[i] == -1)System.out.printf("%d ", l[i]);
else System.out.printf("%d ", a[l[i]]);
}
}
单调队列
维护一个滑动窗口,确定滑动窗口位于每个位置时,窗口中的最大值和最小值。
import java.util.*;
import java.io.*;
public class Main {
static final int N = 1000010, MOD = 1000000007;
static int[] q = new int[N]; //单调队列中存储的是下标
static int[] a = new int[N];
static int tt, hh = 1; //模拟队列的指针,tt为队尾,hh为队头
public static void main(String[] args) throws Exception {
//Scanner sc = new Scanner(System.in);
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = bf.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int k = Integer.parseInt(s[1]);
s = bf.readLine().split(" ");
for(int i = 1; i <= n; i ++)
{
a[i] = Integer.parseInt(s[i - 1]);
}
//先求最小值
for(int i = 1; i <= n; i ++)
{
while(tt >= hh && q[hh] < i - k + 1) hh ++; //判断队头合法性
while(tt >= hh && a[q[tt]] >= a[i]) tt --; //判断队尾合法性
q[++ tt] = i;
if(i >= k) bw.write(a[q[hh]] + " ");
}
bw.write("\n");
tt = 0;
hh = 1;
//求最大值
for(int i = 1; i <= n; i ++)
{
while(tt >= hh && q[hh] < i - k + 1) hh ++;
while(tt >= hh && a[q[tt]] <= a[i]) tt --;
q[++ tt] = i;
if(i >= k) bw.write(a[q[hh]] + " ");
}
bw.flush();
}
}
KMP字符串匹配
import java.util.*;
import java.io.*;
public class Main {
static final int N = 1000010, MOD = 1000000007;
static int[] ne = new int[N];
public static void main(String[] args) throws Exception {
//Scanner sc = new Scanner(System.in);
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(bf.readLine());
String p = " " + bf.readLine(); //读入p串保证下标从1开始
int m = Integer.parseInt(bf.readLine());
String s = " " + bf.readLine();
//初始化ne数组
for(int i = 2, j = 0; i <= n; i ++)
{
while(j > 0 && p.charAt(i) != p.charAt(j + 1)) j = ne[j];
if(p.charAt(i) == p.charAt(j + 1)) j ++;
ne[i] = j;
}
//开始匹配
for(int i = 1, j = 0; i <= m; i ++)
{
while(j > 0 && s.charAt(i) != p.charAt(j + 1)) j = ne[j];
if(s.charAt(i) == p.charAt(j + 1)) j ++;
if(j == n)
{
bw.write(i - n + " ");
j = ne[j];
}
}
bw.flush();
}
}
并查集
朴素版本
package test;
import java.util.*;
import java.io.*;
public class Main {
static final int N = 100010, MOD = 1000000007;
static int[] p = new int[N];
public static int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
public static void merge(int x, int y)
{
int fx = find(x);
int fy = find(y);
p[fx] = fy;
}
public static void main(String[] args) throws Exception {
//Scanner sc = new Scanner(System.in);
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = bf.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
for(int i = 1; i <= n; i ++) p[i] = i; //初始化并查集数组
while(m -- > 0)
{
s = bf.readLine().split(" ");
int x = Integer.parseInt(s[1]);
int y = Integer.parseInt(s[2]);
if(s[0].equals("Q"))
{
if(find(x) == find(y)) bw.write("Yes" + "\n");
else bw.write("No" + "\n");
}
else
{
merge(x, y);
}
}
bw.flush();
}
}
维护节点数量的并查集
import java.util.*;
import java.io.*;
public class Main {
static final int N = 100010, MOD = 998244353;
static int n, m;
static int[] p = new int[N]; //并查集数组
static int[] sz = new int[N]; // 维护集合的大小的数组
public static int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args) throws Exception {
//Scanner sc = new Scanner(System.in);
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = bf.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
for(int i = 1; i <= n; i ++)
{
p[i] = i;
sz[i] = 1;
}
for(int i = 1; i <= m; i ++)
{
s = bf.readLine().split(" ");
if(s[0].equals("C"))
{
int x = Integer.parseInt(s[1]);
int y = Integer.parseInt(s[2]);
int fx = find(x);
int fy = find(y);
if(fx != fy)
{
p[fx] = fy;
sz[fy] += sz[fx];
}
}
else if(s[0].equals("Q1"))
{
int x = Integer.parseInt(s[1]);
int y = Integer.parseInt(s[2]);
if(find(x) == find(y)) bw.write("Yes" + "\n");
else bw.write("No" + "\n");
}
else
{
int x = Integer.parseInt(s[1]);
int fx = find(x);
bw.write(sz[fx] + "\n");
}
}
bw.flush();
}
}
带权并查集
题意:输入的op为1,则代表x,y的种类不同,op为2即为查询两者是否为同一类
C++ Code
d[fx]的更新原理:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, q;
int d[N], p[N];
int find(int x)
{
if(p[x] == x)return p[x];
else
{
int fa = p[x];
p[x] = find(p[x]);
d[x] += d[fa];
return p[x];
}
}
void merge(int x, int y)
{
int fx = find(x);
int fy = find(y);
if(fx == fy) return;
p[fx] = fy;
d[fx] = ((d[x] - d[y] - 1) % 2 + 2) % 2;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> q;
for(int i = 1; i <= n; i ++)
{
p[i] = i;
d[i] = 0;
}
while(q --)
{
int op, x, y;
cin >> op >> x >> y;
if(op == 1)
{
merge(x, y);
}
else
{
if(find(x) != find(y)) cout << "Unknown"<< endl;
else if(((d[x] - d[y]) % 2 + 2) % 2 == 1) cout << "NO" << endl;
else cout << "YES" << endl;
}
}
return 0;
}
字符串Hash
package test;
import java.util.*;
import java.io.*;
public class Main {
static final int N = 100010, p = 131;
static final long Q = Long.MAX_VALUE;
static long[] P = new long[N];
static long[] h = new long[N];
public static long getans(int l, int r)
{
return h[r] - h[l - 1] * P[r - l + 1];
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
//BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
//BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = sc.nextInt();
int m = sc.nextInt();
String str = " " + sc.next(); //让字符下标从1开始
P[0] = 1;
for(int i = 1; i <= n; i ++)
{
P[i] = P[i - 1] * p % Q;
h[i] = h[i - 1] * p % Q + str.charAt(i);
}
while(m -- > 0)
{
int l1, r1, l2, r2;
l1 = sc.nextInt();
r1 = sc.nextInt();
l2 = sc.nextInt();
r2 = sc.nextInt();
if(getans(l1, r1) == getans(l2, r2)) System.out.println("Yes");
else System.out.println("No");
}
}
}
树状数组
单点修改,区间查询
import java.util.*;
import java.io.*;
public class Main {
static final int N = 100010, MOD = (int)1e9 + 7; //b为设置的偏移量
static int[] tr = new int[N], a = new int[N];
static int n, m;
public static int lowbit(int x)
{
return x & -x;
}
public static void add(int t, int x)
{
for(int i = t; i <= n; i += lowbit(i)) tr[i] += x;
}
public static int query(int x)
{
int res = 0;
for(int i = x; i > 0; i -= lowbit(i))
{
res += tr[i];
}
return res;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
//BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = sc.nextInt();
m = sc.nextInt();
for(int i = 1; i <= n; i ++)
{
a[i] = sc.nextInt();
add(i, a[i]);
}
while(m -- > 0)
{
int op, x, y;
op = sc.nextInt();
x = sc.nextInt();
y = sc.nextInt();
if(op == 0)
{
System.out.println(query(y) - query(x - 1));
}
else
{
add(x, y);
}
}
}
}
区间修改,区间查询
C++ Code:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 10, p = 1e9 + 7;
int n, q;
LL a[N], td[N], tdi[N]; //td维护差分数组d的树状数组,tdi则维护i*d的树状数组,两个树状数组跟据公式维护区间和
//树状数组模板
int lowbit(int x)
{
return x & -x;
}
void add(LL k, LL x) //对树状数组进行单点修改
{
for(int i = k; i <= n; i += lowbit(i)) td[i] += x, tdi[i] += x * k;
}
LL getsum(LL x)
{
LL res = 0;
for(int i = x; i > 0; i -= lowbit(i)) res += (x + 1) * td[i] - tdi[i];
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> q;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++)
{
add(i, a[i]), add(i + 1, -a[i]);
}
while(q --)
{
int op;
cin >> op;
if(op == 1)
{
LL l, r, v;
cin >> l >> r >> v;
add(l, v), add(r + 1, -v);
}
else
{
LL l, r;
cin >> l >> r;
cout << getsum(r) - getsum(l - 1) << endl;
}
}
return 0;
}
优先队列PriorityQueue
用法代码如下:
package test;
import java.util.*;
import java.io.*;
public class Main {
static final int N = 1010, MOD = (int)1e9 + 7;
static int[][] dp = new int[N][N];
static int n;
static class PII implements Comparable<PII>
{
int x, y;
public PII(int x, int y)
{
this.x = x;
this.y = y;
}
//堆先以x为关键字从小到大排序,再以y为关键字从大到小排序
public int compareTo(PII v) {
if(x != v.x) return x - v.x;
else return v.y - y;
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
//BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 大根堆
Queue<Integer> pqb = new PriorityQueue<>(Collections.reverseOrder());
// 小根堆
Queue<Integer> pqs = new PriorityQueue<>();
pqs.add(1);
pqs.add(2);
pqs.add(3);
pqb.add(1);
pqb.add(2);
pqb.add(3);
while(pqs.size() > 0)
{
System.out.printf("%d ", pqs.remove());
}
System.out.println();
while(pqb.size() > 0)
{
System.out.printf("%d ", pqb.remove());
}
System.out.println();
//带类自定义排序的堆
Queue<PII> pqt = new PriorityQueue<>();
pqt.add(new PII(1, 3));
pqt.add(new PII(2, 4));
pqt.add(new PII(4, 1));
pqt.add(new PII(4, 3));
while(pqt.size() > 0)
{
PII t = pqt.remove();
System.out.printf("%d %d\n", t.x, t.y);
}
}
}
Map补充知识
package test;
import java.util.*;
public class Main{
static int mod = (int)1e9 + 7;
public static void main(String[] args){
Map<Integer,Integer> map = new HashMap<>(); //创建一个哈希表
Scanner scan = new Scanner(System.in);
Map<String, Integer> mp = new HashMap<>();
mp.put("abc", 1);
mp.put("abc", 2);
mp.put("cde", 2);
//给当前映射值加一的方法,直接用get会报错
mp.put("cde", mp.getOrDefault("cde", 0) + 1);
System.out.printf("%d\n", mp.get("cde"));
//Map遍历的方法
for(Map.Entry<String, Integer> t : mp.entrySet())
{
System.out.printf("%s %d\n", t.getKey(), t.getValue());
}
}
}