此作业为某大学数据结构作业2，答案为我当时所写，仅供学习和参考

问题 A: 统计回文子串

题目描述

现在给你一个字符串S，请你计算S中有多少连续子串是回文串。

输入

输入包含多组测试数据。每组输入是一个非空字符串，长度不超过5000。

输出

对于每组输入，输出回文子串的个数。

样例输入

1
2
aba
aa

样例输出

1
2
4
3

参考答案

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 <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    while (getline(cin, s)) {
        int ans=0;
        for (int i = 0; i < s.length(); ++i) {
            int j=i,k=i;
            while (j>=0 && k<s.length()) {
                if (s[j]==s[k]) ++ans;
                else break;
                --j;
                ++k;
            }
        }
        for (int i = 0; i < s.length()-1; ++i) {
            int j=i,k=i+1;
            while (j>=0 && k<s.length()) {
                if (s[j]==s[k]) ++ans;
                else break;
                --j;
                ++k;
            }
        }
        cout << ans << endl;
        s.clear();
        if (cin.peek() == '\n') break;
    }
    return 0;
}

问题 B: 构建矩阵

题目描述

现请你构建一个N*N的矩阵，第i行j列的元素为i与j的乘积。（i，j均从1开始）

输入

输入的第一行为一个正整数C，表示测试样例的个数。
然后是C行测试样例，每行为一个整数N（1<=N<=9），表示矩阵的行列数。

输出

对于每一组输入，输出构建的矩阵。

样例输入

1
2
3
2
1
4

样例输出

1
2
3
4
5
1
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16

参考答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    while (n--) {
        int N;
        cin >> N;
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                cout << i*j << " ";
            }
            cout << endl;
        }
    }
    return 0;
}

问题 C: 找规律填数字

题目描述

小宇正在读小学，今天老师布置了几道数学题目。小宇平时上课经常不专心，这些他可发愁了，怎么办呢？看看你能不能帮帮他。
题目是给你一组有规律序列的前面5个整数，请你给出它后面跟着的5个整数，如：1,2,3,4,5,,,_,,___。这是个等差数列，后面应该是6,7,8,9,10，就这么简单。而且现在小宇已经知道这串序列要么是等差数列，要么是等比数列或者是斐波那契数列。

输入

输入包含多组测试数据。每组输入5个整数，每个数字之间隔一个空格，当5个数字都为0时输入结束。

输出

对于每组输入，输出这串数列的后面5个数字，每个数字之间隔一个空格。

样例输入

1
2
3
4
1 2 3 4 5
1 2 4 8 16
1 2 3 5 8
0 0 0 0 0

样例输出

1
2
3
6 7 8 9 10
32 64 128 256 512
13 21 34 55 89

参考答案

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
#include <iostream>

using namespace std;

bool isDis(int* arr){
    int distant = arr[1]-arr[0];
    for (int i = 1; i < 4; ++i) {
        if ((arr[i+1]-arr[i])!=distant) return false;
    }
    return true;
}

bool isFib(int* arr){
    for (int i = 0; i < 3; ++i) {
        if (arr[i] + arr[i+1] != arr[i+2]) return false;
    }
    return true;
}

void outDis(int num, int dis){
    for (int i = 0; i < 5; ++i) {
        cout << num+dis << " ";
        num += dis;
    }
    cout << endl;
}

void outGeo(int num, int pro){
    for (int i = 0; i < 5; ++i) {
        cout << num*pro << " ";
        num *= pro;
    }
    cout << endl;
}

void outFib(int num1, int num2){
    for (int i = 0; i < 5; ++i) {
        cout << num1 + num2 << " ";
        int tmp = num1;
        num1 = num2;
        num2 += tmp;
    }
    cout << endl;
}

int main() {
    int arr[5];
    while (true) {
        cin >> arr[0] >> arr[1] >> arr[2] >> arr[3] >> arr[4];
        bool flag = true;
        for (auto it : arr) {
            if (it!=0) flag = false;
        }
        if (flag) break;
        if (isDis(arr)) {
            outDis(arr[4], arr[1]-arr[0]);
        }
        else if (isFib(arr)) {
            outFib(arr[3], arr[4]);
        }
        else {
            outGeo(arr[4], arr[1]/arr[0]);
        }
    }
    return 0;
}

问题 D: 复原二叉树

题目描述

小明在做数据结构的作业，其中一题是给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。

输入

输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。

输出

对于每组输入，输出对应的二叉树的后续遍历结果。

样例输入

1
2
DBACEGF ABCDEFG
BCAD CBAD

样例输出

1
2
ACBFGED
CDAB

参考答案

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
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

struct node{
    char data;
    node *lChild, *rChild;
};

node* getNewNode(char& data){
    return new node({data, nullptr, nullptr});
}

node* mergeTree(string preS, string inS){
    if (preS.empty()) return nullptr;
    if (preS.length()==1) return getNewNode(preS[0]);
    node* root = getNewNode(preS[0]);

    if (inS[0]==preS[0]) {
        root->rChild = mergeTree(string(preS.begin()+1, preS.end()), string(inS.begin()+1, inS.end()));
    } else {
        int k = 0;
        while (inS[k]!=preS[0]) {
            ++k;
        }
        root->lChild = mergeTree(string(preS.begin()+1, preS.begin()+1+k), string(inS.begin(), inS.begin()+k));
        root->rChild = mergeTree(string(preS.begin()+1+k, preS.end()), string(inS.begin()+1+k, inS.end()));
    }

    return root;
}

void postOrder(node* root){
    if (root==nullptr) return;
    postOrder(root->lChild);
    postOrder(root->rChild);
    cout << root->data;
}

void clear(node* root){
    if (root==nullptr) return;
    clear(root->lChild);
    clear(root->rChild);
    delete root;
}

int main() {
    string s, preS, inS;
    while (getline(cin, s)) {
        preS.assign(s, 0, s.length()/2);
        inS.assign(s, (s.length()+2)/2, s.length()/2);
        node* root = mergeTree(preS, inS);
        //输出后序遍历
        postOrder(root);
        cout << endl;
        s.clear();
        clear(root);
        if (cin.peek() == '\n') break;
    }
    return 0;
}

问题 E: 子树的后序遍历

题目描述

给你一颗二叉树的中序和后序遍历序列，请编程输出该二叉树左子树或右子树的后序遍历序列。

输入

占三行，第一行表示二叉树的中序遍历序列，第二行表示后序遍历序列。用大写字母标识结点，二叉树的结点最多26个。
第三行是单个字母，L表示要求输出该二叉树的左子树的后序遍历序列，R表示要求输出该二叉树的右子树的后序遍历序列。

输出

按要求输出该二叉树左子树或右子树的后序遍历序列。

样例输入

1
2
3
BDCEAFHG
DECBHGFA
R

样例输出

1
HGF

参考答案

这里我偷了个懒，直接把字符串倒过来，用上一问的代码做的

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
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

struct node{
    char data;
    node *lChild, *rChild;
};

node* getNewNode(char& data){
    return new node({data, nullptr, nullptr});
}

node* mergeTree(string preS, string inS){
    if (preS.empty()) return nullptr;
    if (preS.length()==1) return getNewNode(preS[0]);
    node* root = getNewNode(preS[0]);

    if (inS[0]==preS[0]) {
        root->lChild = mergeTree(string(preS.begin()+1, preS.end()), string(inS.begin()+1, inS.end()));
    } else {
        int k = 0;
        while (inS[k]!=preS[0]) {
            ++k;
        }
        root->rChild = mergeTree(string(preS.begin()+1, preS.begin()+1+k), string(inS.begin(), inS.begin()+k));
        root->lChild = mergeTree(string(preS.begin()+1+k, preS.end()), string(inS.begin()+1+k, inS.end()));
    }

    return root;
}

void postOrder(node* root){
    if (root==nullptr) return;
    postOrder(root->lChild);
    postOrder(root->rChild);
    cout << root->data;
}

void clear(node* root){
    if (root==nullptr) return;
    clear(root->lChild);
    clear(root->rChild);
    delete root;
}

int main() {
    string s, preS, inS;
    cin >> preS >> inS;
    char flag;
    cin >> flag;
    reverse(preS.begin(), preS.end());
    reverse(inS.begin(), inS.end());
    node* root = mergeTree(inS, preS);
    //输出后序遍历
    if (flag == 'L') postOrder(root->lChild);
    else postOrder(root->rChild);

    s.clear();
    clear(root);
    return 0;
}

问题 F: 迷宫问题

题目描述

小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。

输入

输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是两个整数N和M（1<=N,M<=100）。
接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。
字符的含义如下：
‘S’：起点
‘E’：终点
‘-’：空地，可以通过
‘#’：障碍，无法通过
输入数据保证有且仅有一个起点和终点。

输出

对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。

样例输入

1
2
3
4
5
6
7
1
5 5
S-###
-----
##---
E#---
---##

样例输出

1
9

参考答案

使用BFS做，DFS会超时

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
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int N, M;

bool l[105][105];

struct point {
    int x;
    int y;
    int step;
};

vector<pair<int, int>> v;

bool canMove(point& p) {
    if (p.x >= 0 && p.y >= 0 && p.x < M && p.y < N && l[p.y][p.x]) {
        return true;
    }
    return false;
}

int move_ming(pair<int, int> S, pair<int, int>& E) {

    if (S==E) return 0;

    queue<point> q;
    q.push(point({S.second, S.first, 0}));
    l[S.first][S.second] = false;
    while (!q.empty()) {
        point p = q.front();
        for(int i = 0; i < 4; ++i) {
            point next_p = point({p.x+v[i].second, p.y+v[i].first, p.step+1});
            if (canMove(next_p)) {
                if (next_p.x == E.second && next_p.y == E.first) {
                    return next_p.step;
                }
                q.push(next_p);
                l[next_p.y][next_p.x] = false;
            }
        }
        q.pop();
    }

    return -1;
}

int main() {
    v.push_back(pair<int, int>(-1, 0));
    v.push_back(pair<int, int>(1, 0));
    v.push_back(pair<int, int>(0, 1));
    v.push_back(pair<int, int>(0, -1));

    int T;
    cin >> T;
    while (T--) {
        cin >> N >> M;
        pair<int, int> S, E;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                l[i][j] = false;
            }
        }

        char sign;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                cin >> sign;
                if (sign == '-') {
                    l[i][j] = true;
                }
                else if (sign == '#') {
                    l[i][j] = false;
                }
                else if (sign == 'S') {
                    l[i][j] = true;
                    S.first = i;
                    S.second = j;
                }
                else if (sign == 'E') {
                    l[i][j] = true;
                    E.first = i;
                    E.second = j;
                }
            }
        }

        cout << move_ming(S, E) << endl;
    }
    return 0;
}