记录一些算法模板
MISC
IO 优化 (LeetCode)
int init_io = []{
ios::sync_with_stdio(false);
return 0;
}();
排序
稳定性
- 不稳定: 堆排序、快速排序、希尔排序、直接选择排序
- 稳定: 冒泡排序、直接插入排序、折半插入排序、归并排序
快速排序
上机 ver.
void quick_sort(int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, k = w[l + r >> 1];
while (i < j) {
while (w[++i] < k);
while (k < w[--j]);
if (i < j) swap(w[i], w[j]);
}
quick_sort(l, j);
quick_sort(j + 1, r);
}
单链表 ver.
class Solution {
public:
ListNode* quickSortList(ListNode* head) {
if (!head) return head;
ListNode *l = nullptr, *r = nullptr, *pivot = head;
head = head->next;
while (head) {
auto t = head;
head = head->next;
if (pivot->val < t->val) t->next = r, r = t;
else t->next = l, l = t;
}
l = quickSortList(l);
r = quickSortList(r);
pivot->next = r;
if (l == nullptr) {
return pivot;
} else {
auto ll = l;
while (ll->next) ll = ll->next;
ll->next = pivot;
return l;
}
}
};
希尔排序
可能比快排优, 数据基本有序情况下
O(n ** 1.3)
void shell_sort()
{
for (int d = n / 3; d; d = (d == 2) ? 1 : d / 3) {
for (int start = 0; start < d; start++)
for (int i = start + d; i < n; i += d) {
// 直接插入排序
int t = w[i], j = i;
while (j > start && w[j - d] > t)
w[j] = w[j - d], j -= d;
w[j] = t;
}
}
}
冒泡排序
void bubble_sort()
{
for (int i = 0; i < n - 1; i ++ )
{
bool has_swap = false;
for (int j = n - 1; j > i; --j)
if (w[j - 1] > w[j])
{
swap(w[j - 1], w[j]);
has_swap = true;
}
if (!has_swap) break;
}
}
插入排序
void insert_sort()
{
for (int i = 1; i < n; i ++ ) {
int t = w[i], j = i;
while (j && w[j - 1] > t)
w[j] = w[j - 1], --j;
w[j] = t;
}
}
折半插入
void binary_search_insert_sort() // 折半插入
{
for (int i = 1; i < n; i++) {
if (w[i - 1] <= w[i]) continue;
int t = w[i];
int l = 0, r = i - 1;
while (l < r) {
int mid = l + r >> 2;
if (w[mid] > t) r = mid;
else l = mid + 1;
}
for (int j = i - 1; j >= r; --j)
w[j + 1] = w[j];
w[r] = t;
}
}
归并排序
void merge_sort(int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(l, mid); merge_sort(mid + 1, r);
// Merge two seg
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
q[k++] = (w[i] < w[j]) ? w[i++] : w[j++];
while (i <= mid) q[k++] = w[i++];
while (j <= r) q[k++] = w[j++];
// Copyback
for (int i = 0; i < k; i++)
w[i + l] = q[i];
}
外部排序
- 归并
- 胜者树与败者树
字符串
KMP
AcWing 831
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
const int N = 1e6 + 10;
int ne[N];
char p[N], s[N];
int main()
{
cin >> n >> p + 1 >> m >> s + 1;
for (int i = 2, j = 0; i <= n; 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 <= m; i++)
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) ++j;
if (j == n) cout << i - n << ' ';
}
return 0;
}