数据结构题目02

1

题目描述

给你若干个字符串,请编程输出每个字符串的子串个数。

输入

若干个字符串,每个字符串占一行,字符串中不含空格,长度最大为1000。

输出

对应每一行的字符串,输出该字符串子串的个数。

样例输入

1
2
3
abc
apple
software

样例输出

1
2
3
7
16
37

题解

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
while(cin >> s){
cout << s.length() * (s.length() + 1) / 2 + 1 << endl;
}
return 0;
}

2

题目描述

给你一个目标串,请查找在给目标串中是否存在模式串,存在就输出第一个模式串在目标串中出现的位置。

输入

占两行,第一行是目标串(长度小于1000),第二行为模式串(长度小于100)。

输出

输出模式串在目标串中出现的位置,即模式串匹配到目标串时第一个字符在目标串的位置(注意从1开始描述字符开始位置),不能匹配时输出0

样例输入

1
2
appleorange
orange

样例输出

1
6

题解

1
2
3
4
5
6
7
8
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, a;
cin >> s >> a;
cout << s.find(a) + 1;
return 0;
}

3

题目描述

在一个N行N列的方阵(或称N阶方阵)中,从左上角到右下角这一斜线上有N个数据元素,这个斜线称为方阵的主对角线。给你一个方阵,请求方阵主对角线上数据的和。

输入

第一行是N(N<100),表示下边是一个N阶方阵。接下来N行N列用空格间隔放置正整数(int型)。

输出

N阶方阵主对角线上数据的和。

样例输入

1
2
3
4
3
1 2 3
1 2 3
1 2 3

样例输出

1
6

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, sum = 0;
cin >> n;
for (int i = 0; i < n; i++)
for(int j = 0; j < n; j++){
int a;
cin >> a;
if (i == j){
sum += a;
}
}
cout << sum;
return 0;
}

4

题目描述

给你一个N行N列的方格矩阵,从外圈按顺时针依次填写自然数,这会构成一个螺旋阵,你能编程实现吗?
比如5行5列的情况如下:

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

输入

输入一个正整数数N(N<100)。

输出

输出符合题意的螺旋阵。

样例输入

1
5

样例输出

1
2
3
4
5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

题解

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
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, c = 0, cnt = 1;
int a[101][101];
cin >> n;
while (cnt <= n * n) {
//上方
for (int i = c; i < n - c; i++) {
a[c][i] = cnt++;
}
//右方
for (int i = c + 1; i < n - c; i++) {
a[i][n - c - 1] = cnt++;
}
//下方
for (int i = n - c - 2; i >= c; i--) {
a[n - c - 1][i] = cnt++;
}
//左方
for (int i = n - c - 2; i >= c + 1; i--) {
a[i][c] = cnt++;
}
c++;
}
for (int i = 0; i < n; i++) {
for(int j = 0; j < n; j++){
cout << a[i][j]<<' ';
}
cout << endl;
}
return 0;
}

5

题目描述

有三根标为A,B,C的柱子,A柱子上从上到下按金字塔状依次叠放着n个半径从1厘米到n厘米的的圆盘,要把A上的所有盘子移动到柱子C上,中间可以临时放在B上,但每次移动每一根柱子上都不能出现大盘子在小盘子上方的情况,要求用最少的移动次数完成,请编程模拟每次移动。

输入

占一行,为整数n(n<64),表示盘子数。

输出

把A上的所有盘子移动到柱子C上,每次只能移动一个盘子,输出移动每一次过程。每次移动占一行,第一个数表示第几步移动,第二个数是移动的盘子的半径,然后是从哪个柱子移动到哪个柱子。

样例输入

1
2

样例输出

1
2
3
1 1 A->B
2 2 A->C
3 1 B->C

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int cnt = 1;
void Hanoi (int n, char x, char y, char z){
if (n == 1) {
printf("%d %d %c->%c\n",cnt++,n,x,z);
}
else {
Hanoi(n - 1, x, z, y);
printf("%d %d %c->%c\n",cnt++,n,x,z);
Hanoi(n - 1, y, x, z);
}
}
int main() {
int n;
cin >> n;
Hanoi(n, 'A', 'B', 'C');
return 0;
}

6

题目描述

已知一颗树的节点间关系,请编程实现该树的先根遍历。

输入

若干行,每行描述了一组双亲节点和孩子节点的关系序偶对(每个节点用不同的大写字母表示,节点小于26个)。且数的度小于5。

输出

该树的先根遍历序列,序列中每个字母用空格隔开。

样例输入

1
2
3
4
B E
B F
A B
A C

样例输出

1
A B E F C

题解

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
#include <bits/stdc++.h>
using namespace std;
struct Node {
vector<int> sons;
Node(){}
}node[26];
int root = -1;
void preOrder(int root) {
cout << char(root + 'A') << ' ';
for (int i = 0; i < node[root].sons.size(); i++){
preOrder(node[root].sons[i]);
}
}
int main() {
char p, c;
while(cin >> p >> c) {
if (p == EOF || c == EOF) break;
node[p - 'A'].sons.push_back(c - 'A');
if (root == c - 'A' || root == -1) {
root = p - 'A';
}
}
preOrder(root);
return 0;
}

7

题目描述

已知一颗树的节点间关系,请编程实现该树的后根遍历序列。

输入

若干行,每行描述了一组双亲节点和孩子节点的关系序偶对(每个节点用不同的大写字母表示,节点小于26个)。且数的度小于5。

输出

该树的后根遍历序列,序列中每个字母用空格隔开。

样例输入

1
2
3
4
B E
B F
A B
A C

样例输出

1
E F B C A

题解

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
#include <bits/stdc++.h>
using namespace std;
struct Node {
vector<int> sons;
Node(){}
}node[26];
int root = -1;
void postOrder(int root) {

for (int i = 0; i < node[root].sons.size(); i++){
postOrder(node[root].sons[i]);
}
cout << char(root + 'A') << ' ';
}
int main() {
char p, c;
while(cin >> p >> c) {
if (p == EOF || c == EOF) break;
node[p - 'A'].sons.push_back(c - 'A');
if (root == c - 'A' || root == -1) {
root = p - 'A';
}
}
postOrder(root);
return 0;
}

数据结构题目02
https://ivansnow02.github.io/posts/45666/
作者
Ivan Snow
发布于
2023年6月6日
许可协议