Java ACM模式下输入输出
https://blog.csdn.net/weixin_43653890/article/details/124253192
快速排序算法模版
public static void quickSort(int[] q, int l, int r) {if (l >= r) return;// 1. 确定边界int i = l - 1, j = r + 1, x = q[l + r >> 1];while (i < j) {//2. 调整区间do i++; while (q[i] < x);do j--; while (q[j] > x);//swapif (i < j) {int tmp = q[i];q[i] = q[j];q[j] = tmp;}}// 3. 递归左区间quickSort(q, l, j);// 3. 递归右区间quickSort(q, j + 1, r);
}
归并排序算法模版
public static void mergeSort(int[] q, int l, int r) {if (l >= r) return;// 1. 确定分界点int mid = l + r >> 1;// 2. 先递归排序mergeSort(q, l, mid);mergeSort(q, mid + 1, r);// 3. 双指针合并两个区间int[] tmp = new int[r - l + 1];int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r) {if (q[i] <= q[j]) tmp[k++] = q[i++];else tmp[k++] = q[j++];}// 当其中一个有序区间走完时，另一个区间直接填补while (i<=mid) tmp[k++] = q[i++];while (j<=r) tmp[k++] = q[j++];for (i = l, j = 0; i<=r; i++,j++) q[i] = tmp[j];}
二分查找算法模版
模版一
// 区间[l, r]被划分成 [l, mid] 和 [mid+1, r]时使用
int bsearch_1(int l, int r) {while (l < r) {int mid = l + r >> 1;if (check[mid) // check() 判断 mid是否满足性质r = mid; elsel = mid + 1;}return l;
}
模版二
// 区间[l, r]被划分成 [l, mid-1] 和 [mid, r]时使用
int bsearch_2(int l, int r) {while (l < r) {int mid = l + r + 1 >> 1; // 注意if (check[mid) // check() 判断 mid是否满足性质l = mid;elser = mid - 1;}return l;
}
如何选择模板
根据 check(mid)来判断 r和 l的取值范围
根据取值范围选择 mid是否有 + 1操作
mid归于左边, r = mid, mid选择 不 +1
mid归于右边, l = mid, mid选择 +1
位运算
求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n
数据结构
单链表
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;// 初始化
void init()
{head = -1;idx = 0;
}// 在链表头插入一个数a
void insert(int a)
{e[idx] = a, ne[idx] = head, head = idx ++ ;
}// 将头结点删除，需要保证头结点存在
void remove()
{head = ne[head];
}
双链表
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;// 初始化
void init()
{//0是左端点，1是右端点r[0] = 1, l[1] = 0;idx = 2;
}// 在节点a的右边插入一个数x
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];
}
栈
// tt表示栈顶
int stk[N], tt = 0;// 向栈顶插入一个数
stk[ ++ tt] = x;// 从栈顶弹出一个数
tt -- ;// 栈顶的值
stk[tt];// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{}
队列
普通队列
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;// 向队尾插入一个数
q[ ++ tt] = x;// 从队头弹出一个数
hh ++ ;// 队头的值
q[hh];// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{}
循环队列
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;// 队头的值
q[hh];// 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt)
{}
单调栈
常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{while (tt && check(stk[tt], i)) tt -- ;stk[ ++ tt] = i;
}
单调队列
常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口while (hh <= tt && check(q[tt], i)) tt -- ;q[ ++ tt] = i;
}
KMP
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{while (j && 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 <= n; i ++ )
{while (j && s[i] != p[j + 1]) j = ne[j];if (s[i] == p[j + 1]) j ++ ;if (j == m){j = ne[j];// 匹配成功后的逻辑}
}