首页data structure

# 1

# 题目描述

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

# 输入

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

# 输出

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

# 样例输入

abc
apple
software

# 样例输出

7
16
37

# 题解

#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

# 样例输入

appleorange
orange

# 样例输出

6

# 题解

#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 阶方阵主对角线上数据的和。

# 样例输入

3
1 2 3
1 2 3
1 2 3

# 样例输出

6

# 题解

#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）。

# 输出

输出符合题意的螺旋阵。

# 样例输入

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

# 题解

#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 上，每次只能移动一个盘子，输出移动每一次过程。每次移动占一行，第一个数表示第几步移动，第二个数是移动的盘子的半径，然后是从哪个柱子移动到哪个柱子。

# 样例输入

2

# 样例输出

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

# 题解

#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。

# 输出

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

# 样例输入

B E
B F
A B
A C

# 样例输出

A B E F C

# 题解

#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。

# 输出

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

# 样例输入

B E
B F
A B
A C

# 样例输出

E F B C A

# 题解

#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;
}