文章目录
一、链表和邻接表
1 链表
这里我们不采用常用的结构体加指针的方式来实现链表，因为这样每个结点都要new一下,常见笔试题中链表结点个数都是1e5~1e6级别的，光new这些结点就足以超时了。
所以我们采用数组来模拟链表的方式。
单链表的主要用途是可以实现邻接表这种结构，邻接表常用来存储图和树。
I 数组模拟单链表
e[N]来存储每个结点的值，ne[N]来存储每个结点的next指针值,如下例：
例题：
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
/*e[i]储存下标为i的结点的值 ne[i]储存下标为i的结点的next指针*/
int e[N], ne[N];
/*head存储的是哨兵头结点指向的下标
idx表示下一个可用的结点的下标
*/
int head;
int idx;
//初始化
void Init()
{
head = -1;
idx = 0;
}
//在head后面插入值为x的结点
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
//在下标为k的结点后面插入值为x的节点
void add(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
// 将下标是k的点后面那个点删掉
void remove(int k)
{
/*直接把k的next指针指向ne[k]的next就行*/
/*直接当这个点不存在就行 算法题中不要管内存泄漏*/
ne[k] = ne[ne[k]];
}
int main()
{
Init();
int m;
cin >> m;
char op;
int k, x;
while (m--)
{
cin >> op;
if (op == 'H')
{
cin >> x;
add_to_head(x);
}
else if (op == 'D')
{
cin >> k;
// 如果是头结点 直接让head的next指向head指向的结点的ne 即head = ne[head];
if (k == 0) head = ne[head];
else
{
/*第k个插入的数下标为k - 1*/
remove(k - 1);
}
}
else
{
cin >> k >> x;
add(k - 1, x);
}
//cout << op << ' ';
}
for (int i = head; i != -1; i = ne[i])
{
cout << e[i] << ' ';
}
return 0;
}
II 数组模拟双链表
l[i]储存下标为i结点的前继，r[i]储存下标为i结点的后继，e[i]储存下标为i结点的值。
例题：
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int r[N];// 后继
int l[N];// 前继
int e[N];// 值
int idx;//下一个空闲的结点
void Init()
{
// 0作为头结点起始
// 1作为右边界终止
r[0] = 1;
l[1] = 0;
idx = 2;
}
// 在下标为k的结点右边插入值为x的结点
void add(int k, int x)
{
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx++;
}
// 在k的左边插入就等价于add(l[k], x)
// 删除下标为k的点
void remove(int k)
{
l[r[k]] = l[k];
r[l[k]] = r[k];
}
int main()
{
Init();
int m;
cin >> m;
char op1, op2;
int k, x;
while (m--)
{
cin >> op1;
if (op1 == 'L')
{
cin >> x;
add(0, x);
}
else if (op1 == 'R')
{
cin >> x;
add(l[1], x);
}
else if (op1 == 'D')
{
cin >> k;
// 第一个插入的结点下标是2
remove(k + 1);
}
else if (op1 == 'I')
{
cin >> op2;
if (op2 == 'L')
{
cin >> k >> x;
add(l[k + 1], x);
}
else
{
cin >> k >> x;
add(k + 1, x);
}
}
}
for (int i = r[0]; i != 1; i = r[i])
{
cout << e[i] << ' ';
}
return 0;
}
邻接表就是开了很多个单链表放到一起，相当于每个与这个点相连的点都存在这个链表中，常用于树和图的存储。
二、栈和队列
模拟栈：
#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 10;
int Stack[N];
int top;
void Init()
{
top = 0;
}
void Push(int x)
{
Stack[top++] = x;
}
int Top()
{
return Stack[top - 1];
}
bool empty()
{
return top == 0;
}
void Pop()
{
--top;
}
int main()
{
int m;
cin >> m;
int x;
string op;
while (m--)
{
cin >> op;
if (op == "push")
{
cin >> x;
Push(x);
}
else if (op == "pop")
{
Pop();
}
else if (op == "empty")
{
if (empty()) cout << "YES" << endl;
else cout << "NO" << endl;
}
else
{
cout << Top() << endl;
}
}
return 0;
}
模拟队列：
#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 10;
/*front表示队头 rear表示队尾 在队尾插入 出队列则front++*/
int Queue[N];
int front;
int rear;
void Init()
{
front = 0;
rear = 0;
}
void Push(int x)
{
Queue[rear++] = x;
}
void Pop()
{
front++;
}
bool empty()
{
return rear <= front;
}
int Front()
{
return Queue[front];
}
int main()
{
int m;
cin >> m;
string op;
int x;
while (m--)
{
cin >> op;
if (op == "push")
{
cin >> x;
Push(x);
}
else if (op == "pop")
{
Pop();
}
else if (op == "empty")
{
cout << (empty() ? "YES" : "NO") << endl;
}
else
{
cout << Front() << endl;
}
}
return 0;
}
1 单调栈和单调队列
I 单调栈
模型题：给定一个序列，求一下在每个数左(右)边离它最近的比它小(大)的数。
考虑方式与双指针算法类似，先考虑暴力算法，然后再去挖掘一些性质去优化时间复杂度。
传统暴力做法就是对每个下标往前遍历，其中隐含的可以优化的点如图：
因此在栈中，若ax >= ay && x < y,则ax就可以被删掉，所以栈中的序列一定是个单调的序列。
代码：
#include <iostream>
#include <stack>
using namespace std;
int main()
{
/*栈内维护一个单调递增元素的序列
因为若a[x] >= a[y] 且x < y
那么要么就输出a[y] 要么输出a[y]之前的元素 若a[y]不满足性质 即
a[y] >= a[i],那么a[x]也一定>= a[i]，所以只能输出a[x]前面的元素
a[x]怎么也不可能输出*/
stack<int> st;
int n;
cin >> n;
int x;
for (int i = 0; i < n; ++i)
{
cin >> x;
while (!st.empty() && st.top() >= x)
{
st.pop();
}
if (st.empty()) cout << -1 << ' ';
else cout << st.top() << ' ';
st.push(x);
}
return 0;
}
把scanf和printf来替换cin cout后，速度确实有提升：
时间复杂度：对于每个元素，最多进栈一次出栈一次，所以时间复杂度是O(n).
单调栈的几个LeetCode例题：
// 解法1
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums)
{
stack<int> st;
int n = nums.size();
vector<int> ret(n, -1);
/*因为是循环数组 所以拉长取模*/
for (int i = 2 * n - 2; i >= 0; --i)
{
/*倒着走 维护一个元素单调递增的栈*/
while (!st.empty() && st.top() <= nums[i % n]) st.pop();
if (!st.empty()) ret[i % n] = st.top();
st.push(nums[i % n]);
}
return ret;
}
};
// 解法2
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums)
{
/*单调栈内存一组尚未解决计算出下一个最大元素位置的递增下标
对遍历到的每一个元素 检查栈顶元素对应的元素值是否小于当前元素值
若小于 则让ret[st.top()] = nums[i] 然后pop掉去看前一个未解决的问题
否则 让当前元素下标i入栈
*/
int n = nums.size();
vector<int> ret(n, -1);
stack<int> st;
for (int i = 0; i < 2 * n - 1 ; ++i)
{
while (!st.empty() && nums[st.top()] < nums[i % n])
{
ret[st.top()] = nums[i % n];
st.pop();
}
st.push(i % n);
}
return ret;
}
};
class Solution {
public:
vector<int> nextLargerNodes(ListNode* head)
{
auto cur = head;
int n = 0;
while (cur != nullptr)
{
cur = cur->next;
++n;
}
vector<int> ret(n, 0);
/*栈内维护一个单调递增的下标序列 表示计算出对应ret[i]的下标i*/
stack<pair<int, int>> st;/*结点下标 元素值 为了支持随机读取*/
int curidx = 0;
for (cur = head; cur != nullptr; cur = cur->next, ++curidx)
{
/*与数组单调栈类似 尚未栈中尚未解决的点能否通过该点解决*/
while (!st.empty() && st.top().second < cur->val)
{
ret[st.top().first] = cur->val;
st.pop();
}
/*然后把该店入进栈*/
st.push({curidx, cur->val});
}
return ret;
}
};
II 单调队列
最经典的应用就是求一下滑动窗口中的最大值和最小值。
单调队列和单调栈的思考方式相似，先想一个暴力做法，然后把没有用的元素删掉，看此时的队列是否有单调性。
-1也是同理。
相等的可以用新进来的那个相等的数字代表进行输出。
所以存输出最小值的队列是一个严格单调递增的序列。
代码：
#include <iostream>
#include <deque>
using namespace std;
const int N = 1e6 + 10;
int main()
{
int n, k;
cin >> n >> k;
int q[N];
for (int i = 0; i < n; ++i) cin >> q[i];
deque<int> dq1;// 用于输出窗口最小值元素的单调递增序列
deque<int> dq2;// 用于输出窗口最大值元素的单调递减序列
for (int i = 0; i < n; ++i)
{
/*看看队首元素是否出了窗口*/
if (!dq1.empty() && dq1.front() < i - k + 1) dq1.pop_front();
/*维护队列的单调递增
输出最小值时 如果队列队尾的元素大于等于此轮入窗口的q[i]
q[i]是后入窗口的 存在窗口内时间更长
那根本没有那个大元素输出的可能性
*/
/*这里大于等于可以换大于*/
while (!dq1.empty() && q[dq1.back()] >= q[i]) dq1.pop_back();
/*队列中存下标 方便看队首元素是否出界*/
dq1.push_back(i);
if (i + 1 >= k)
{
printf("%d ", q[dq1.front()]);
}
}
printf("\n");
for (int i = 0; i < n; ++i)
{
/*看看队首元素是否出了窗口*/
if (!dq2.empty() && i - k + 1 > dq2.front()) dq2.pop_front();
/*维护队列的单调递减
输出最大值时 如果队列队尾的元素小于等于此轮入窗口的q[i]
q[i]是后入窗口的 存在窗口内时间更长
那根本没有那个小元素输出的可能性*/
/*这里小于等于可以换小于*/
while (!dq2.empty() && q[dq2.back()] <= q[i]) dq2.pop_back();
dq2.push_back(i);
if (i + 1 >= k)
{
printf("%d ", q[dq2.front()]);
}
}
return 0;
}
刷了LeetCode题以后更好的写法：当这次移出窗口的元素是最大值或最小值时，才需要让单调队列的队头出队列。
#include <iostream>
#include <deque>
using namespace std;
const int N = 1e6 + 10;
int main()
{
int n, k;
cin >> n >> k;
int q[N];
for (int i = 0; i < n; ++i) cin >> q[i];
deque<int> q1;
deque<int> q2;
for (int i = 0; i < n; ++i)
{
/*若待移除元素是队头 则让队头出队列*/
if (!q1.empty() && i - k >= 0 && q1.front() == q[i - k]) q1.pop_front();
/*求窗口最小值时，出现在我之前比我大的元素都不可能是最小值*/
/*这里不是以下标来确定排除队首元素的 所以这里大于不能换大于等于*/
while (!q1.empty() && q1.back() > q[i]) q1.pop_back();
q1.push_back(q[i]);
if (i + 1 >= k)
{
cout << q1.front() << ' ';
}
}
cout << endl;
for (int i = 0; i < n; ++i)
{
/*若待移除元素是队头 则让队头出队列*/
if (!q2.empty() && i - k >= 0 && q2.front() == q[i - k]) q2.pop_front();
/*求窗口最大值时，出现在我之前比我小的元素都不可能是最大值*/
/*这里不是以下标来确定排除队首元素的 所以这里小于不能换小于等于*/
while (!q2.empty() && q2.back() < q[i]) q2.pop_back();
q2.push_back(q[i]);
if (i + 1 >= k) cout << q2.front() << ' ';
}
return 0;
}
LeetCode单调队列例题：
class MaxQueue {
public:
MaxQueue()
{
}
int max_value()
{
if (q2.empty()) return -1;
// 返回单调队列q2队首元素
return q2.front();
}
void push_back(int value)
{
q1.push(value);
// 比value小的元素都没机会输出 维护单调递减(非严格)的队列q2
// 每个元素最多出队一次 摊到每个元素平均时间复杂度为O(1)
while (!q2.empty() && q2.back() < value) q2.pop_back();
q2.push_back(value);
}
int pop_front()
{
if (q2.empty()) return -1;
int val = q1.front();
q1.pop();
// 若弹出的元素就是最大元素 则需要把双向队列的队首元素也弹出以保持一直
if (val == q2.front()) q2.pop_front();
return val;
}
private:
queue<int> q1;// 用来存储队列元素以应对pop_front
deque<int> q2;// 作为一个单调递减的队列来O(1)的返回max_value.
};
class Solution {
public:
int longestSubarray(vector<int>& nums, int limit)
{
int n = nums.size();
int ret = 0;
deque<int> q1;// 用于输出最大值单调递减序列 值,下标
deque<int> q2;// 用于输出最小值的单调递增序列 值,下标
/*i表示以j结尾的子数组最左边能到达的位置 它不会往左走 具有单调性
可以使用双指针算法*/
for (int j = 0, i = 0; j < n; ++j)
{
/*比nums[j]小的元素都不可能是最大值*/
while (!q1.empty() && q1.back() < nums[j]) q1.pop_back();
/*比nums[j]大的元素都不可能是最小值*/
while (!q2.empty() && q2.back() > nums[j]) q2.pop_back();
q1.push_back(nums[j]);
q2.push_back(nums[j]);
/*若当前区间[i,j]的最大值减最小值大于limit 则i要往前走且可能移除最大或最小元素*/
while (!q1.empty() && !q2.empty() && q1.front() - q2.front() > limit)
{
/*当前移除的元素如果和队头相等 就把队头移除*/
if (nums[i] == q1.front()) q1.pop_front();
if (nums[i] == q2.front()) q2.pop_front();
i++;
}
ret = max(ret, j - i + 1);
}
return ret;
}
};
三、KMP算法
先想一下暴力做法怎么做。
暴力做法就是两层循环，
// 枚举长串的起点
for (int i = 1; i <= n; ++i)
{
bool flag = true;
for (int l = i, j = 1; j <= m, l <= n; ++j, ++l)
{
if (s[l] != p[j])
{
flag = false;
break;
}
}
if (flag == true)
{
break;
}
}
KMP的思想：
这就是next[i]的含义：以sub[i - 1]为结尾的串和以sub[0]为开头的串相等且串的长度最长，这时以sub[0]为开头的串的结尾的下一个位置的下标。
具体代码。
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
char P[N];// 子串
char S[N];// 长串
int n, m;// 子串长度 长串长度
int ne[N];// next数组
int main()
{
cin >> n >> P >> m >> S;
ne[0] = -1;// 0下标匹配失败回溯到-1
ne[1] = 0;// 1下标匹配失败只能回溯到0
int i = 2, k = 0;// 求解next[i] k储存next[i - 1]
// 求解ne数组
while (i < n)
{
/*P[i - 1]和 P[k]在匹配*/
while (k != -1 && P[i - 1] != P[k]) k = ne[k];
ne[i] = k + 1;
++i;
++k;
}
// 匹配
i = 0;
int j = 0;
while (i < m)
{
/*S[i]和P[j]在匹配*/
while (j != -1 && S[i] != P[j]) j = ne[j];
/*走到这里匹配成功或j到了-1怎么也没法和i匹配
总之这时i需要加1 j需要加1*/
++i;
++j;
/*如果j走到了n 说明P串匹配完成了一次 返回这时的起点 也就是i - j*/
if (j == n)
{
cout << i - j << ' ';
/*为了去寻找下一个匹配完成的成功位置
我们可以看做是在P[n - 1]位置匹配失败
那时的i等于i - 1
j要回溯到j = ne[n - 1]*/
--i;
j = ne[n - 1];
}
}
return 0;
}
储存next[i - 1]
// 求解ne数组
while (i < n)
{
/P[i - 1]和 P[k]在匹配/
while (k != -1 && P[i - 1] != P[k]) k = ne[k];
ne[i] = k + 1;
++i;
++k;
}
// 匹配
i = 0;
int j = 0;
while (i < m)
{
/S[i]和P[j]在匹配/
while (j != -1 && S[i] != P[j]) j = ne[j];
/走到这里匹配成功或j到了-1怎么也没法和i匹配
总之这时i需要加1 j需要加1/
++i;
++j;
/如果j走到了n 说明P串匹配完成了一次 返回这时的起点 也就是i - j/
if (j == n)
{
cout << i - j << ’ ';
/为了去寻找下一个匹配完成的成功位置
我们可以看做是在P[n - 1]位置匹配失败
那时的i等于i - 1
j要回溯到j = ne[n - 1]/
–i;
j = ne[n - 1];
}
}
return 0;
}