算法题

发表于 分类于 阅读次数： 本文字数： 545 阅读时长 ≈ 2 分钟

导航
返回数据结构与算法分类

本篇记录了一些个人做过算法题。

鞍点问题

找出二维矩阵的所有鞍点，如果没有鞍点打印相应信息。

鞍点：该元素在矩阵所在的行中最大，所在的列中最小。

矩阵大小不超过5*5

输入：

矩阵的行数 矩阵的列数

矩阵每一行的数字

测试输入：

4 4

4 4 5 5

1 2 5 4

1 2 4 3

8 9 6 8

期待输出：

第3行第3列是鞍点，鞍点是：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
#include<stdio.h>

int main(void) {
    int hang, lie, c, max, d, i, j, k;
    int a[5][5];
    printf("输入矩阵的行数列数：\n");
    if (scanf("%d%d", &hang, &lie) != 2 ||
        hang < 1 || hang > 5 || lie < 1 || lie > 5)
        return 1;
    printf("输入矩阵：\n");
    for (i = 0; i < hang; i++)
        for (j = 0; j < lie; j++)
            if (scanf("%d", &a[i][j]) != 1)
                return 1;
    d = 0;
    for (i = 0; i < hang; i++) {
        max = a[i][0];
        for (j = 1; j < lie; j++)
            if (a[i][j] > max)
                max = a[i][j];
        for (j = 0; j < lie; j++) {
            if (a[i][j] != max)
                continue;
            c = 0;
            for (k = 0; k < hang; k++) {
                if (a[i][j] > a[k][j]) {
                    c = 1;
                    break;
                }
            }
            if (c == 0) {
                d++;
                printf("第%d行，第%d列是鞍点，鞍点是：%d\n", i + 1, j + 1, a[i][j]);
            }
        }
    }
    if (d == 0)
        printf("没有鞍点。");
    return 0;
}

回文字符串

下面两个C++示例使用栈的实现中的SqStack及其函数，需将对应定义放在main前，并包含<iostream>、<string>和using namespace std;。每个main单独编译。

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
int main() {
    //回文字符串 
    bool flag=true ;
    char k;
    int i;
    SqStack q;
    initStack(q);
    string s;
    cin>>s;
    if (s.size() > static_cast<size_t>(maxSize)) {
        cout<<"输入超出栈容量"<<endl;
        return 1;
    }
    int t = static_cast<int>(s.size());
    for(i = 0 ;i < t/2 ; i++){
        push(q,s[i]);
    }
    if(t%2!=0){
        i++;
    }
    for(;i<t;i++){
        if(!pop(q,k) || s[i]!=k){
            flag=false;
            break;
        }
    }
    cout<<flag<<endl;
    
    return 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
//括号匹配
int main() {
    int i;
    SqStack q;
    initStack(q);
    string s;
    char r;
    bool flag = true;
    cin>>s;
    if (s.size() > static_cast<size_t>(maxSize)) {
        cout<<"输入超出栈容量"<<endl;
        return 1;
    }
    int t = static_cast<int>(s.size());
    for(i=0 ;i<t ; i++){
        if(s[i]=='('||s[i]=='['||s[i]=='{'){
            push(q,s[i]);
        }else if(s[i]==')'||s[i]==']'||s[i]=='}'){
            if(!pop(q,r) ||
               (s[i]==')' && r!='(') ||
               (s[i]==']' && r!='[') ||
               (s[i]=='}' && r!='{')){
                flag = false;
                break;
            }
        }
    }
    if(flag && isEmpty(q)){
        cout<<"匹配"<<endl;
    }else{
        cout<<"不匹配"<<endl;
    }
    return 0;
}