题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int e[N],ne[N],head,idx;
// e是值域,he是指向下一个数字,head是头指针,idx是到了那个操作数
int n;
void Init()
{
head = -1;// 最开始的时候head的下标要指向-1(链表头结点指向-1)
// head就是一个指针而已,初始化的时候为一,代表里面没有元素,有元素的时候指向第一个值
idx = 0;
//第一个是在一开始的时候,作为链表的下标
//第二在链表进行各种插入,删除等操作的时候,作为一个临时的辅助性的所要操作的元素的下
//标来帮助操作。并且是在每一次插入操作的时候,给插入元素一下标
}
// 插入头结点
void int_to_head(int x)
{
e[idx] = x;
ne[idx] = head;//head作为一个指针指向空节点,现在ne[idx] = head;做这把交椅的人换了
//先在只是做到了第一步,将元素x的指针指向了head原本指向的
head = idx; //x;//head现在表示指向第一个元素了,它不在是空指针了。
idx++;
}
//将x插入到下标为k的点的后面
void add(int k,int x)
{
e[idx] = x;
ne[idx] = ne[k];//让元素x配套的指针,指向它要占位的元素的下一个位置
ne[k] = idx;//让原来元素的指针指向自己,idx向后移动
idx++;
/*
将指针转变的这个过程用比喻描述一下,边老师为了省事,想插个队,队里有两个熟人
小杨和小刘,所以,他想插到两个人中间,但是三个人平时关系太好了,只要在一起,就
要让后面的人的手插到前面的人的屁兜里。如果前面的人屁兜里没有基佬的手,将浑身不
适。所以,必须保证前面的人屁兜里有一只手。(小杨在前,小刘在后)
这个时候,边老师大步向前,将自己的手轻轻的放入小杨的屁兜里,(这是第一步)
然后,将小刘放在小杨屁兜里的手抽出来放到自己屁兜里。(这是第二步)
*/
}
//删除k后面的数
void remove(int k)
{
ne[k] = ne[ne[k]];//让k的指针指向,k下一个人的下一个人,那中间的那位就被挤掉了。
}
int main()
{
cin >> n ;
Init();
while(n--)
{
//int x,k;
char a;
cin >> a;
if(a == 'H')
{
int x;
cin >> x;
int_to_head(x);
}
else if(a == 'D')
{
int k;
cin >> k ;
if (!k) head = ne[head];//删除头节点
else remove(k - 1);//注意删除第k个输入后面的数,那函数里放的是下标,k要减去1
}
else
{
int x,k;
cin >> k >> x;
add(k - 1,x); // 同样的下标要减一
}
}
for (int i = head; i != -1; i = ne[i] ) cout << e[i] << ' ';
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla