数据结构专题
徐仓仓 Lv3
  2022-08-16 16:14:44 2022-08-16 16:14    

📅time:8.16 - 8.17

🍔题目：

1051 25 Pop Sequence

1074 25 Reversing Linked List 模拟反转链表
1032 25 Sharing 链表遍历 所有题都这么easy就好了
1052 25 Linked List Sorting 链表排序 败在可能有多个链表
1097 25 Deduplication on a Linked List 链表遍历，分为两个链表

stack

判断某序列是不是栈的输出顺序

🎈1051 Pop Sequence

List

链表定义

静态链表

若结点地址是比较小的整数（5位数的地址），可采用静态链表；

注意很多题目输出时要保留五位printf(“%05d”,address);

1
2
3
4
5
struch Node{
	int data;
	int next;
}node[size];
node[11111].next = 22222;

动态链表

1
2
3
4
struct node{
	int data;
	node* next;
}

反转链表

🎈1074 Reversing Linked List

将每个范围内的结点进行反转：

如 1→2→3→4→5→6 ,K=3,反转后 3→2→1→6→5→4; K=4,反转后 4→3→2→1→5→6。

  • 直接利用vector的reverse函数，将指定区间进行反转。（十分简单，但难以想到）
  • 模拟链表反转（之过了17分，因为每个区间的第一个结点的next错误）

注意：测试数据可能不只一个链表，要对有效结点进行计数。

For the sake of simplicity

duplicated absolute values

附录

1051 Pop Sequence

利用vector实现

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
#include<iostream>
#include<stack>
using namespace std;
int M, N, K;
int num[1010];
int main() {
	cin >> M >> N >> K;
	for (int i = 0; i < K; i++) {
		for (int j = 0; j < N; j++) {
			cin >> num[j];
		}
		stack<int>q;
		bool flag = true;
		int index = 0;
		int n = 0;
		while (n < N) {
			//if(!q.empty())
			//cout << "top" << q.top() << endl;
			if (!q.empty() && q.top() == num[index]) {
				index++;
				q.pop();
				//cout << "pop"<<endl;
			}
			else {
				q.push(++n);
				//cout << "push" << n << endl;
			}
			if (q.size() > M) {
				flag = false;
				break;
			}
		}
		while (!q.empty()) {
			if (q.top() == num[index++]) {
				q.pop();
			}
			else { flag = false; break; }
		}
		if(!flag){ cout << "NO\n"; }
		else cout << "YES\n";
	}
}

1074 Reversing Linked List

注意：测试数据可能不只一个链表，要对有效结点进行计数。

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
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int start, N, K;
int number[maxn];
int nextd[maxn];
int main() {
	cin >> start >> N >> K;
	int add;
	for (int i = 0; i < N; i++) {
		cin >> add;
		cin >> number[add] >> nextd[add];
	}
	vector<int>q;
	int index = start;
	while (index != -1) {
		q.push_back(index);
		index = nextd[index];
	}
	for (int i = 0; i < q.size() / K; i++) {
		reverse(q.begin() + i * K, q.begin() + (i + 1) * K);
	}
	for (int i = 0; i < q.size(); i++) {
		printf("%05d %d ", q[i], number[q[i]]);
		if (i + 1 == q.size()) puts("-1");
		else printf("%05d\n", q[i + 1]);
	}
}

1032 Sharing

链表遍历，注意输出格式

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
#include<iostream>
using namespace std;
const int maxn = 100000;
int s1, s2, N;
bool flag[maxn];
struct node {
	char c;
	int next;
}chain[maxn];
int main() {
	cin >> s1 >> s2 >> N;
	int index;
	for (int i = 0; i < N; i++) {
		cin >> index;
		cin >> chain[index].c >> chain[index].next;
	}
	index = s1;
	while (index != -1) {
		flag[index] = true;
		index = chain[index].next;
	}
	index = s2;
	while (index != -1) {
		if (flag[index]){
			printf("%05d\n", index);//注意输出格式
			return 0;
		}
		index = chain[index].next;
	}
	cout << -1;
}

1052 Linked List Sorting

测试点4：可能有多个链表

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

#include<iostream>
#include<algorithm>
using namespace std;
struct Node {
	int n = 0;
	int next = -1;
	int p = -1;
	bool flag = false;
};
bool cmp(Node a, Node b) {
	if (a.flag == false || b.flag == false) {
		return a.flag > b.flag;
	}
	return a.n < b.n;
}
Node all[100010];
int main() {
	int size;
	int start;
	cin >> size >> start;
	int address, num, next_address, max = 0;
	for (int i = 0; i < size; i++) {
		scanf("%d%d%d", &address, &num, &next_address);
		all[address].p = address;
		all[address].n = num;
		all[address].next = next_address;
		max = address > max ? address : max;
	}
	int index = start;
	int count = 0;
	while (all[index].p != -1&&index!=-1) {
		count++;
		all[index].flag = true;
		index = all[index].next;
	}
	/*all[index].flag = true;
	count++;*/
	if (count == 0) {
		printf("%d %d\n", 0, -1);
		return 0;
	}
	sort(all, all + max + 1, cmp);
	printf("%d %05d\n", count, all[0].p);
	for (int i = 0; i < count - 1; i++) {
		printf("%05d %d %05d\n", all[i].p, all[i].n, all[i + 1].p);
	}
	printf("%05d %d %d\n", all[count - 1].p, all[count - 1].n, -1);
}

1097 Deduplication on a Linked List

注意第二个链表可能是空的

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
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 100000;
struct node {
	int data;
	int next=-1;
	int p;
};
node chain[maxn];
bool flag[maxn];
vector<node>s1, s2;
int main() {
	int start,N;
	cin >> start >> N;
	int index;
	for (int i = 0; i < N; i++) {
		cin >> index;
		cin >> chain[index].data >> chain[index].next;
		chain[index].p = index;
	}
	index = start;
	while (index != -1) {
		if (!flag[abs(chain[index].data)]) {
			flag[abs(chain[index].data)] = true;
			s1.push_back(chain[index]);
		}
		else s2.push_back(chain[index]);
		index = chain[index].next;
	}
	for (int i = 0; i < s1.size()-1; i++) {
		printf("%05d %d %05d\n", s1[i].p, s1[i].data, s1[i + 1].p);
	}
	printf("%05d %d %d\n", s1[s1.size() - 1].p, s1[s1.size() - 1].data, -1);
	if (!s2.empty()) {
		for (int i = 0; i < s2.size() - 1; i++) {
			printf("%05d %d %05d\n", s2[i].p, s2[i].data, s2[i + 1].p);
		}
		printf("%05d %d %d\n", s2[s2.size() - 1].p, s2[s2.size() - 1].data, -1);
	}
}
 Comments