算法题整理——链表

发表于 | 分类于 |

UVa11988_Broken Keyboard

题意

输入多组数据，每组一行，包括不超过100000个字母、下划线和字符[和]。分别代表Home键和end键。对于每一组输入，输出打印在屏幕上的文本。

思路

使用链表。

笔者用了两个数组，一个按照输入顺序来存储字符，另一个存储当前位置字符下一个的位置。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<stdio.h>
#include<string.h>
int main()
{
	int const max=1e5; 
	char a[max];
	scanf("%s",a+1);
	int n=strlen(a+1);
	int cur=0,last=0;
	int next[max];
	for(int i=1;i<=n;i++)
	{
		if(a[i]=='[')
		{
			cur=0;
		}
		else if(a[i]==']')
		{
			cur=last;
		}
		else
		{
			next[i]=next[cur];
			next[cur]=i;
			if(cur==last)
			{
				last=i;
			}
			cur=i;
		}
	}
	for(int i=next[0];i!=0;i=next[i])
	{
		printf("%c",a[i]);
	}
}

UVa12657_移动盒子

题意

你有一排盒子，从左到右编号为1~n，现在可以执行以下四种命令：

1 X Y表示把盒子X移动到Y的左边。

2 X Y表示把盒子X移动到Y的右边。

3 X Y表示交换X和Y的位置。

4表示整条链左右翻转。

指令保证X不等于Y，输入盒子数，指令数，以及指令，输出所有奇数位置的盒子编号之和。

分析

本题可以使用链表实现，记录下每个节点左右两边的节点编号。进行操作时，可以维护这样的连接关系。

对于翻转，把所有节点的左右邻居翻转过来的操作太繁琐，所以可以使用一个翻转标记来记录是否翻转。如果已经翻转过，那么1操作需要转化成2操作来处理，2操作转化成1操作。如果再次翻转，标记从新置0，相当于没有翻转。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<stdio.h>
//#include<fstream>
const int N=1e5+5;

int left[N];
int right[N];

int main()
{
	//std::fstream output;
	//output.open("realoutput.txt");
	int n,m;
	int com,a,b,temp;
	int flag;
	int con=0;
	while(scanf("%d %d\n",&n,&m)!=EOF)
	{
		flag=0;
		for(int i=1;i<=n;++i)
		{
			left[i]=i-1;
			right[i]=(i+1)%(n+1);
		}
		right[0]=1;
		left[0]=n;
		while(m--)
		{
			scanf("%d",&com);
			if(com==4)
			{
				flag=!flag;
				continue;
			}
			scanf("%d %d",&a,&b);
			if(flag)com=3-com;
			else com%=3;
			switch (com)
			{
				case 0:
					if(right[a]==b)
					{
						right[left[a]]=b;
						left[right[b]]=a;
						right[a]=right[b];
						left[b]=left[a];
						left[a]=b;
						right[b]=a;
					}
					else if(left[a]==b)
					{
						right[left[b]]=a;
						left[right[a]]=b;
						right[b]=right[a];
						left[a]=left[b];
						left[b]=a;
						right[a]=b;
					}
					else
					{
						right[left[a]]=b;
						left[right[a]]=b;
						right[left[b]]=a;
						left[right[b]]=a;
						temp=right[a];
						right[a]=right[b];
						right[b]=temp;
						temp=left[b];
						left[b]=left[a];
						left[a]=temp;
					}
					break;
				case 1:
					if(left[b]==a)break;
					left[right[a]]=left[a];
					right[left[a]]=right[a];
					left[a]=left[b];
					right[a]=b;
					right[left[b]]=a;
					left[b]=a;
					break;
				case 2:
					if(right[b]==a)break;
					left[right[a]]=left[a];
					right[left[a]]=right[a];
					right[a]=right[b];
					left[a]=b;
					left[right[b]]=a;
					right[b]=a;
					break;
			}
		}
		long long ret=0;
		int odd=1;
		if(!flag)
		{
			for(int i=right[0];i;i=right[i])
			{
				if(odd)ret+=(long long)i;
				odd=!odd;
			}
		}
		else
		{
			for(int i=left[0];i;i=left[i])
			{
				if(odd)ret+=(long long)i;
				odd=!odd;
			}	
		}
		printf("Case %d: %lld\n",++con,ret);
		//output<<ret<<std::endl;
	}
	//output.close();
	return 0;
}