AcWing 827. 双链表
原题链接
简单
作者:
N1ce丶燊
,
2019-06-05 22:58:35
,
所有人可见
,
阅读 11283
#include <iostream>
using namespace std;
const int N=100010;
int e[N],l[N],r[N],idx=0;
void insertL(int x)
{
l[idx]=0;
r[idx]=r[0];
r[0]=idx;
l[r[idx]]=idx;
e[idx++]=x;
}
void insertR(int x)
{
r[idx]=1;
l[idx]=l[1];
r[l[idx]]=idx;
l[1]=idx;
e[idx++]=x;
}
void deleteK(int k)
{
r[l[k]]=r[k];
l[r[k]]=l[k];
}
void insertKL(int k,int x)
{
l[idx]=l[k];
r[idx]=k;
r[l[idx]]=idx;
l[k]=idx;
e[idx++]=x;
}
void insertKR(int k,int x)
{
r[idx]=r[k];
l[idx]=k;
l[r[idx]]=idx;
r[k]=idx;
e[idx++]=x;
}
void init()
{
r[0]=1;
l[1]=0;
idx=2;
}
int main()
{
ios::sync_with_stdio(false);
init();
int m;
cin>>m;
while(m-->0)
{
string command;
int k,x;
cin>>command;
if(command=="L")
{
cin>>x;
insertL(x);
}
else if(command=="R")
{
cin>>x;
insertR(x);
}
else if (command=="D")
{
cin>>k;
deleteK(k+1);
}
else if (command=="IL")
{
cin>>k>>x;
insertKL(k+1,x);
}
else if(command=="IR")
{
cin>>k>>x;
insertKR(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<' ';
cout<<endl;
return 0;
}
思路清晰
// 在第 k 个插入的数左侧插入一个数 void add_IL(int k, int x) { e[idx] = x; l[idx] = l[k]; //s->pre = k->pre r[idx] = k; //s->next = k l[k] = idx; //k->pre = s r[l[idx]] = idx; //k->pre->next = s idx++; //r[l[idx]] = idx++; 是错的 }
请问,为什么这个idx++合在最后一句一起写是错的?
我试了一下,不会错,是不是你的代码有别的问题?
为什么用字符数组结果不对呢,换成string就对了
字符数组会把空格也读进去
大佬 牛逼 很详细
大哥啊,我觉得代码可以稍微简化一下,看得有点费劲
可能只是想详细给新人写写hh
是第k+1不是第k卡了我半天。。谢谢dl
可以写通用函数, 写的太细了.
牛
第k个数的左边插入x中的,新节点->pre->next相当于就是r[l[idx]]=k;而右插入x中的新节点->pre->next相当于l[r[k]]=idx;不知道作者的思路是啥,我不太理解。
右插入x中的新节点->pre->next相当于l[r[k]]=idx 意思就是k的右指针所指向的节点的左指针指向idx