一、单链表 —— 模板题 AcWing 826. 单链表
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static final int N = 100010;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
MySingleLinkedList mySingleLinkedList = new MySingleLinkedList();
int m = in.nextInt();
while (m-- > 0) {
String sa = in.next();
char op = sa.charAt(0);
if (op == 'H') {
int x = in.nextInt();
mySingleLinkedList.addHead(x);
} else if (op == 'D') {
int k = in.nextInt();
if (k == 0) {
mySingleLinkedList.removeHead();
} else {
mySingleLinkedList.remove(k - 1);
}
} else if (op == 'I') {
int k = in.nextInt();
int x = in.nextInt();
mySingleLinkedList.add(k - 1, x);
} else {
throw new RuntimeException();
}
}
mySingleLinkedList.print();
}
private static class MySingleLinkedList {
private static int head;
private static final int[] val = new int[N];
private static final int[] next = new int[N];
private static int index;
/**
* 初始化单链表
*/
public MySingleLinkedList() {
head = -1;
index = 0;
Arrays.fill(next, -1);
}
/**
* 插入头节点
*
* @param x 插入的值
*/
private void addHead(int x) {
// 将插入的值x赋值给idx位置的数组val
val[index] = x;
// 将原来的head赋值给idx位置的数组next
next[index] = head;
// 将idx位置赋值给head，然后idx++
head = index++;
}
/**
* 插入
*
* @param k 位置
* @param x 插入的值
*/
private void add(int k, int x) {
// 将插入的值x赋值给idx位置的数组val
val[index] = x;
// 将原来的next[k]赋值给idx位置的数组next
next[index] = next[k];
// 将idx位置赋值给next[k]，然后idx++
next[k] = index++;
}
/**
* 删除头节点
*/
private void removeHead() {
// 将原来的next[head]赋值给head，头节点指向原来头节点的下一位
head = next[head];
}
/**
* 删除
*
* @param k 位置
*/
private void remove(int k) {
// 将原来的next[k]的next赋值给next[k]，k位置的下一位指向k位置的下一位的下一位
next[k] = next[next[k]];
}
/**
* 输出
*/
private void print() {
// 从头街迪阿尼开始遍历，如果当前位置不是-1，则继续遍历next[i]
for (int i = head; i != -1; i = next[i]) {
System.out.print(val[i] + " ");
}
}
}
}
二、双链表 —— 模板题 AcWing 827. 双链表
import java.util.Objects;
import java.util.Scanner;
public class Main {
private static final int N = 100010;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int m = in.nextInt();
MyDoubleLinkedList myDoubleLinkedList = new MyDoubleLinkedList();
while (m-- > 0) {
String op = in.next();
if (Objects.equals(op, "L")) {
int x = in.nextInt();
myDoubleLinkedList.insert(0, x);
} else if (Objects.equals(op, "R")) {
int x = in.nextInt();
myDoubleLinkedList.insert(myDoubleLinkedList.getLeft(1), x);
} else if (Objects.equals(op, "D")) {
int k = in.nextInt();
myDoubleLinkedList.remove(k + 1);
} else if (Objects.equals(op, "IL")) {
int k = in.nextInt();
int x = in.nextInt();
myDoubleLinkedList.insert(myDoubleLinkedList.getLeft(k + 1), x);
} else if (Objects.equals(op, "IR")) {
int k = in.nextInt();
int x = in.nextInt();
myDoubleLinkedList.insert(k + 1, x);
}
}
myDoubleLinkedList.print();
}
private static class MyDoubleLinkedList {
private static final int[] val = new int[N];
private static final int[] left = new int[N];
private static final int[] right = new int[N];
private static int index;
/**
* 初始化双链表
*/
public MyDoubleLinkedList() {
// left和right作为起点和终点
left[1] = 0;
right[0] = 1;
index = 2;
}
/**
* 插入
*
* @param k 位置
* @param x 插入的值
*/
private void insert(int k, int x) {
// 将插入的值x赋值给idx位置的数组val
val[index] = x;
// 维护双链表左索引
left[index] = k;
// 维护双链表右索引（原来k位置的右索引）
right[index] = right[k];
// 维护原来k位置的右索引的左索引
left[right[k]] = index;
// 维护原来k位置的右索引
right[k] = index;
index++;
}
/**
* 删除
*
* @param k 位置
*/
private void remove(int k) {
// 将k位置的右索引的左索引
left[right[k]] = left[k];
right[left[k]] = right[k];
}
private void print() {
for (int i = right[0]; i != 1; i = right[i]) {
System.out.print(val[i] + " ");
}
}
private Integer getLeft(int k) {
return left[k];
}
}
}
三、栈 —— 模板题 AcWing 828. 模拟栈
static class MyStack {
private final int[] st;
private int tt;
public MyStack() {
int n = 100010;
st = new int[n];
tt = 0;
}
private void push(int x) {
st[++tt] = x;
}
private void pop() {
tt--;
}
private boolean isEmpty() {
return tt <= 0;
}
private int peek() {
return st[tt];
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
MyStack mStack = new MyStack();
int m = in.nextInt();
while (m-- > 0) {
String op = in.next();
switch (op) {
case "push":
int x = in.nextInt();
mStack.push(x);
break;
case "pop":
mStack.pop();
break;
case "empty":
boolean isEmpty = mStack.isEmpty();
if (isEmpty) {
System.out.println("YES");
} else {
System.out.println("NO");
}
break;
case "query":
int query = mStack.peek();
System.out.println(query);
break;
default:
throw new RuntimeException();
}
}
}
static class MyStack {
private final int[] st;
private int tt;
public MyStack() {
int n = 100010;
st = new int[n];
tt = 0;
}
private void push(int x) {
st[++tt] = x;
}
private void pop() {
tt--;
}
private boolean isEmpty() {
return tt <= 0;
}
private int peek() {
return st[tt];
}
}
}
四、队列 —— 模板题 AcWing 829. 模拟队列
static class MyQueue {
private final int[] q;
private int hh;
private int tt;
public MyQueue() {
int n = 1000010;
q = new int[n];
hh = 0;
tt = -1;
}
private void offerLast(int x) {
q[++tt] = x;
}
private void pollFirst() {
hh++;
}
private void pollLast() {
tt--;
}
private boolean isEmpty() {
return hh > tt;
}
private int peekFirst() {
return q[hh];
}
private int peekLast() {
return q[tt];
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
MyQueue myQueue = new MyQueue();
int m = in.nextInt();
while (m-- > 0) {
String op = in.next();
switch (op) {
case "push":
int x = in.nextInt();
myQueue.offerLast(x);
break;
case "pop":
myQueue.pollFirst();
break;
case "empty":
boolean isEmpty = myQueue.isEmpty();
if (isEmpty) {
System.out.println("YES");
} else {
System.out.println("NO");
}
break;
case "query":
int query = myQueue.peekFirst();
System.out.println(query);
break;
default:
throw new RuntimeException();
}
}
}
static class MyQueue {
private final int[] q;
private int hh;
private int tt;
public MyQueue() {
int n = 1000010;
q = new int[n];
hh = 0;
tt = -1;
}
private void offerLast(int x) {
q[++tt] = x;
}
private void pollFirst() {
hh++;
}
private void pollLast() {
tt--;
}
private boolean isEmpty() {
return hh > tt;
}
private int peekFirst() {
return q[hh];
}
private int peekLast() {
return q[tt];
}
}
}
五、单调栈 —— 模板题 AcWing 830. 单调栈
MyStack myStack = new MyStack();
for (int i = 0; i < n; i++) {
int x = in.nextInt();
while (!myStack.empty() && myStack.query() >= x) {
myStack.pop();
}
// ...
myStack.push(x);
}
5.1 模拟栈
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
MyStack myStack = new MyStack();
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
int x = in.nextInt();
while (!myStack.isEmpty() && myStack.peek() >= x) {
myStack.pop();
}
if (myStack.isEmpty()) {
System.out.print("-1 ");
} else {
System.out.print(myStack.peek() + " ");
}
myStack.push(x);
}
}
static class MyStack {
private final int[] st;
private int tt;
public MyStack() {
int n = 100010;
st = new int[n];
tt = 0;
}
private void push(int x) {
st[++tt] = x;
}
private void pop() {
tt--;
}
private boolean isEmpty() {
return tt <= 0;
}
private int peek() {
return st[tt];
}
}
}
5.2 Java 容器
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Deque<Integer> stack = new ArrayDeque<>();
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
int x = in.nextInt();
while (!stack.isEmpty() && stack.peek() >= x) {
stack.pop();
}
if (stack.isEmpty()) {
System.out.print("-1 ");
} else {
System.out.print(stack.peek() + " ");
}
stack.push(x);
}
}
}
不用 Stack 至少有以下两点原因
1、从性能上来说应该使用 Deque 代替 Stack。
Stack 和 Vector 都是线程安全的，其实多数情况下并不需要做到线程安全，因此没有必要使用 Stack。毕竟保证线程安全需要上锁，有额外的系统开销。
2、Stack 从 Vector 继承是个历史遗留问题，JDK 官方已建议优先使用 Deque 的实现类来代替 Stack。
Stack 从 Vector 继承的一个副作用是，暴露了 set/get 方法，可以进行随机位置的访问，这与 Stack 只能从尾巴上进行增减的本意相悖。
此外，Deque 在转成 ArrayList 或者 stream 的时候保持了“后进先出”的语义，而 Stack 因为是从 Vector 继承，没有这个语义。
六、单调队列 —— 模板题 AcWing 154. 滑动窗口
MyQueue myQueue = new MyQueue();
for (int i = 0; i < n; i++) {
while (!myQueue.isEmpty() && myQueue.peekFirst() < i - k + 1) {
myQueue.pollFirst();
}
while (!myQueue.isEmpty() && arr[myQueue.peekLast()] >= arr[i]) {
myQueue.pollLast();
}
myQueue.offerLast(i);
}
6.1 模拟队列
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
// 存下标！！！
MyQueue myQueue = new MyQueue();
String[] sa = in.readLine().split(" ");
int n = Integer.parseInt(sa[0]);
int k = Integer.parseInt(sa[1]);
sa = in.readLine().split(" ");
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(sa[i]);
}
for (int i = 0; i < n; i++) {
while (!myQueue.isEmpty() && myQueue.peekFirst() < i - k + 1) {
myQueue.pollFirst();
}
while (!myQueue.isEmpty() && arr[myQueue.peekLast()] >= arr[i]) {
myQueue.pollLast();
}
myQueue.offerLast(i);
if (i - k + 1 >= 0) {
System.out.print(arr[myQueue.peekFirst()] + " ");
}
}
System.out.println();
// 清空队列
myQueue = new MyQueue();
for (int i = 0; i < n; i++) {
while (!myQueue.isEmpty() && myQueue.peekFirst() < i - k + 1) {
myQueue.pollFirst();
}
while (!myQueue.isEmpty() && arr[myQueue.peekLast()] <= arr[i]) {
myQueue.pollLast();
}
myQueue.offerLast(i);
if (i - k + 1 >= 0) {
System.out.print(arr[myQueue.peekFirst()] + " ");
}
}
in.close();
}
static class MyQueue {
private final int[] q;
private int hh;
private int tt;
public MyQueue() {
int n = 1000010;
q = new int[n];
hh = 0;
tt = -1;
}
private void offerLast(int x) {
q[++tt] = x;
}
private void pollFirst() {
hh++;
}
private void pollLast() {
tt--;
}
private boolean isEmpty() {
return hh > tt;
}
private int peekFirst() {
return q[hh];
}
private int peekLast() {
return q[tt];
}
}
}
6.2 Java 容器
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
// 存下标！！！
Deque<Integer> myQueue = new ArrayDeque<>();
String[] sa = in.readLine().split(" ");
int n = Integer.parseInt(sa[0]);
int k = Integer.parseInt(sa[1]);
sa = in.readLine().split(" ");
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(sa[i]);
}
for (int i = 0; i < n; i++) {
while (!myQueue.isEmpty() && myQueue.peekFirst() < i - k + 1) {
myQueue.pollFirst();
}
while (!myQueue.isEmpty() && arr[myQueue.peekLast()] >= arr[i]) {
myQueue.pollLast();
}
myQueue.offerLast(i);
if (i - k + 1 >= 0) {
System.out.print(arr[myQueue.peekFirst()] + " ");
}
}
System.out.println();
// 清空队列
myQueue.clear();
for (int i = 0; i < n; i++) {
while (!myQueue.isEmpty() && myQueue.peekFirst() < i - k + 1) {
myQueue.pollFirst();
}
while (!myQueue.isEmpty() && arr[myQueue.peekLast()] <= arr[i]) {
myQueue.pollLast();
}
myQueue.offerLast(i);
if (i - k + 1 >= 0) {
System.out.print(arr[myQueue.peekFirst()] + " ");
}
}
in.close();
}
}
七、KMP —— 模板题 AcWing 831. KMP 字符串
private static void kmp(char[] p, int n, char[] s, int m) throws IOException {
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 2, j = 0; i <= n; i++) {
while (j > 0 && p[i] != p[j + 1]) {
j = ne[j];
}
if (p[i] == p[j + 1]) {
j++;
}
ne[i] = j;
}
for (int i = 1, j = 0; i <= m; i++) {
while (j > 0 && s[i] != p[j + 1]) {
j = ne[j];
}
if (s[i] == p[j + 1]) {
j++;
}
if (j == n) {
out.write(i - n + " ");
j = ne[j];
}
}
out.flush();
out.close();
}
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
private static final int N = 1000010;
private static final int[] ne = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
String sa = in.readLine();
char[] p = new char[n + 5];
for (int i = 1; i <= n; i++) {
p[i] = sa.charAt(i - 1);
}
int m = Integer.parseInt(in.readLine());
sa = in.readLine();
char[] s = new char[m + 5];
for (int i = 1; i <= m; i++) {
s[i] = sa.charAt(i - 1);
}
kmp(p, n, s, m);
in.close();
}
private static void kmp(char[] p, int n, char[] s, int m) throws IOException {
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 2, j = 0; i <= n; i++) {
while (j > 0 && p[i] != p[j + 1]) {
j = ne[j];
}
if (p[i] == p[j + 1]) {
j++;
}
ne[i] = j;
}
for (int i = 1, j = 0; i <= m; i++) {
while (j > 0 && s[i] != p[j + 1]) {
j = ne[j];
}
if (s[i] == p[j + 1]) {
j++;
}
if (j == n) {
out.write(i - n + " ");
j = ne[j];
}
}
out.flush();
out.close();
}
}
八、Trie —— 模板题 AcWing 835. Trie 字符串统计
编号为 point 的节点指向了编号为 v 的节点，边对应了字母 u，反映到 son 数组中就是：son[point][u] = v
比如
son[0][0] = 1 // 即son[0][a] = 1
son[1][0] = 2 // 即son[1][a] = 2
son[2][2] = 3 // 即son[2][c] = 3
son[3][3] = 4 // 即son[3][d] = 4
son[2][1] = 5 // 即son[2][b] = 5
那么字符串就是 aacdb
private static final int N = 100010;
private static final int[][] son = new int[N][26];
private static final int[] cnt = new int[N];
private static int idx = 0;
/**
* 将字符串o插入到trie树中
*
* @param p 字符串
*/
private static void insert(String p) {
// 业务异常判断
if (p == null || p.isEmpty()) {
return;
}
// 指针，从根节点到尾节点节点，跟随o的遍历而变化
int point = 0;
for (int i = 0; i < p.length(); i++) {
// u是当前遍历到的字符的int值
int u = p.charAt(i) - 'a';
// son数组两个维度分别是：当前遍历到的位置，正在匹配的字符
// 如果匹配不到，则创建该节点，通过全局变量idx
if (son[point][u] == 0) {
// idx比较难以理解，可以理解为一种uuid（通用唯一识别码）
son[point][u] = ++idx;
}
// if的else分支即，son[point][u] ！= 0，那么即可以找到下一节点
// 指针移动到下一个待匹配的位置
point = son[point][u];
}
// 将尾指针的cnt记录++
cnt[point]++;
}
/**
* 查找字符串o在trie树中出现的次数
*
* @param p 字符串
* @return 在trie树中出现的次数
*/
private static int query(String p) {
int point = 0;
for (int i = 0; i < p.length(); i++) {
int u = p.charAt(i) - 'a';
if (son[point][u] == 0) {
// 与构建树的区别在于，如果没有该节点，则认为出现次数为0
return 0;
}
point = son[point][u];
}
// 通过cnt查找出现的次数
return cnt[point];
}
import java.util.Scanner;
public class Main {
private static final int N = 100010;
private static final int[][] son = new int[N][26];
private static final int[] cnt = new int[N];
private static int idx = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
// 注意换行符，需要空置
in.nextLine();
while (n-- > 0) {
String op = in.nextLine();
String[] opArray = op.split(" ");
String o = opArray[0];
String p = opArray[1];
if (o.equals("I")) {
insert(p);
} else {
System.out.println(query(p));
} else {
throw new RuntimeException("参数异常");
}
}
}
/**
* 将字符串o插入到trie树中
*
* @param p 字符串
*/private static void insert(String p) {
// 业务异常判断
if (p == null || p.isEmpty()) {
return;
}
// 指针，从根节点到尾节点节点，跟随o的遍历而变化
int point = 0;
for (int i = 0; i < p.length(); i++) {
// u是当前遍历到的字符的int值
int u = p.charAt(i) - 'a';
// son数组两个维度分别是：当前遍历到的位置，正在匹配的字符
// 如果匹配不到，则创建该节点，通过全局变量idx
if (son[point][u] == 0) {
// idx比较难以理解，可以理解为一种uuid（通用唯一识别码）
son[point][u] = ++idx;
}
// if的else分支即，son[point][u] ！= 0，那么即可以找到下一节点
// 指针移动到下一个待匹配的位置
point = son[point][u];
}
// 将尾指针的cnt记录++
cnt[point]++;
}
/**
* 查找字符串o在trie树中出现的次数
*
* @param p 字符串
* @return 在trie树中出现的次数
*/
private static int query(String p) {
int point = 0;
for (int i = 0; i < p.length(); i++) {
int u = p.charAt(i) - 'a';
if (son[point][u] == 0) {
// 与构建树的区别在于，如果没有该节点，则认为出现次数为0
return 0;
}
point = son[point][u];
}
// 通过cnt查找出现的次数
return cnt[point];
}
}
九、并查集 —— 模板题 AcWing 836. 合并集合
private static final int[] parent = new int[N];
/**
* 将集合合并 如果两个数已经在同一个集合中，则忽略这个操作；
*
* @param a a集合
* @param b b集合
*/
private static void merge(int a, int b) {
int aParent = find(a);
int bParent = find(b);
// 如果两个数已经在同一个集合中，则忽略这个操作；
if (aParent == bParent) {
return;
}
// 将a集合的根节点的父节点设置成b集合的根节点
parent[aParent] = bParent;
}
/**
* 寻找x集合的父节点
*
* @param x x集合
* @return x集合的父节点
*/
private static int find(int x) {
// 根节点的父节点等于根节点本身的为根节点
// 如果当前不是父节点，则递归查询父节点
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
// // 迭代写法
// while (parent[x] != x) {
// x = parent[x];
// }
// 返回父节点
return parent[x];
}
import java.util.Scanner;
public class Main {
private static final int N = 100010;
private static final int[] parent = new int[N];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
// 初始化数组
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
// 注意换行符，需要空置
in.nextLine();
while (m-- > 0) {
String[] op = in.nextLine().split(" ");
String o = op[0];
int a = Integer.parseInt(op[1]);
int b = Integer.parseInt(op[2]);
if (o.equals("M")) {
merge(a, b);
} else if (o.equals("Q")) {
if (find(a) == find(b)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
} else {
throw new RuntimeException("参数异常");
}
}
}
/**
* 将集合合并 如果两个数已经在同一个集合中，则忽略这个操作；
*
* @param a a集合
* @param b b集合
*/
private static void merge(int a, int b) {
int aParent = find(a);
int bParent = find(b);
// 如果两个数已经在同一个集合中，则忽略这个操作；
if (aParent == bParent) {
return;
}
// 将a集合的根节点的父节点设置成b集合的根节点
parent[aParent] = bParent;
}
/**
* 寻找x集合的父节点
*
* @param x x集合
* @return x集合的父节点
*/
private static int find(int x) {
// 根节点的父节点等于根节点本身的为根节点
// 如果当前不是父节点，则递归查询父节点
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
// // 迭代写法
// while (parent[x] != x) {
// x = parent[x];
// }
// 返回父节点
return parent[x];
}
}
十、堆 —— 模板题 AcWing 838. 堆排序 , AcWing 839. 模拟堆
import java.util.Scanner;
public class Main {
private static final int N = 100010;
private static final int[] heap = new int[N];
private static int size = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
for (int i = 1; i <= n; i++) {
heap[i] = in.nextInt();
}
// 记录当前堆的大小
size = n;
// 从n/2的位置开始，直到1的位置结束，初始化堆
// 堆是一个完全二叉树，所有非叶子节点的格式等于叶子节点的数量
// 因此可以优化，最下面一排没有子节点的节点不用参与
for (int i = n / 2; i >= 0; i--) {
down(i);
}
while (m-- > 0) {
// 每次输出最小根节点
System.out.print(heap[1] + " ");
// 利用尾节点插入头节点
heap[1] = heap[size];
// 删掉尾节点
size--;
// 重新调整堆
down(1);
}
}
/**
* 重新调整堆
*
* @param u 下标
*/
private static void down(int u) {
// 待调整的下表，也是分身变量
int temp = u;
// 如果左子节点合法，并且左子节点小于当前节点，则需要调整堆
if (u * 2 <= size && heap[u * 2] < heap[temp]) {
// 利用分身变量记录需要调整的堆位置
temp = u * 2;
}
// 如果右子节点合法，并且右子节点小于当前节点，则需要调整堆
if (u * 2 + 1 <= size && heap[u * 2 + 1] < heap[temp]) {
// 利用分身变量记录需要调整的堆位置
temp = u * 2 + 1;
}
// 如果需要调整
if (temp != u) {
// 交换位置
swap(u, temp);
// 重新调整堆
down(temp);
}
}
/**
* 交换方法
*
* @param x 下标
* @param y 下标
*/
private static void swap(int x, int y) {
int temp = heap[x];
heap[x] = heap[y];
heap[y] = temp;
}
}
import java.util.Scanner;
public class Main {
private static final int N = 100010;
private static final int[] heap = new int[N];
/**
* point heap，ph数组即point heap数组，ph[i] = j记录的是第i次插入的值下标j
*/ private static final int[] ph = new int[N];
/**
* heap point，hp数组即heap point数组，hp[j] = i记录的是值下标j是第i次插入的
*/
private static final int[] hp = new int[N];
private static int size = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = 0;
while (n-- > 0) {
String op = in.next();
/**
* I x，插入一个数 x；size++;h[size] = x;up(size);
* PM，输出当前集合中的最小值； h[1]
* DM，删除当前集合中的最小值（数据保证此时的最小值唯一）； h[1] = h[size];size--;down(1);
* D k，删除第 k 个插入的数； h[k] = h[size];size--;down(k),up(k)
* C k x，修改第 k 个插入的数，将其变为 x；h[k] = x,down(k) ,up(k);
*/
if (op.equals("I")) {
int x = in.nextInt();
size++;
// 记录当前是第几次插入
m++;
// 维护ph和hp数组，注意是下标
ph[m] = size;
hp[size] = m;
// 尾插法
heap[size] = x;
// 尾节点发生变化，，因此up(size)
up(size);
} else if (op.equals("PM")) {
// 最小根
System.out.println(heap[1]);
} else if (op.equals("DM")) {
// 头尾交换
heapSwap(1, size);
// 去掉尾节点
size--;
// 头节点发生变化，因此down(1)
down(1);
} else if (op.equals("D")) {
int k = in.nextInt();
// 查找第k次插入的值下标
k = ph[k];
// 和尾节点交换
heapSwap(k, size);
size--;
up(k);
down(k);
} else if (op.equals("C")) {
int k = in.nextInt();
int x = in.nextInt();
// 查找第k次插入的值下标
k = ph[k];
// 修改值
heap[k] = x;
up(k);
down(k);
}
}
}
/**
* 重新调整堆
*
* @param u 下标
*/
private static void up(int u) {
// 父节点合法，并且父节点大于当前节点
while ((u / 2 > 0) && (heap[u] < heap[u / 2])) {
// 交换当前节点和父节点
heapSwap(u, u / 2);
// 当前节点变为父节点
u /= 2;
}
}
/**
* 重新调整堆
*
* @param u 下标
*/
private static void down(int u) {
// 待调整的下表，也是分身变量
int temp = u;
// 如果左子节点合法，并且左子节点小于当前节点，则需要调整堆
if (u * 2 <= size && heap[u * 2] < heap[temp]) {
// 利用分身变量记录需要调整的堆位置
temp = u * 2;
}
// 如果右子节点合法，并且右子节点小于当前节点，则需要调整堆
if (u * 2 + 1 <= size && heap[u * 2 + 1] < heap[temp]) {
// 利用分身变量记录需要调整的堆位置
temp = u * 2 + 1;
}
// 如果需要调整
if (temp != u) {
// 交换位置
heapSwap(u, temp);
// 重新调整堆
down(temp);
}
}
/**
* 堆交换方法：1、交换ph数组，2、狡猾hp数组，3、交换heap数组
*
* @param x 下标
* @param y 下标
*/
private static void heapSwap(int x, int y) {
// 交换ph数组的位置
// ph数组即point heap数组，ph[i] = j记录的是第i次插入的值j下标
swap(ph, hp[x], hp[y]);
// 交换hp数组的位置
// hp数组即heap point数组，hp[j] = i记录的是值j下标是第i次插入的
swap(hp, x, y);
// 交换heap数组的位置
swap(heap, x, y);
}
/**
* 交换方法
*
* @param arr 数组
* @param x 下标
* @param y 下标
*/
private static void swap(int[] arr, int x, int y) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}
十一、一般哈希 —— 模板题 AcWing 840. 模拟散列表
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static final int N = 100010;
private static final int[] h = new int[N];
private static final int[] e = new int[N];
private static final int[] next = new int[N];
private static int idx = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine();
Arrays.fill(h, Integer.MAX_VALUE);
while (n-- > 0) {
String op = in.nextLine();
String[] opArray = op.split(" ");
String o = opArray[0];
Integer p = Integer.valueOf(opArray[1]);
if (o.equals("I")) {
insert(p);
} else if (o.equals("Q")) {
if (query(p)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
} else {
throw new RuntimeException();
}
}
}
/**
* 生成质数
*
* @param startNumber 起始数字
* @return 质数
*/
private static Integer generatePrime(Integer startNumber) {
for (int i = startNumber; ; i++) {
boolean flag = true;
for (int j = 2; j <= Math.sqrt(i); j++) {
if (i % j == 0) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
}
/**
* 插入x到哈希表中
*
* @param x 插入的值
*/
private static void insert(Integer x) {
int prime = generatePrime(100000);
// 由于负数求模也是负数，因此加上N
int k = (x % prime + prime) % prime;
// 头插法
e[idx] = x;
next[idx] = h[k];
h[k] = idx++;
}
/**
* 到哈希表中查询x是否存在
*
* @param x 查询的值
* @return 是否存在
*/
private static boolean query(Integer x) {
int prime = generatePrime(100000);
int k = (x % prime + prime) % prime;
for (int i = h[k]; i != Integer.MAX_VALUE; i = next[i]) {
if (e[i] == x) {
return true;
}
}
return false;
}
}
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static final int N = 200010;
private static final int[] h = new int[N];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine();
Arrays.fill(h, Integer.MAX_VALUE);
while (n-- > 0) {
String op = in.nextLine();
String[] opArray = op.split(" ");
String o = opArray[0];
Integer p = Integer.valueOf(opArray[1]);
if (o.equals("I")) {
Integer k = query(p);
h[k] = p;
} else if (o.equals("Q")) {
Integer k = query(p);
if (h[k] != Integer.MAX_VALUE && h[k] == p) {
System.out.println("Yes");
} else {
System.out.println("No");
}
} else {
throw new RuntimeException();
}
}
}
/**
* 生成质数
*
* @param startNumber 起始数字
* @return 质数
*/
private static Integer generatePrime(Integer startNumber) {
for (int i = startNumber; ; i++) {
boolean flag = true;
for (int j = 2; j <= Math.sqrt(i); j++) {
if (i % j == 0) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
}
/**
* 到哈希表中查询x是否存在
*
* @param x 查询的值
* @return 是否存在
*/
private static Integer query(Integer x) {
int prime = generatePrime(200000);
int k = (x % prime + prime) % prime;
while (h[k] != Integer.MAX_VALUE && h[k] != x) {
k++;
if (k == prime) {
k = 0;
}
}
return k;
}
}
好棒！我顶
for (int i = n / 2; i >= 0; i–) {
down(i);
}
堆排序这里为什么是>= 0啊
佬 能不能写一个 Java里面类似于 C++ STL的常用模板啊 求求了
cpp的建议看y总的哈= =
我就是Java 看b站一些集合框架
类的视频看不来 有些迷茫
周末我研究一哈，最近也在整理这块=-=
收到 太感谢啦呜呜
nb
:)