fantacy

用户名：dotcpp0750464

访问量：177

签　名：

等　　级
排　　名	29180
经　　验	522
参赛次数	0
文章发表	2
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

左移右移双向链表 c++
浏览：70

你可能喜欢

A+B for Input-Output Practice (VII) （C++代码）

左移右移双向链表 c++

　　作者: fantacy　　　　发表时间：2024-04-11 10:32:59 浏览：70　|　评论：0　

原题链接：蓝桥杯2022年第十三届决赛真题-左移右移

##### 解题思路
使用双向链表维护整个数组即可，每次操作就是处理节点边与边之间的关系
左移x：1.删除节点x 2.将x插入到r[0]节点的左边
右移x：1.删除节点x 2.将x插入到n+1节点的左边

##### 时间复杂度
O(m + n)

##### 注意事项
记得数组开大一点，我这里开到了200010

##### 参考代码
```c++
#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
const int N = 200010;
 
int n, m;
int l[N], r[N];
 
void del(int x)
{
    r[l[x]] = r[x];
    l[r[x]] = l[x]; 
}
 
// 将a节点插入到b节点的左边 
void insert(int a, int b)
{
    r[l[b]] = a;
    l[a] = l[b];
    l[b] = a;
    r[a] = b;
}
 
int main()
{
    scanf("%d%d", &n, &m);  
     
    r[0] = 1, l[n + 1] = n;
     
    for(int i = 1; i <= n; i++)
    {
        l[i] = i - 1;
        r[i] = i + 1;
    }
     
    while(m--)
    {
        int x;
        char op[3];
        scanf("%s%d", op, &x);
        if(op[0] == 'L')
        {
            if(r[0] == x && l[x] == 0) continue;
            // 删除节点 
            del(x);
            insert(x, r[0]);
        }
        else
        {
            if(l[n + 1] == x && r[x] == n + 1) continue;
			// 删除节点
            del(x);
            insert(x, n + 1);           
        }
    }
     
    for(int i = r[0]; i != n + 1; i = r[i])
        printf("%d ", i);
         
    return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

fantacy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

C二级辅导-计负均正（C++代码）

IP判断（C++代码）

A+B for Input-Output Practice (VII) （C++代码）

回文串（C语言代码）

左移右移双向链表 c++

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

多输入输出练习2 （C语言代码）

买不到的数目（C语言代码）

C二级辅导-计负均正（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 指针（C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

DNA （Java代码）

fantacy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

C二级辅导-计负均正 （C++代码）

IP判断 （C++代码）

A+B for Input-Output Practice (VII) （C++代码）

回文串 （C语言代码）

左移右移 双向链表 c++

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

多输入输出练习2 （C语言代码）

买不到的数目 （C语言代码）

C二级辅导-计负均正 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 指针（C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

DNA （Java代码）

C二级辅导-计负均正（C++代码）

IP判断（C++代码）

回文串（C语言代码）

左移右移双向链表 c++

　　评论区

买不到的数目（C语言代码）

C二级辅导-计负均正（C语言代码）