数据结构与算法编程题

First Post:

Last Update:

数据结构与算法作业

https://blog.csdn.net/lady_killer9/article/details/82695895?fromshare = blogdetail&sharetype = blogdetail&sharerId = 82695895&sharerefer = PC&sharesource = 2402_88180382&sharefrom = from_link

数据结构编程题

课本上的算法设计题

1.求两个递增链表的差集（第二章算法设计题第 4 题）

两个链表 A 和 B 分别表示两个集合 其元素递增排列。设计算法求出两个集合 A 和 B 的差集（仅由在 A 中出现而不在 B 中出现的元素构成的集合），并将结果以同样的形式存储，同时返回该集合的元素个数

在此之前先理解要想对函数内的值进行操作使得其在 main 函数值改变 必须用指针改变指定地址的值

如 swap 函数的实现 要理解子函数和主函数都会分配地址和内存 不是公共用的

利用改变指向的值来改变

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdio.h>
#include <stdlib.h>

// 链表节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 向链表末尾插入节点
void append(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;  // 如果链表为空，将新节点作为头节点
    } else {
        Node* temp = *head;
        while (temp->next) {
            temp = temp->next;  // 找到链表的最后一个节点
        }
        temp->next = newNode;  // 将新节点插入到链表末尾
    }
}

// 计算两个链表的差集 A - B
Node* difference(Node* A, Node* B, int* count) {
    Node* result = NULL;  // 差集链表的头节点
    *count = 0;  // 差集元素的数量
    Node* aPtr = A;  // 链表 A 的指针
    Node* bPtr = B;  // 链表 B 的指针

    // 遍历链表 A
    while (aPtr) {
        // 如果 A 的当前元素小于 B 的当前元素，加入差集
        if (bPtr == NULL || aPtr->data < bPtr->data) {
            append(&result, aPtr->data);  // 将 A 的元素添加到差集链表中
            (*count)++;  // 增加差集元素个数
            aPtr = aPtr->next;  // 移动 A 的指针
        }
        // 如果 A 和 B 的当前元素相等，跳过该元素
        else if (aPtr->data == bPtr->data) {
            aPtr = aPtr->next;  // 移动 A 的指针
            bPtr = bPtr->next;  // 移动 B 的指针
        }
        // 如果 A 的当前元素大于 B 的当前元素，移动 B 的指针
        else {
            bPtr = bPtr->next;
        }
    }
    return result;
}

// 打印链表
void printList(Node* head) {
    if (head == NULL) {
        printf("差集为空\n");
        return;
    }
    Node* temp = head;
    while (temp) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// 释放链表内存
void freeList(Node* head) {
    Node* temp;
    while (head) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

// 主函数
int main() {
    // 创建两个有序链表 A 和 B
    Node* A = NULL;
    Node* B = NULL;

    // 向链表 A 和 B 添加元素
    append(&A, 1);
    append(&A, 3);
    append(&A, 5);
    append(&A, 7);

    append(&B, 2);
    append(&B, 3);
    append(&B, 6);

    // 计算差集 A - B
    int count = 0;
    Node* diff = difference(A, B, &count);

    // 打印差集
    printf("差集 (A - B): ");
    printList(diff);
    printf("差集元素个数: %d\n", count);

    // 释放内存
    freeList(A);
    freeList(B);
    freeList(diff);

    return 0;
}

线性表

1.合并两个有序链表

描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入

输入两个顺序表 l1，l2，l1 和 l2 均按非递减顺序排列，两个链表的节点数目范围是 [0,50]，-100 <= Node.val <= 100

-1 表示链表结束符

输出

输出合并后的顺序表

输入样例

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

输出样例

1
2
1 1 2 3 4 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
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node* next;
} Node;

// 输入链表
Node* inputList() {
    int x;
    Node* head = (Node*)malloc(sizeof(Node));
    Node* tail = head;
    while (scanf("%d", &x) && x != -1) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->val = x;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
    }
    return head;
}

// 合并链表
Node* merge(Node* l1, Node* l2) {
    Node* dummy = (Node*)malloc(sizeof(Node));
    Node* tail = dummy;
    l1 = l1->next;
    l2 = l2->next;

    while (l1 && l2) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy;
}

// 打印链表
void printList(Node* head) {
    head = head->next;
    while (head) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

int main() {
    Node* l1 = inputList();
    Node* l2 = inputList();
    Node* merged = merge(l1, l2);
    printList(merged);
    return 0;
}

  • 输入链表函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // 输入链表
    Node* inputList() {
    int x;
    Node* head = (Node*)malloc(sizeof(Node));
    Node* tail = head;
    while (scanf("%d", &x) && x != -1) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = x;
    newNode->next = NULL;
    tail->next = newNode;
    tail = newNode;
    }
    return head;
    }
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>
using namespace std;

struct Node {
    int val;
    Node* next;
};

// 输入链表
Node* inputList() {
    int x;
    Node* head = new Node();
    Node* tail = head;
    while (cin >> x && x != -1) {
        Node* newNode = new Node();
        newNode->val = x;
        newNode->next = nullptr;
        tail->next = newNode;
        tail = newNode;
    }
    return head;
}

// 合并链表
Node* merge(Node* l1, Node* l2) {
    Node* dummy = new Node();
    Node* tail = dummy;
    l1 = l1->next;
    l2 = l2->next;

    while (l1 && l2) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy;
}

// 打印链表
void printList(Node* head) {
    head = head->next;
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Node* l1 = inputList();
    Node* l2 = inputList();
    Node* merged = merge(l1, l2);
    printList(merged);
    return 0;
}

描述 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回已排序的链表 输入 输入已排序的链表，链表中节点数目在范围 [0, 300] 内，-100 <= Node.val <= 100，题目数据保证链表已经按升序排列 -1 表示链表结束符 输出 输出已排序的链表 输入样例

2: 删除排序链表中的重复元素

1 1 2 3 3 -1 输出样例

1 2 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node* next;
} Node;

// 输入链表
Node* inputList() {
    int x;
    Node* head = (Node*)malloc(sizeof(Node));
    Node* tail = head;
    while (scanf("%d", &x) && x != -1) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->val = x;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
    }
    return head;
}

// 删除重复元素
Node* removeDuplicates(Node* head) {
    Node* curr = head->next;
    while (curr && curr->next) {
        if (curr->val == curr->next->val) {
            Node* tmp = curr->next;
            curr->next = curr->next->next;
            free(tmp); // 释放重复节点
        } else {
            curr = curr->next;
        }
    }
    return head;
}

// 打印链表
void printList(Node* head) {
    head = head->next;
    while (head) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

int main() {
    Node* head = inputList();
    head = removeDuplicates(head);
    printList(head);
    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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
};

// 输入链表
Node* inputList() {
    int x;
    Node* head = new Node();
    Node* tail = head;
    while (cin >> x && x != -1) {
        Node* newNode = new Node();
        newNode->val = x;
        newNode->next = nullptr;
        tail->next = newNode;
        tail = newNode;
    }
    return head;
}

// 删除重复元素
Node* removeDuplicates(Node* head) {
    Node* curr = head->next;
    while (curr && curr->next) {
        if (curr->val == curr->next->val) {
            Node* tmp = curr->next;
            curr->next = curr->next->next;
            delete tmp; // 释放重复节点
        } else {
            curr = curr->next;
        }
    }
    return head;
}

// 打印链表
void printList(Node* head) {
    head = head->next;
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Node* head = inputList();
    head = removeDuplicates(head);
    printList(head);
    return 0;
}

3: 移除链表元素

描述 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 输入 输入链表和 val，列表中的节点数目在范围 [0, 10^4] 内，1 <= Node.val <= 50，0 <= val <= 50 -1 表示链表结束符 输出 输出移除元素的链表 输入样例

1 2 6 3 4 5 6 -1 6 输出样例

1 2 3 4 5

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
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node* next;
} Node;

// 构建链表
Node* inputList() {
    int x;
    Node* head = (Node*)malloc(sizeof(Node));
    Node* tail = head;
    while (scanf("%d", &x) && x != -1) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->val = x;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
    }
    return head;
}

// 移除指定值的节点
Node* removeElements(Node* head, int val) {
    Node* curr = head;
    while (curr->next) {
        if (curr->next->val == val) {
            Node* tmp = curr->next;
            curr->next = curr->next->next;
            free(tmp);
        } else {
            curr = curr->next;
        }
    }
    return head;
}

// 打印链表
void printList(Node* head) {
    Node* p = head->next;
    while (p) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
}

int main() {
    Node* head = inputList();
    int val;
    scanf("%d", &val);
    head = removeElements(head, val);
    printList(head);
    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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
};

// 构建链表
Node* inputList() {
    int x;
    Node* head = new Node();
    Node* tail = head;
    while (cin >> x && x != -1) {
        Node* newNode = new Node();
        newNode->val = x;
        newNode->next = nullptr;
        tail->next = newNode;
        tail = newNode;
    }
    return head;
}

// 移除指定值的节点
Node* removeElements(Node* head, int val) {
    Node* curr = head;
    while (curr->next) {
        if (curr->next->val == val) {
            Node* tmp = curr->next;
            curr->next = curr->next->next;
            delete tmp;
        } else {
            curr = curr->next;
        }
    }
    return head;
}

// 打印链表
void printList(Node* head) {
    Node* p = head->next;
    while (p) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;
}

int main() {
    Node* head = inputList();
    int val;
    cin >> val;
    head = removeElements(head, val);
    printList(head);
    return 0;
}

4: 从尾到头打印链表

描述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

输入

输入链表，0 <= 链表长度 <= 10000

  • 1 表示链表结束符

输出

输出反转后的链表

输入样例

1
1 2 6 3 4 5 6 -1

输出样例

1
6 5 4 3 6 2 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Node* inputList() {
    int x;
    Node* head = (Node*)malloc(sizeof(Node));
    Node* tail = head;
        while (scanf("%d", &x) && x != -1) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->val = x;
        newNode->next = head->next;
        head->next = newNode;
        head = newNode;
    }
    return head;
}
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
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node* next;
} Node;

// 构建链表
Node* inputList() {
    int x;
    Node* head = (Node*)malloc(sizeof(Node));
    Node* tail = head;
    while (scanf("%d", &x) && x != -1) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->val = x;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
    }
    return head;
}

// 使用栈实现从尾到头打印链表
void printReverse(Node* head) {
    Node* curr = head->next;  // 跳过头节点
    int stack[10000];         // 用一个数组模拟栈
    int top = -1;
    
    // 将链表的值压入栈中
    while (curr) {
        stack[++top] = curr->val;
        curr = curr->next;
    }

    // 从栈中弹出值，按从尾到头的顺序打印
    while (top >= 0) {
        printf("%d ", stack[top--]);
    }
    printf("\n");
}

int main() {
    Node* head = inputList();
    printReverse(head);
    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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <stack>
using namespace std;

struct Node {
    int val;
    Node* next;
};

// 构建链表
Node* inputList() {
    int x;
    Node* head = new Node();
    Node* tail = head;
    while (cin >> x && x != -1) {
        Node* newNode = new Node();
        newNode->val = x;
        newNode->next = nullptr;
        tail->next = newNode;
        tail = newNode;
    }
    return head;
}

// 使用栈实现从尾到头打印链表
void printReverse(Node* head) {
    Node* curr = head->next;  // 跳过头节点
    stack<int> stk;
    
    // 将链表的值压入栈中
    while (curr) {
        stk.push(curr->val);
        curr = curr->next;
    }

    // 从栈中弹出值，按从尾到头的顺序打印
    while (!stk.empty()) {
        cout << stk.top() << " ";
        stk.pop();
    }
    cout << endl;
}

int main() {
    Node* head = inputList();
    printReverse(head);
    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
35
36
37
38
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node* next;
};

// 使用头插法构建链表
Node* inputList() {
    int x;
    Node* head = (Node*)malloc(sizeof(Node));  // 创建头节点
    head->next = NULL;  // 头节点的 next 初始为 NULL
    while (scanf("%d", &x) && x != -1) {  // 输入直到遇到 -1
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->val = x;
        newNode->next = head->next;  // 新节点的 next 指向原头节点的下一个节点
        head->next = newNode;  // 将新节点插入到头部
    }
    return head;  // 返回头节点
}

// 普通打印链表函数
void printList(Node* head) {
    Node* current = head->next;  // 跳过头节点
    while (current) {
        printf("%d ", current->val);
        current = current->next;
    }
    printf("\n");
}

int main() {
    Node* head = inputList();
    printList(head);  // 打印链表
    return 0;
}

5: 合并两个链表

描述

给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。

请你将 list1 中下标从 a 到 b 的全部节点都删除，并将 list2 接在被删除节点的位置。

输入

3 <= list1.length <= 10^4

1 <= a <= b < list1.length - 1

1 <= list2.length <= 10^4

  • 1 作为链表结束符

输出

输出链表

输入样例

1
2
3
4
5
0 1 2 3 4 5 -1
3
4
1000000 1000001 1000002 -1

输出样例

1
0 1 2 1000000 1000001 1000002 5
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
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node* next;
} Node;

// 尾插法构建链表
Node* inputList() {
    int x;
    Node* dummy = (Node*)malloc(sizeof(Node));
    dummy->next = NULL;
    Node* tail = dummy;
    while (scanf("%d", &x) && x != -1) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->val = x;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
    }
    return dummy;
}

// 打印链表
void printList(Node* head) {
    Node* p = head->next;  // 跳过 dummy 节点
    while (p) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
}

// 合并链表：删除 list1 第 a 到 b 个节点，插入 list2
Node* mergeInBetween(Node* list1, int a, int b, Node* list2) {
    Node* prevA = list1;
    for (int i = 0; i < a; i++) {
        prevA = prevA->next;
    }
    Node* afterB = prevA;
    for (int i = a; i <= b; i++) {
        afterB = afterB->next;
    }
    afterB = afterB->next;

    prevA->next = list2->next;

    Node* tail2 = list2;
    while (tail2->next) {
        tail2 = tail2->next;
    }
    tail2->next = afterB;

    return list1;
}

int main() {
    Node* list1 = inputList();
    int a, b;
    scanf("%d%d", &a, &b);
    Node* list2 = inputList();

    Node* merged = mergeInBetween(list1, a, b, list2);
    printList(merged);
    return 0;
}

1

6: 二进制链表转整数

描述

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。请你返回该链表所表示数字的 十进制值

输入

输入链表，链表不为空。链表的结点总数不超过 30。每个结点的值不是 0 就是 1。

  • 1 表示链表结束符

输出

输出十进制数

输入样例

1
2
1 0 1 -1

输出样例

1
5
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
#include <stdio.h>
#include <stdlib.h>

// 定义链表结构
struct ListNode {
    int val;
    struct ListNode *next;
};

// 创建新节点
struct ListNode* createNode(int value) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = value;
    newNode->next = NULL;
    return newNode;
}

// 二进制转十进制
int getDecimalValue(struct ListNode* head) {
    int result = 0;
    while (head != NULL) {
        result = result * 2 + head->val;  // 每次左移一位并加上当前位
        head = head->next;
    }
    return result;
}

int main() {
    // 读取输入并构建链表
    struct ListNode *head = NULL, *tail = NULL;
    int val;
    
    // 读取输入直到遇到-1
    while (scanf("%d", &val) && val != -1) {
        struct ListNode* newNode = createNode(val);
        if (head == NULL) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }

    // 计算并输出结果
    int result = getDecimalValue(head);
    printf("%d\n", result);

    // 释放内存
    while (head != NULL) {
        struct ListNode* temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

7: 两数相加 Ⅱ

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

**描述** 

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

**输入**

链表的长度范围为 [1, 100]

0 <= node.val <= 9

输入数据保证链表代表的数字无前导 0

- 1表示链表结束符

**输出**

输出链表

**输入样例**

7 2 4 3 -1 5 6 4 -1

1
2
3

**输出样例**

7 8 0 7

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

``` c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义链表结构
struct ListNode {
    int val;
    struct ListNode *next;
};

// 创建新节点
struct ListNode* createNode(int value) {
    struct ListNode * newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode-> val = value;
    newNode-> next = NULL;
    return newNode;
}

// 反转链表
struct ListNode * reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL, * curr = head, *next = NULL;
    while (curr != NULL) {
        next = curr-> next;
        curr-> next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 两数相加
struct ListNode * addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    // 反转链表以便从低位开始加
    l1 = reverseList(l1);
    l2 = reverseList(l2);
    
    struct ListNode* dummy = createNode(0);
    struct ListNode* curr = dummy;
    int carry = 0;
    
    // 按位相加
    while (l1 != NULL || l2 != NULL || carry > 0) {
        int sum = carry;
        if (l1 != NULL) {
            sum += l1-> val;
            l1 = l1-> next;
        }
        if (l2 != NULL) {
            sum += l2-> val;
            l2 = l2-> next;
        }
        
        carry = sum / 10;
        curr-> next = createNode(sum % 10);
        curr = curr-> next;
    }
    
    // 反转结果链表，使最高位在前
    struct ListNode* result = reverseList(dummy-> next);
    free(dummy);
    return result;
}

// 打印链表
void printList(struct ListNode* head) {
    while (head != NULL) {
        printf("%d", head-> val);
        if (head-> next != NULL) {
            printf(" ");
        }
        head = head-> next;
    }
    printf("\n");
}

int main() {
    struct ListNode *l1 = NULL, * l2 = NULL;
    struct ListNode *tail1 = NULL, * tail2 = NULL;
    int val;
    
    // 读取第一个链表
    while (scanf("%d", &val) && val != -1) {
        struct ListNode* newNode = createNode(val);
        if (l1 == NULL) {
            l1 = tail1 = newNode;
        } else {
            tail1-> next = newNode;
            tail1 = newNode;
        }
    }
    
    // 读取第二个链表
    while (scanf("%d", &val) && val != -1) {
        struct ListNode* newNode = createNode(val);
        if (l2 == NULL) {
            l2 = tail2 = newNode;
        } else {
            tail2-> next = newNode;
            tail2 = newNode;
        }
    }
    
    // 计算并打印结果
    struct ListNode* result = addTwoNumbers(l1, l2);
    printList(result);
    
    // 释放内存
    while (result != NULL) {
        struct ListNode* temp = result;
        result = result-> next;
        free(temp);
    }
    
    return 0;
}

8: 反转链表Ⅱ

描述

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

输入

链表中节点数目为 n

1 <= n <= 500

  • 500 <= Node.val <= 500

1 <= left <= right <= n

  • 1表示链表结束符

输出

输出链表

输入样例

1
2
1 2 3 4 5 -1 2 4

输出样例

1
1 4 3 2 5
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
95
#include <stdio.h>
#include <stdlib.h>

// 定义链表结构
struct ListNode {
    int val;
    struct ListNode *next;
};

// 创建新节点
struct ListNode* createNode(int value) {
    struct ListNode * newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode-> val = value;
    newNode-> next = NULL;
    return newNode;
}

// 反转链表指定区间
struct ListNode * reverseBetween(struct ListNode* head, int left, int right) {
    if (head == NULL || left == right) return head;
    
    struct ListNode* dummy = createNode(0);
    dummy-> next = head;
    struct ListNode* pre = dummy;
    
    // 移动到反转区间的前一个位置
    for (int i = 1; i < left; i++) {
        pre = pre-> next;
    }
    
    // 开始反转
    struct ListNode* curr = pre-> next;
    struct ListNode* next;
    struct ListNode* first = curr;  // 保存反转区间的第一个节点
    
    // 反转指定区间的链表
    for (int i = left; i <= right; i++) {
        next = curr-> next;
        curr-> next = pre-> next;
        pre-> next = curr;
        curr = next;
    }
    
    // 连接反转后的链表
    first-> next = curr;
    
    // 获取结果并释放 dummy 节点
    struct ListNode* result = dummy-> next;
    free(dummy);
    return result;
}

// 打印链表
void printList(struct ListNode* head) {
    while (head != NULL) {
        printf("%d", head-> val);
        if (head-> next != NULL) {
            printf(" ");
        }
        head = head-> next;
    }
    printf("\n");
}

int main() {
    struct ListNode *head = NULL, * tail = NULL;
    int val, left, right;
    
    // 读取链表
    while (scanf("%d", &val) && val != -1) {
        struct ListNode* newNode = createNode(val);
        if (head == NULL) {
            head = tail = newNode;
        } else {
            tail-> next = newNode;
            tail = newNode;
        }
    }
    
    // 读取 left 和 right
    scanf("%d %d", &left, &right);
    
    // 反转指定区间并打印结果
    struct ListNode* result = reverseBetween(head, left, right);
    printList(result);
    
    // 释放内存
    while (result != NULL) {
        struct ListNode* temp = result;
        result = result-> next;
        free(temp);
    }
    
    return 0;
}

9: 链表最大孪生和

描述

在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。

比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。

孪生和定义为一个节点和它孪生节点两者值之和。

给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。

输入

输入链表的节点数目是 [2, 10^5] 中的 偶数 。

1 <= Node.val <= 10^5

  • 1是链表结束符

输出

输出孪生和

输入样例

1
2
5 4 2 1 -1

输出样例

1
6
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
#include <stdio.h>
#include <stdlib.h>

// 定义链表结构
struct ListNode {
    int val;
    struct ListNode *next;
};

// 创建新节点
struct ListNode* createNode(int value) {
    struct ListNode * newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode-> val = value;
    newNode-> next = NULL;
    return newNode;
}

// 获取链表长度
int getLength(struct ListNode* head) {
    int len = 0;
    while (head != NULL) {
        len++;
        head = head-> next;
    }
    return len;
}

// 计算最大孪生和
int pairSum(struct ListNode* head) {
    if (head == NULL) return 0;
    
    // 获取链表长度
    int n = getLength(head);
    
    // 创建数组存储链表值
    int * values = (int*)malloc(n * sizeof(int));
    struct ListNode* curr = head;
    for (int i = 0; i < n; i++) {
        values [i] = curr-> val;
        curr = curr-> next;
    }
    
    // 计算最大孪生和
    int maxSum = 0;
    for (int i = 0; i < n/2; i++) {
        int twinSum = values [i] + values [n-1-i];
        if (twinSum > maxSum) {
            maxSum = twinSum;
        }
    }
    
    // 释放数组内存
    free(values);
    return maxSum;
}

int main() {
    struct ListNode *head = NULL, * tail = NULL;
    int val;
    
    // 读取链表
    while (scanf("%d", &val) && val != -1) {
        struct ListNode* newNode = createNode(val);
        if (head == NULL) {
            head = tail = newNode;
        } else {
            tail-> next = newNode;
            tail = newNode;
        }
    }
    
    // 计算并输出结果
    int result = pairSum(head);
    printf("%d\n", result);
    
    // 释放链表内存
    while (head != NULL) {
        struct ListNode* temp = head;
        head = head-> next;
        free(temp);
    }
    
    return 0;
}

10: 两数相加Ⅱ(新）

描述

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

输入

链表的长度范围为 [1, 100]

0 <= node.val <= 9

输入数据保证链表代表的数字无前导 0

  • 1表示链表结束符

输出

输出链表

输入样例

1
2
3
7 2 4 3 -1
5 6 4 -1

输出样例

1
7 8 0 7
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <stdio.h>
#include <stdlib.h>

// 定义链表结构
struct ListNode {
    int val;
    struct ListNode *next;
};

// 创建新节点
struct ListNode* createNode(int value) {
    struct ListNode * newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode-> val = value;
    newNode-> next = NULL;
    return newNode;
}

// 反转链表
struct ListNode * reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL, * curr = head, *next = NULL;
    while (curr != NULL) {
        next = curr-> next;
        curr-> next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 两数相加
struct ListNode * addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    // 反转链表以便从低位开始加
    l1 = reverseList(l1);
    l2 = reverseList(l2);
    
    struct ListNode* dummy = createNode(0);
    struct ListNode* curr = dummy;
    int carry = 0;  // 进位
    
    // 从低位开始相加
    while (l1 != NULL || l2 != NULL || carry > 0) {
        int sum = carry;
        
        if (l1 != NULL) {
            sum += l1-> val;
            l1 = l1-> next;
        }
        if (l2 != NULL) {
            sum += l2-> val;
            l2 = l2-> next;
        }
        
        // 处理进位
        carry = sum / 10;
        curr-> next = createNode(sum % 10);
        curr = curr-> next;
    }
    
    // 反转结果链表，使最高位在前
    struct ListNode* result = reverseList(dummy-> next);
    free(dummy);
    return result;
}

// 打印链表
void printList(struct ListNode* head) {
    while (head != NULL) {
        printf("%d", head-> val);
        if (head-> next != NULL) {
            printf(" ");
        }
        head = head-> next;
    }
    printf("\n");
}

int main() {
    struct ListNode *l1 = NULL, * l2 = NULL;
    struct ListNode *tail1 = NULL, * tail2 = NULL;
    int val;
    
    // 读取第一个链表
    while (scanf("%d", &val) && val != -1) {
        struct ListNode* newNode = createNode(val);
        if (l1 == NULL) {
            l1 = tail1 = newNode;
        } else {
            tail1-> next = newNode;
            tail1 = newNode;
        }
    }
    
    // 读取第二个链表
    while (scanf("%d", &val) && val != -1) {
        struct ListNode* newNode = createNode(val);
        if (l2 == NULL) {
            l2 = tail2 = newNode;
        } else {
            tail2-> next = newNode;
            tail2 = newNode;
        }
    }
    
    // 计算并打印结果
    struct ListNode* result = addTwoNumbers(l1, l2);
    printList(result);
    
    // 释放内存
    struct ListNode *temp;
    while (l1 != NULL) {
        temp = l1;
        l1 = l1-> next;
        free(temp);
    }
    while (l2 != NULL) {
        temp = l2;
        l2 = l2-> next;
        free(temp);
    }
    while (result != NULL) {
        temp = result;
        result = result-> next;
        free(temp);
    }
    
    return 0;
}

11: 重排链表

描述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

输入

输入链表的长度范围为 [1, 5 * 10^4]

1 <= node.val <= 1000

  • 1表示链表结束符

输出

输出重排链表

输入样例

1
2
1 2 3 4 5 -1

输出样例

1
1 5 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
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构
struct ListNode {
    int val;
    struct ListNode* next;
};

// 创建新节点
struct ListNode* createNode(int value) {
    struct ListNode * node = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (node == NULL) return NULL;
    node-> val = value;
    node-> next = NULL;
    return node;
}

// 找到链表中点
struct ListNode * findMiddle(struct ListNode* head) {
    struct ListNode *slow = head, * fast = head;
    struct ListNode *prev = NULL;
    
    while (fast && fast-> next) {
        fast = fast-> next-> next;
        prev = slow;
        slow = slow-> next;
    }
    
    if (prev) prev-> next = NULL;
    return slow;
}

// 反转链表
struct ListNode * reverse(struct ListNode* head) {
    struct ListNode *prev = NULL, * curr = head;
    while (curr) {
        struct ListNode* next = curr-> next;
        curr-> next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 合并两个链表
void merge(struct ListNode * l1, struct ListNode* l2) {
    while (l1 && l2) {
        struct ListNode* next1 = l1-> next;
        struct ListNode* next2 = l2-> next;
        
        l1-> next = l2;
        if (next1) l2-> next = next1;
        
        l1 = next1;
        l2 = next2;
    }
}

// 重排链表主函数
void reorderList(struct ListNode* head) {
    if (! head || ! head-> next) return;
    
    // 找中点并分割
    struct ListNode* mid = findMiddle(head);
    if (! mid) return;
    
    // 反转后半部分
    struct ListNode* second = reverse(mid);
    
    // 合并前后两部分
    merge(head, second);
}

// 创建链表
struct ListNode* createList() {
    struct ListNode *head = NULL, * tail = NULL;
    int val;
    
    while (scanf("%d", &val) && val != -1) {
        struct ListNode* node = createNode(val);
        if (! node) return NULL;
        
        if (! head) {
            head = tail = node;
        } else {
            tail-> next = node;
            tail = node;
        }
    }
    return head;
}

// 打印链表
void printList(struct ListNode* head) {
    while (head) {
        printf("%d", head-> val);
        if (head-> next) printf(" ");
        head = head-> next;
    }
    printf("\n");
}

// 释放链表内存
void freeList(struct ListNode* head) {
    while (head) {
        struct ListNode* temp = head;
        head = head-> next;
        free(temp);
    }
}

int main() {
    struct ListNode* head = createList();
    if (head) {
        reorderList(head);
        printList(head);
        freeList(head);
    }
    return 0;
}

12: 删除链表的倒数第 N 个结点

描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

输入

输入链表和要删除的n ，链表中结点的数目为 sz，

1 <= sz <= 30，0 <= Node.val <= 100，1 <= n <= sz

  • 1表示链表结束符

输出

输出链表

输入样例

1
2
3
1 2 3 4 5 -1
2

输出样例

1
1 2 3 5
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
95
96
97
98
99
100
101
102
103
#include <stdio.h>
#include <stdlib.h>

// 定义链表结构
struct ListNode {
    int val;
    struct ListNode *next;
};

// 创建新节点
struct ListNode* createNode(int value) {
    struct ListNode * newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode-> val = value;
    newNode-> next = NULL;
    return newNode;
}

// 删除倒数第 n 个节点
struct ListNode * removeNthFromEnd(struct ListNode* head, int n) {
    // 创建虚拟头节点，处理删除第一个节点的情况
    struct ListNode* dummy = createNode(0);
    dummy-> next = head;
    
    // 定义快慢指针，都从虚拟头节点开始
    struct ListNode *fast = dummy;
    struct ListNode *slow = dummy;
    
    // 快指针先前进 n+1 步
    for (int i = 0; i <= n; i++) {
        // 如果 n 大于链表长度，直接返回原链表
        if (fast == NULL) {
            return head;
        }
        fast = fast-> next;
    }
    
    // 快慢指针同时移动，直到快指针到达末尾
    while (fast != NULL) {
        fast = fast-> next;
        slow = slow-> next;
    }
    
    // 删除倒数第 n 个节点
    struct ListNode* toDelete = slow-> next;
    slow-> next = slow-> next-> next;
    free(toDelete);
    
    // 获取新的头节点
    head = dummy-> next;
    free(dummy);
    
    return head;
}

// 打印链表
void printList(struct ListNode* head) {
    while (head != NULL) {
        printf("%d", head-> val);
        if (head-> next != NULL) {
            printf(" ");
        }
        head = head-> next;
    }
    printf("\n");
}

int main() {
    struct ListNode *head = NULL, * tail = NULL;
    int val, n;
    
    // 读取链表
    while (scanf("%d", &val) && val != -1) {
        struct ListNode* newNode = createNode(val);
        if (head == NULL) {
            head = tail = newNode;
        } else {
            tail-> next = newNode;
            tail = newNode;
        }
    }
    
    // 读取 n
    scanf("%d", &n);
    
    // 删除倒数第 n 个节点并打印结果
    if (head != NULL) {
        head = removeNthFromEnd(head, n);
        printList(head);
        
        // 释放内存
        while (head != NULL) {
            struct ListNode* temp = head;
            head = head-> next;
            free(temp);
        }
    }
    
    return 0;
}

栈和队列

顺序栈的基本操作

Project: sequence_stack (数据结构-顺序栈) Date: 2018/09/14 Author: Frank Yu InitStack(SqStack &s) 参数：顺序栈s 功能：初始化 时间复杂度O(1) Push(SqStack &s,SElemType e) 参数：顺序栈s,元素e 功能：将e入栈 时间复杂度:O(1) Pop(SqStack &s,SElemType &e) 参数：顺序栈s,元素e 功能：出栈,e接收出栈元素值 时间复杂度O(1) GetTop(SqStack s,SElemType &e) 参数：顺序栈s,元素e 功能：得到栈顶元素 时间复杂度O(1) 注意：严蔚敏版没有判断栈空函数，在入栈、出栈函数里面判断栈是否空，与王道的不同 尤其是top指针在base之上(有元素时) 另外，严蔚敏版 59页取栈顶有误

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

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
#define Status int
#define SElemType int
#define MaxSize 100
//栈数据结构
typedef struct Stack
{
SElemType *base;//栈底指针 不变
SElemType *top;//栈顶指针 一直在栈顶元素上一个位置
int stacksize;//栈可用的最大容量
}SqStack;
//**** 基本操作函数**//
//初始化函数
Status InitStack(SqStack &s)
{
s.base = new SElemType [MaxSize];//动态分配最大容量
if(! s.base)
{
printf("分配失败\n");
return 0;
}
s.top = s.base;//栈顶指针与栈底相同 王道上 top 起初在 base 下面，感觉很别扭，top 应该高于或等于 base
s.stacksize = MaxSize;
return 1;
}
//入栈
Status Push(SqStack &s, SElemType e)
{
if(s.top-s.base == s.stacksize) return 0;//栈满
(s.top++)= e;//先入栈，栈顶指针再上移 注意与王道上的不同，具体问题具体分析
return 1;
}
//出栈 用 e 返回值
Status Pop(SqStack &s, SElemType &e)
{
if(s.top == s.base) return 0;//栈空
e =-s.top;//先减减 指向栈顶元素，再给 e
return 1;
}
//得到栈顶元素，不修改指针
bool GetTop(SqStack s, SElemType &e) //严蔚敏版 59 页有问题，应该用 e 去获得，函数返回 bool 类型去判断
{
if(s.top == s.base) return false;//栈空
else e =*-s.top;
return true;
}
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

//**功能实现函数** ******//
//菜单
void menu()
{
printf(" **1.入栈      2.出栈***\n ");
printf(" **3.取栈顶    4.退出***\n ");
}
//入栈功能函数 调用 Push 函数
void PushToStack(SqStack &s)
{
int n; SElemType e; int flag;
printf("请输入入栈元素个数(>= 1)：\n");
scanf("%d",&n);
for(int i = 0; i < n; i++)
{
printf("请输入第%d 个元素的值:", i+1);
scanf("%d",&e);
flag = Push(s, e);
if(flag)printf("%d 已入栈\n", e);
else {printf("栈已满！！！\n"); break;}
}
}
//出栈功能函数 调用 Pop 函数
void PopFromStack(SqStack &s)
{
int n; SElemType e; int flag;
printf("请输入出栈元素个数(>= 1)：\n");
scanf("%d",&n);
for(int i = 0; i < n; i++)
{
flag = Pop(s, e);
if(flag)printf("%d 已出栈\n", e);
else {printf("栈已空！！！\n"); break;}
}
}
//取栈顶功能函数 调用 GetTop
void GetTopOfStack(SqStack &s)
{
SElemType e; bool flag;
flag = GetTop(s, e);
if(flag)printf("栈顶元素为:%d\n", e);
else printf("栈已空！！！\n");
}
//主函数
int main()
{
SqStack s; int choice;
InitStack(s);
while(1)
{
menu();
printf("请输入菜单序号：\n");
scanf("%d",&choice);
if(choice == 4) break;
switch(choice)
{
case 1: PushToStack(s); break;
case 2: PopFromStack(s); break;
case 3: GetTopOfStack(s); break;
default: printf("输入错误！！！\n");
}
}
return 0;
}

算法设计题 双栈结构的实现

  • （1）将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空；当第1号栈的栈顶指针top[1]等于m时，该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下：   typedef struct{   int top[2], bot[2]; //栈顶和栈底指针 　 SElemType *V; //栈数组   int m; //栈最大可容纳元素个数   }DblStack;

链栈的基本操作

1: 括号匹配

描述

使用计算机进行运算时，需要对表达式中括号是否匹配进行检查，例如：(1+2)/(21+9)中括号匹配，(3+2(+(1+2))(2/3中括号不匹配。使用顺序栈实现对表达式中括号是否相匹配的检查。

输入

一个表达式（长度不超过100）。其中符号中仅包含“0123456789±*/^()”等基本符号。并且，表达式中的数字都是一位的，不会出现形如12的数字

输出

若匹配输出Yes，否则输出No

输入输出样例

输入1

1
2
(1+2)/(2*1+9)

输出1

1
2
Yes

输入2

1
2
(3+2(+(1+2))*(2/3

输出2

1
No
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
95
96
97
98
99
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAX_SIZE 100

// 定义顺序栈结构
typedef struct {
    char data [MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s-> top = -1;
}

// 判断栈是否为空
bool isEmpty(Stack *s) {
    return s-> top == -1;
}

// 判断栈是否已满
bool isFull(Stack *s) {
    return s-> top == MAX_SIZE - 1;
}

// 入栈操作
bool push(Stack *s, char c) {
    if (isFull(s)) {
        return false;
    }
    s-> data [++(s-> top)] = c;
    return true;
}

// 出栈操作
bool pop(Stack *s) {
    if (isEmpty(s)) {
        return false;
    }
    s-> top--;
    return true;
}

// 获取栈顶元素
char getTop(Stack *s) {
    if (isEmpty(s)) {
        return '\0';
    }
    return s-> data [s-> top];
}

// 检查括号是否匹配
bool checkBrackets(const char *expr) {
    Stack stack;
    initStack(&stack);
    
    for (int i = 0; expr [i] != '\0'; i++) {
        // 遇到左括号，入栈
        if (expr [i] == '(') {
            if (! push(&stack, '(')) {
                return false;  // 栈满，表达式过长
            }
        }
        // 遇到右括号，检查是否有匹配的左括号
        else if (expr [i] == ')') {
            if (isEmpty(&stack)) {
                return false;  // 没有匹配的左括号
            }
            pop(&stack);
        }
    }
    
    // 检查是否所有左括号都有匹配的右括号
    return isEmpty(&stack);
}

int main() {
    char expr [MAX_SIZE];
    
    // 读取表达式
    if (fgets(expr, MAX_SIZE, stdin) != NULL) {
        // 移除换行符
        size_t len = strlen(expr);
        if (len > 0 && expr [len-1] == '\n') {
            expr [len-1] = '\0';
        }
        
        // 检查括号匹配并输出结果
        if (checkBrackets(expr)) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    
    return 0;
}

2: 回文链表

描述

“回文”指正读反读均相同的字符序列，如“abcdcba”和“abba”均是回文，使用栈这种数据结构判断给定字符序列是否为回文，要求使用链栈实现。

输入

一个字符序列，字符序列长度≤1000

输出

输出为true/false，分别表示输入的字符序列是否为回文

样例

输入

1
2
abcda

输出

1
false
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

// 链栈节点结构
struct StackNode {
    char data;
    struct StackNode* next;
};

// 链栈结构
typedef struct {
    struct StackNode* top;
} LinkStack;

// 初始化链栈
void initStack(LinkStack* s) {
    s-> top = NULL;
}

// 判断栈是否为空
bool isEmpty(LinkStack* s) {
    return s-> top == NULL;
}

// 入栈操作
bool push(LinkStack* s, char c) {
    struct StackNode * node = (struct StackNode*)malloc(sizeof(struct StackNode));
    if (node == NULL) {
        return false;  // 内存分配失败
    }
    
    node-> data = c;
    node-> next = s-> top;
    s-> top = node;
    return true;
}

// 出栈操作并返回栈顶元素
char pop(LinkStack* s) {
    if (isEmpty(s)) {
        return '\0';
    }
    
    struct StackNode* temp = s-> top;
    char data = temp-> data;
    s-> top = temp-> next;
    free(temp);
    return data;
}

// 释放栈内存
void freeStack(LinkStack* s) {
    while (! isEmpty(s)) {
        pop(s);
    }
}

// 判断字符串是否为回文
bool isPalindrome(const char* str) {
    int len = strlen(str);
    int mid = len / 2;
    LinkStack stack;
    initStack(&stack);
    
    // 将前半部分字符入栈
    for (int i = 0; i < mid; i++) {
        if (! push(&stack, str [i])) {
            freeStack(&stack);
            return false;
        }
    }
    
    // 如果字符串长度为奇数，跳过中间字符
    int start = (len % 2 == 0) ? mid : mid + 1;
    
    // 比较后半部分字符与栈中字符
    for (int i = start; i < len; i++) {
        if (isEmpty(&stack) || pop(&stack) != str [i]) {
            freeStack(&stack);
            return false;
        }
    }
    
    bool result = isEmpty(&stack);
    freeStack(&stack);
    return result;
}

int main() {
    char str [1001];  // 多一个位置存储字符串结束符'\0'
    
    // 读取输入字符串
    if (fgets(str, sizeof(str), stdin) != NULL) {
        // 移除换行符
        size_t len = strlen(str);
        if (len > 0 && str [len-1] == '\n') {
            str [len-1] = '\0';
        }
        
        // 判断是否为回文并输出结果
        if (isPalindrome(str)) {
            printf("true\n");
        } else {
            printf("false\n");
        }
    }
    
    return 0;
}

3: 入栈与出栈

描述

给定一个正整数数列（以0表示输入结束），从第一个数开始，将每一个数入栈，入栈的同时获得一个分数，即该数的数值乘以入栈后栈的大小，请计算将所有元素入栈后的分数和，然后将栈内元素依次输出，要求使用顺序栈。元素个数<100，每个元素<100。

输入

一行，一个正整数数列，以0结尾。

输出

两行，第一行为一个正整数，表示分数和。

第二行为将所有元素出栈后的结果，空格分隔

输入输出样例

输入

1
2
5 4 3 2 1 0

输出

1
2
35
1 2 3 4 5
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
#include <stdio.h>
#define MAXSIZE 100

// 定义顺序栈
typedef struct {
    int data [MAXSIZE];
    int top;
} Stack;

// 初始化栈
void InitStack(Stack *S) {
    S-> top = -1;
}

// 入栈
void Push(Stack *S, int x) {
    if (S-> top < MAXSIZE - 1) {
        S-> data [++S-> top] = x;
    }
}

// 出栈
int Pop(Stack *S) {
    if (S-> top >= 0) {
        return S-> data [S-> top--];
    }
    return -1;
}

int main() {
    Stack s;
    InitStack(&s);

    int num, score = 0;

    // 读取数据并入栈，同时计算分数
    while (1) {
        scanf("%d", &num);
        if (num == 0) break;
        Push(&s, num);
        score += num * (s.top + 1);
    }

    // 输出分数
    printf("%d\n", score);

    // 直接输出逆序（原栈中 top 在高位，先出就是后输入）
    while (s.top >= 0) {
        printf("%d", Pop(&s));
        if (s.top >= 0) printf(" ");
    }
    printf("\n");

    return 0;
}

4: 点击消除

描述

给定一个字符串，每次“点击”，可以把字符串中相邻两个相同字母消除，例如，字符串”abbc”点击后可以生成”ac”。但相同而不相邻、不相同的相邻字母都是不可以被消除的。

通过点击足够多次之后可以把字符串变得尽可能短，编程实现输出给定字符串足够多次点击后的最终形态。

输入

一个字符串，仅由小写字母组成。（字符串长度不大于10000）

输出

一个字符串，为“点击消除”后的最终形态。若最终的字符串为空串，则输出0。

输入输出样例

输入

1
2
abbc

输出

1
ac
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
#include <stdio.h>
#include <string.h>

#define MAX_SIZE 10001

// 使用数组模拟栈
typedef struct {
    char data [MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s-> top = -1;
}

// 入栈
void push(Stack* s, char c) {
    s-> data [++s-> top] = c;
}

// 出栈
char pop(Stack* s) {
    if (s-> top >= 0) {
        return s-> data [s-> top--];
    }
    return '\0';
}

// 获取栈顶元素
char peek(Stack* s) {
    if (s-> top >= 0) {
        return s-> data [s-> top];
    }
    return '\0';
}

// 判断栈是否为空
int isEmpty(Stack* s) {
    return s-> top == -1;
}

int main() {
    char str [MAX_SIZE];
    Stack stack;
    
    // 初始化栈
    initStack(&stack);
    
    // 读取输入字符串
    scanf("%s", str);
    int len = strlen(str);
    
    // 遍历字符串
    for (int i = 0; i < len; i++) {
        // 如果栈为空或栈顶元素与当前字符不同，则入栈
        if (isEmpty(&stack) || peek(&stack) != str [i]) {
            push(&stack, str [i]);
        } else {
            // 如果相同，则弹出栈顶元素（消除相邻相同字符）
            pop(&stack);
        }
    }
    
    // 如果栈为空，输出 0
    if (isEmpty(&stack)) {
        printf("0\n");
        return 0;
    }
    
    // 将结果存入临时数组并反转
    char result [MAX_SIZE];
    int resultLen = 0;
    
    while (! isEmpty(&stack)) {
        result [resultLen++] = pop(&stack);
    }
    
    // 输出结果（需要反转）
    for (int i = resultLen - 1; i >= 0; i--) {
        printf("%c", result [i]);
    }
    printf("\n");
    
    return 0;
}

5: 周末舞会

描述

假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。

输入

第一行两个正整数，表示男士人数 mm 和女士人数 nn，1≤m,n≤10001≤m,n≤1000；

第二行一个正整数，表示舞曲的数目 kk，k≤1000k≤1000。

输出

共 kk 行，每行两个数，之间用一个空格隔开，表示配对舞伴的序号，男士在前，女士在后。

样例

输入

1
2
3
2 4
6

输出

1
2
3
4
5
6
1 1
2 2
1 3
2 4
1 1
2 2
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
#include <stdio.h>
#define MAX_SIZE 1001

// 循环队列结构
typedef struct {
    int data [MAX_SIZE];
    int front;  // 队头指针
    int rear;   // 队尾指针
    int size;   // 当前队列大小
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    q-> front = 0;
    q-> rear = 0;
    q-> size = 0;
}

// 入队
void enqueue(Queue* q, int value) {
    if (q-> size < MAX_SIZE) {
        q-> data [q-> rear] = value;
        q-> rear = (q-> rear + 1) % MAX_SIZE;
        q-> size++;
    }
}

// 出队
int dequeue(Queue* q) {
    if (q-> size > 0) {
        int value = q-> data [q-> front];
        q-> front = (q-> front + 1) % MAX_SIZE;
        q-> size--;
        return value;
    }
    return -1;
}

// 获取队头元素但不出队
int peek(Queue* q) {
    if (q-> size > 0) {
        return q-> data [q-> front];
    }
    return -1;
}

int main() {
    int m, n, k;
    Queue male, female;
    
    // 读取输入
    scanf("%d %d", &m, &n);
    scanf("%d", &k);
    
    // 初始化队列
    initQueue(&male);
    initQueue(&female);
    
    // 初始化男士队列
    for (int i = 1; i <= m; i++) {
        enqueue(&male, i);
    }
    
    // 初始化女士队列
    for (int i = 1; i <= n; i++) {
        enqueue(&female, i);
    }
    
    // 模拟 k 轮舞曲
    for (int i = 0; i < k; i++) {
        // 如果某个队列为空，重新填充队列
        if (male.size == 0) {
            for (int j = 1; j <= m; j++) {
                enqueue(&male, j);
            }
        }
        if (female.size == 0) {
            for (int j = 1; j <= n; j++) {
                enqueue(&female, j);
            }
        }
        
        // 配对并输出结果
        int man = dequeue(&male);
        int woman = dequeue(&female);
        printf("%d %d\n", man, woman);
    }
    
    return 0;
}

6: 无法吃午餐的学生数量

描述

学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮：

1.如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。

否则，这名学生会 放弃这个三明治 并回到队列的尾部。

2.这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。

输入两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 i个三明治的类型（i = 0 是栈的顶部）， students[j] 是初始队列里第 j名学生对三明治的喜好（j = 0 是队列的最开始位置）。请你返回无法吃午餐的学生数量。

输入

输入为两行，第一个行重数字表示学生对三明治的喜好（-1表示结束），第二个行中数字表示三明治的顺序（-1表示结束），数组中元素数量均<100

输出

输出为一个整数，表示无法吃午餐的学生的数量

输入输出样例

输入

1
2
3
1 1 1 0 0 1 -1
1 0 0 0 1 1 -1

输出

1
2
3

解释：

  • 最前面的学生拿走栈顶三明治离开，剩余学生队列为 [1,1,0,0,1]，三明治栈为 [0,0,0,1,1]；
  • 最前面学生放弃栈顶三明治，排到队尾，剩余学生队列为 [1,0,0,1,1]，三明治栈为 [0,0,0,1,1]；
  • 最前面学生放弃栈顶三明治，排到队尾，,剩余学生队列为 [1,0,0,1,1]，三明治栈为 [0,0,0,1,1]；
  • 最前面学生放弃栈顶三明治，排到队尾，,剩余学生队列为 [0,0,1,1,1]，三明治栈为 [0,0,0,1,1]；
  • 最前面的学生拿走栈顶三明治离开，剩余学生队列为 [0,1,1,1]，三明治栈为 [0,0,1,1]；
  • 最前面的学生拿走栈顶三明治离开，剩余学生队列为 [1,1,1]，三明治栈为 [0,1,1]；
  • 剩余三名学生无法吃到午饭
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

// 定义队列结构
typedef struct {
    int data [MAX_SIZE];
    int front, rear;
    int size;
} Queue;

// 定义栈结构
typedef struct {
    int data [MAX_SIZE];
    int top;
} Stack;

// 初始化队列
void initQueue(Queue* q) {
    q-> front = q-> rear = 0;
    q-> size = 0;
}

// 初始化栈
void initStack(Stack* s) {
    s-> top = -1;
}

// 入队
void enqueue(Queue* q, int value) {
    if (q-> size < MAX_SIZE) {
        q-> data [q-> rear] = value;
        q-> rear = (q-> rear + 1) % MAX_SIZE;
        q-> size++;
    }
}

// 出队
int dequeue(Queue* q) {
    if (q-> size > 0) {
        int value = q-> data [q-> front];
        q-> front = (q-> front + 1) % MAX_SIZE;
        q-> size--;
        return value;
    }
    return -1;
}

// 入栈
void push(Stack* s, int value) {
    if (s-> top < MAX_SIZE - 1) {
        s-> data [++s-> top] = value;
    }
}

// 获取栈顶元素
int peek(Stack* s) {
    if (s-> top >= 0) {
        return s-> data [s-> top];
    }
    return -1;
}

// 出栈
void pop(Stack* s) {
    if (s-> top >= 0) {
        s-> top--;
    }
}

int countStudents(Queue * students, Stack* sandwiches) {
    int count = 0;  // 记录连续不匹配的次数
    
    // 当队列不为空且没有陷入死循环时继续
    while (students-> size > 0 && count < students-> size) {
        int student = dequeue(students);
        
        // 如果学生喜好匹配栈顶三明治
        if (student == peek(sandwiches)) {
            pop(sandwiches);
            count = 0;  // 重置计数器
        } else {
            enqueue(students, student);
            count++;  // 增加不匹配计数
        }
    }
    
    return students-> size;  // 返回剩余学生数量
}

int main() {
    Queue students;
    Stack sandwiches;
    int val;
    
    initQueue(&students);
    initStack(&sandwiches);
    
    // 读取学生喜好
    while (1) {
        scanf("%d", &val);
        if (val == -1) break;
        enqueue(&students, val);
    }
    
    // 读取三明治顺序（需要临时存储以反转顺序）
    Stack tempStack;
    initStack(&tempStack);
    while (1) {
        scanf("%d", &val);
        if (val == -1) break;
        push(&tempStack, val);
    }
    
    // 将三明治正确顺序放入最终栈中
    while (tempStack.top >= 0) {
        push(&sandwiches, tempStack.data [tempStack.top]);
        tempStack.top--;
    }
    
    // 计算并输出结果
    int result = countStudents(&students, &sandwiches);
    printf("%d\n", result);
    
    return 0;
}

7: 栈的压入、弹出序列

描述

对输入的两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

  1. 栈中数据的数量≤10002. push 的所有数字均不相同

输入

输入为两行，每行包括一个数字序列，用空格隔开，-1结束。两个数字序列分别表示栈的压入顺序与弹出顺序

输出

输出为true/false表示第二个序列能否为该栈的弹出顺序

输入输出样例

输入

1
2
3
1 2 3 4 5 -1
4 5 3 2 1 -1

输出

1
true
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
95
96
97
98
99
100
101
102
103
104
#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 1001

// 定义栈结构
typedef struct {
    int data [MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s-> top = -1;
}

// 入栈操作
bool push(Stack* s, int value) {
    if (s-> top >= MAX_SIZE - 1) {
        return false;
    }
    s-> data [++s-> top] = value;
    return true;
}

// 出栈操作
bool pop(Stack* s) {
    if (s-> top < 0) {
        return false;
    }
    s-> top--;
    return true;
}

// 获取栈顶元素
int peek(Stack* s) {
    if (s-> top >= 0) {
        return s-> data [s-> top];
    }
    return -1;
}

// 判断栈是否为空
bool isEmpty(Stack* s) {
    return s-> top == -1;
}

// 读取序列
int readSequence(int sequence []) {
    int i = 0;
    int num;
    while (1) {
        scanf("%d", &num);
        if (num == -1) break;
        sequence [i++] = num;
    }
    return i;
}

// 判断是否为合法的弹出序列
bool isPopSequence(int * pushSeq, int* popSeq, int len) {
    Stack stack;
    initStack(&stack);
    
    int pushIndex = 0;  // 压入序列的当前位置
    int popIndex = 0;   // 弹出序列的当前位置
    
    // 模拟压栈和出栈过程
    while (pushIndex < len) {
        // 压入当前元素
        push(&stack, pushSeq [pushIndex]);
        
        // 当栈不为空且栈顶元素等于当前待弹出元素时
        while (! isEmpty(&stack) && peek(&stack) == popSeq [popIndex]) {
            pop(&stack);
            popIndex++;
        }
        
        pushIndex++;
    }
    
    // 检查是否所有元素都已正确弹出
    return isEmpty(&stack);
}

int main() {
    int pushSeq [MAX_SIZE];
    int popSeq [MAX_SIZE];
    
    // 读取压入序列
    int len = readSequence(pushSeq);
    
    // 读取弹出序列
    readSequence(popSeq);
    
    // 判断并输出结果
    if (isPopSequence(pushSeq, popSeq, len)) {
        printf("true\n");
    } else {
        printf("false\n");
    }
    
    return 0;
}

8: 循环队列

描述

请你实现一个循环队列，该循环队列可利用的空间大小等于n个int型变量的大小。

操作：

push x：将x加入到循环队列尾端。若循环队列已满，输出”full”(不含引号)，否则不输出任何内容。保证x为int型整数。

front：输出队首元素，队首不出队。若队列为空，输出”empty”(不含引号)。

pop：输出队首元素，且队首出队。若队列为空，输出”empty”(不含引号)

输入

第一行输入两个整数n,q (1≤n,q≤105)，表示循环队列可利用的空间大小和操作次数。

接下来的q行，每行一个字符串，表示一个操作。保证操作是题目描述 中的一种

输出

按照题目描述 中的要求输出

输入输出样例

输入

1
2
3
4
5
6
7
8
9
10
11
12
3 10
push 1
push 2
front
push 3
push 4
pop
pop
pop
front
pop

输出

1
2
3
4
5
6
7
1
full
1
2
3
empty
empty
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
95
96
97
98
99
100
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAX_SIZE 100001

// 循环队列结构
typedef struct {
    int data [MAX_SIZE];  // 存储数据的数组
    int front;           // 队首指针
    int rear;           // 队尾指针
    int size;           // 当前队列中的元素个数
    int capacity;       // 队列容量
} CircularQueue;

// 初始化循环队列
void initQueue(CircularQueue* q, int n) {
    q-> front = 0;
    q-> rear = 0;
    q-> size = 0;
    q-> capacity = n;
}

// 判断队列是否为空
bool isEmpty(CircularQueue* q) {
    return q-> size == 0;
}

// 判断队列是否已满
bool isFull(CircularQueue* q) {
    return q-> size == q-> capacity;
}

// 入队操作
bool push(CircularQueue* q, int value) {
    if (isFull(q)) {
        printf("full\n");
        return false;
    }
    
    q-> data [q-> rear] = value;
    q-> rear = (q-> rear + 1) % q-> capacity;
    q-> size++;
    return true;
}

// 获取队首元素但不出队
bool getFront(CircularQueue* q) {
    if (isEmpty(q)) {
        printf("empty\n");
        return false;
    }
    
    printf("%d\n", q-> data [q-> front]);
    return true;
}

// 出队操作
bool pop(CircularQueue* q) {
    if (isEmpty(q)) {
        printf("empty\n");
        return false;
    }
    
    printf("%d\n", q-> data [q-> front]);
    q-> front = (q-> front + 1) % q-> capacity;
    q-> size--;
    return true;
}

int main() {
    int n, q;
    CircularQueue queue;
    char operation [10];
    
    // 读取队列大小和操作次数
    scanf("%d %d", &n, &q);
    
    // 初始化队列
    initQueue(&queue, n);
    
    // 处理每个操作
    for (int i = 0; i < q; i++) {
        scanf("%s", operation);
        
        if (strcmp(operation, "push") == 0) {
            int x;
            scanf("%d", &x);
            push(&queue, x);
        }
        else if (strcmp(operation, "front") == 0) {
            getFront(&queue);
        }
        else if (strcmp(operation, "pop") == 0) {
            pop(&queue);
        }
    }
    
    return 0;
}

9: 最长有效括号

描述

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度

输入

输入为一个只包含 ‘(’ 和 ‘)’ 的字符串，字符串长度<10000。

输出

输出为一个数字，表示最长有效括号子串的长度

输入输出样例

输入

1
2
(()

输出

1
2
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
#include <stdio.h>
#include <string.h>

#define MAX_SIZE 10000

// 定义栈结构
typedef struct {
    int data [MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s-> top = -1;
}

// 入栈
void push(Stack* s, int value) {
    if (s-> top < MAX_SIZE - 1) {
        s-> data [++s-> top] = value;
    }
}

// 出栈
int pop(Stack* s) {
    if (s-> top >= 0) {
        return s-> data [s-> top--];
    }
    return -1;
}

// 判断栈是否为空
int isEmpty(Stack* s) {
    return s-> top == -1;
}

// 获取最长有效括号子串长度
int longestValidParentheses(char* s) {
    int len = strlen(s);
    Stack stack;
    initStack(&stack);
    
    // 将-1 压入栈底，作为边界标记
    push(&stack, -1);
    
    int maxLen = 0;
    
    for (int i = 0; i < len; i++) {
        if (s [i] == '(') {
            // 遇到左括号，将其下标入栈
            push(&stack, i);
        } else {
            // 遇到右括号，先弹出栈顶
            pop(&stack);
            
            if (isEmpty(&stack)) {
                // 如果栈空，说明当前右括号不能匹配，将其下标入栈作为新的边界
                push(&stack, i);
            } else {
                // 计算当前有效括号串的长度
                int currentLen = i - stack.data [stack.top];
                // 更新最大长度
                if (currentLen > maxLen) {
                    maxLen = currentLen;
                }
            }
        }
    }
    
    return maxLen;
}

int main() {
    char s [MAX_SIZE];
    
    // 读取输入字符串
    scanf("%s", s);
    
    // 计算并输出结果
    int result = longestValidParentheses(s);
    printf("%d\n", result);
    
    return 0;
}

10: 找出游戏的获胜者

描述

共有 n 名小伙伴一起做游戏。小伙伴们围成一圈，按 顺时针顺序 从 1 到 n 编号。确切地说，从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置，其中 1 <= i < n ，从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。

游戏遵循如下规则：

  • 从第 1 名小伙伴所在位置 开始 。
  • 沿着顺时针方向数 k 名小伙伴，计数时需要 包含 起始时的那位小伙伴。逐个绕圈进行计数，一些小伙伴可能会被数过不止一次。
  • 你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏。
  • 如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始，回到步骤 2 继续执行
  • 否则，圈子中最后一名小伙伴赢得游戏。

给你参与游戏的小伙伴总数 n ，和一个整数 k ，返回游戏的获胜者。

输入

输入为两个整数，n和k(1≤k≤n≤500)

输出

输出游戏的获胜者

输入输出样例

输入

1
2
5 2

输出

1
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
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 <stdio.h>
#include <stdlib.h>

// 定义循环链表节点结构
typedef struct Node {
    int number;         // 小伙伴编号
    struct Node* next;  // 指向下一个节点
} Node;

// 创建循环链表
Node* createCircularList(int n) {
    Node* head = NULL;
    Node* tail = NULL;
    
    // 创建 n 个节点
    for (int i = 1; i <= n; i++) {
        Node * newNode = (Node*)malloc(sizeof(Node));
        newNode-> number = i;
        newNode-> next = NULL;
        
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail-> next = newNode;
            tail = newNode;
        }
    }
    
    // 将尾节点指向头节点，形成循环
    if (tail != NULL) {
        tail-> next = head;
    }
    
    return head;
}

// 找出游戏获胜者
int findWinner(int n, int k) {
    if (n == 1) return 1;
    
    // 创建循环链表
    Node* head = createCircularList(n);
    Node* current = head;
    Node* prev = NULL;
    
    // 游戏进行直到只剩一个人
    while (current-> next != current) {
        // 数 k-1 次，因为当前位置已经算一次
        for (int i = 1; i < k; i++) {
            prev = current;
            current = current-> next;
        }
        
        // 删除当前节点
        if (prev == NULL) {
            // 如果是第一个节点
            Node* last = current;
            while (last-> next != current) {
                last = last-> next;
            }
            head = current-> next;
            last-> next = head;
        } else {
            prev-> next = current-> next;
        }
        
        // 释放被删除的节点
        Node* temp = current;
        current = current-> next;
        free(temp);
    }
    
    // 获取获胜者编号
    int winner = current-> number;
    
    // 释放最后一个节点
    free(current);
    
    return winner;
}

int main() {
    int n, k;
    
    // 读取输入
    scanf("%d %d", &n, &k);
    
    // 计算并输出获胜者
    int winner = findWinner(n, k);
    printf("%d\n", winner);
    
    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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
typedef struct TreeNode {
    int value;                 // 节点权值
    struct TreeNode* left;     // 左子树指针
    struct TreeNode* right;    // 右子树指针
} TreeNode;

// 创建新节点
TreeNode* createNode(int value) {
    TreeNode * newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode-> value = value;
    newNode-> left = NULL;
    newNode-> right = NULL;
    return newNode;
}

// 递归计算左子树权值和
int sumOfLeftSubtree(TreeNode* root) {
    if (root == NULL) {
        return 0; // 空节点返回 0
    }
    int leftSum = sumOfLeftSubtree(root-> left); // 左子树权值和
    int rightSum = sumOfLeftSubtree(root-> right); // 计算右子树，虽然不加到结果，但避免遗漏子树遍历
    return leftSum + root-> value; // 加上当前节点的值
}

// 主函数
int main() {
    // 创建一个二叉树示例
    TreeNode* root = createNode(10);
    root-> left = createNode(5);
    root-> right = createNode(15);
    root-> left-> left = createNode(3);
    root-> left-> right = createNode(7);

    // 计算左子树权值和
    int leftSubtreeSum = sumOfLeftSubtree(root-> left);
    printf("左子树权值和: %d\n", leftSubtreeSum);

    // 释放内存
    free(root-> left-> left);
    free(root-> left-> right);
    free(root-> left);
    free(root-> right);
    free(root);

    return 0;
}

串 数组和广义表

1.数组与串-小鱼的数字游戏

题目描述

小鱼最近被要求参加一个数字游戏，要求它把看到的一串数字 a_i（长度不一定，以 00 结束），记住了然后反着念出来（表示结束的数字 00 就不要念出来了）。这对小鱼的那点记忆力来说实在是太难了，你也不想想小鱼的整个脑袋才多大，其中一部分还是好吃的肉！所以请你帮小鱼编程解决这个问题。

题目难度 简单

输入描述

一行内输入一串整数，以 00 结束，以空格间隔。

输出描述

一行内倒着输出这一串整数，以空格间隔。

输入输出样例

输入

3 65 23 5 34 1 30 0

输出

30 1 34 5 23 65 3

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

int main() {
    int arr [1000]; // 假设最多有 1000 个数字
    int n = 0;
    int x;
    while (1) {
        scanf("%d", &x);
        if (x == 0) break; // 以 0 结束，0 不计入
        arr [n++] = x;
    }
    for (int i = n - 1; i >= 0; i--) {
        printf("%d", arr [i]);
        if (i > 0) printf(" ");
    }
    printf("\n");
    return 0;
}

2.数组与串-N皇后 (回溯算法 代码回想录 困难)

题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

输入描述

输入一个数组

输出描述

输出方案总数

输入输出样例

输入：n = 4

输出：2

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
#include <stdio.h>
#include <stdlib.h>
#define N 20       //皇后的数量
int q [N];          //各行皇后所在的列
int count = 0;     //统计 N 皇后问题解的个数

//输出 N 皇后问题的解决方案
void print(int n)
{
    int i, j;
    count++;
    printf("第%d 个解：\n", count);
    for (i = 1; i <= n; i++)        //行
    {
        for (j = 1; j <= n; j++)   //列
        {
            if (q [i] != j)
                printf("x");
            else
                printf("Q");
        }
        printf("\n");
    }
    printf("\n");
}
//检验第 k 行第 j 列上是否可以摆放皇后
int isSafe(int k, int j)
{
    int i;
    for (i = 1; i < k; i++) {
        //如果有其它皇后位置同一列上，或者位于该位置的斜线位置上，则该位置无法使用
        if (q [i] == j || abs(i - k) == abs(q [i] - j))
            return 0;
    }
    return 1;
}
//放置皇后到棋盘上
void n_queens(int k, int n)
{
    int j;
    if (k > n)     //递归的出口
        print(n);
    else
    {
        for (j = 1; j <= n; j++)   //试探第 k 行的每一列，找到符合要求的列
        {
            if (isSafe(k, j))
            {
                q [k] = j;
                n_queens(k + 1, n);  //在确认第 k 行皇后位置的前提下，继续测试下一行皇后的位置
            }
        }
    }
}

int main()
{
    int n;
    printf("请输入皇后个数：");
    scanf("%d", &n);
    n_queens(1, n);
    printf("共有 %d 种不同的排列", count);
    return 0;
}

3.数组与串-小鱼比可爱

题目描述

人比人，气死人；鱼比鱼，难死鱼。小鱼最近参加了一个“比可爱”比赛，比的是每只鱼的可爱程度。参赛的鱼被从左到右排成一排，头都朝向左边，然后每只鱼会得到一个整数数值，表示这只鱼的可爱程度，很显然整数越大，表示这只鱼越可爱，而且任意两只鱼的可爱程度可能一样。由于所有的鱼头都朝向左边，所以每只鱼只能看见在它左边的鱼的可爱程度，它们心里都在计算，在自己的眼力范围内有多少只鱼不如自己可爱呢。请你帮这些可爱但是鱼脑不够用的小鱼们计算一下。

输入描述

第一行输入一个正整数 nn，表示鱼的数目。

第二行内输入 n个正整数，用空格间隔，依次表示从左到右每只小鱼的可爱程度 a_i。

输出描述

一行，输出 n 个整数，用空格间隔，依次表示每只小鱼眼中有多少只鱼不如自己可爱。

输入输出样例

输入：

6

4 3 0 5 1 2

输出：

0 0 0 3 1 2

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 <stdio.h>
#include <string.h>

int main()
{
  int n;
  scanf("%d", &n);
  int arr [n];
  int a [n];
  memset(a, 0, sizeof(a [0]) * n);
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr [i]);
    for (int j = 0; j < i; j++)
    {
      if (arr [i] > arr [j])
        a [i]++;

    }
    printf("%d", a [i]);
    if (i == n-1)
      break;
    printf(" ");
  }
  return 0;
}

4: 数组与串-杨辉三角

题目描述

给出 n(n≤20)，输出杨辉三角的前 n 行。

如果你不知道什么是杨辉三角，可以观察样例找找规律。

输入描述

输入一个数字阶数

输出描述

输出杨辉三角

输入输出样例

输入: 6

输出:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int tri [21][21] = {0}; // 因为 n <= 20，开到 21 即可

    for (int i = 0; i < n; i++) {
        tri [i][0] = tri [i][i] = 1; // 每行的第一个和最后一个都是 1
        for (int j = 1; j < i; j++) {
            tri [i][j] = tri [i-1][j-1] + tri [i-1][j];
        }
    }
    // 输出
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            printf("%d", tri [i][j]);
            if (j != i) printf(" ");
        }
        printf("\n");
    }
    return 0;
}

4: 数组与串-冰雹猜想

题目描述

给出一个正整数 n，然后对这个数字一直进行下面的操作：如果这个数字是奇数，那么将其乘 3 再加 1，否则除以 2。经过若干次循环后，最终都会回到 1。经过验证很大的数字（7*10^{11}）都可以按照这样的方式比变成 1，所以被称为“冰雹猜想”。例如当 n 是 2020，变化的过程是20→10→5→16→8→4→2→1。

输入描述

输入一个正整数 n。

输出描述

输出若干个由空格隔开的正整数，表示从最后的 1 开始倒序的变化数列。

输入输出样例

输入：20

输出：1 2 4 8 16 5 10 20

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 <stdio.h>

int main() {
    int n;
    scanf("%d", &n);        // 读入初始数字
    int arr [1000];          // 存储变化过程的数组
    int cnt = 0;            // 计数器，记录数列长度
    
    // 当数字不为 1 时继续循环
    while (n != 1) {
        arr [cnt++] = n;     // 保存当前数字
        if (n % 2 == 0)     // 偶数时除以 2
            n = n / 2;
        else                // 奇数时乘 3 加 1
            n = n * 3 + 1;
    }
    arr [cnt++] = 1;         // 最后加入 1
    
    // 倒序输出
    for (int i = 0; i < cnt; i++) {
        printf("%d", arr [cnt - 1 - i]);
        if (i != cnt - 1) printf(" ");  // 除了最后一个数字，其他后面都加空格
    }
    printf("\n");
    return 0;
}

5: 数组与串-液晶屏

题目描述

液晶屏上，每个阿拉伯数字都是可以显示成 3×5 的点阵的（其中 X 表示亮点，. 表示暗点）。现在给出数字位数（不超过 100）和一串数字，要求输出这些数字在显示屏上的效果。数字的显示方式如同样例输出，注意每个数字之间都有一列间隔。

输入描述

第一行输入一个正整数 n，表示数字的位数。

第二行输入一个长度为 n 的自然数

输出描述

输出五行，表示显示屏上的数字。

有些同学反应看不懂，这里观察一下就知道了

每个数字是一个3×5的矩阵

每个数字之间用一个1×5的.相隔

这里输出有点显示字符占位不一样，导致显示问题。

这里我添加一张图片方便大家观察

输入输出样例

输入：

1
2
3
10
0123456789

输出：

1
2
3
4
5
6
XXX...X.XXX.XXX.X.X.XXX.XXX.XXX.XXX.XXX
X.X...X...X...X.X.X.X...X.....X.X.X.X.X
X.X...X.XXX.XXX.XXX.XXX.XXX...X.XXX.XXX
X.X...X.X.....X...X...X.X.X...X.X.X...X
XXX...X.XXX.XXX...X.XXX.XXX...X.XXX.XXX

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
#include <stdio.h>
#include <string.h>

const char *lcd [10][5] = {
    {"XXX", "X.X", "X.X", "X.X", "XXX"}, // 0
    {"..X", "..X", "..X", "..X", "..X"}, // 1
    {"XXX", "..X", "XXX", "X..", "XXX"}, // 2
    {"XXX", "..X", "XXX", "..X", "XXX"}, // 3
    {"X.X", "X.X", "XXX", "..X", "..X"}, // 4
    {"XXX", "X..", "XXX", "..X", "XXX"}, // 5
    {"XXX", "X..", "XXX", "X.X", "XXX"}, // 6
    {"XXX", "..X", "..X", "..X", "..X"}, // 7
    {"XXX", "X.X", "XXX", "X.X", "XXX"}, // 8
    {"XXX", "X.X", "XXX", "..X", "XXX"}  // 9
};

int main() {
    int n;
    char digits [110];
    scanf("%d", &n);
    scanf("%s", digits);

    for (int row = 0; row < 5; row++) {
        for (int i = 0; i < n; i++) {
            printf("%s", lcd [digits[i] - '0'][row]);
            // 每个数字之间输出一个点列，最后一个数字后不输出
            if (i != n - 1) printf(".");
        }
        printf("\n");
    }
    return 0;
}

树与二叉树

1: 相同的树

输出格式:

输入

p = [1,2,3], q = [1,2,3]

输出

true

输入

p = [1,2], q = [1,null,2]

输出

false

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

// 二叉树定义
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 判断两棵树是否相同
bool isSameTree(struct TreeNode * p, struct TreeNode* q) {
    if (! p && ! q) return true;
    if (! p || ! q) return false;
    if (p-> val != q-> val) return false;
    return isSameTree(p-> left, q-> left) && isSameTree(p-> right, q-> right);
}

// 去除字符串前后空白和方括号
void trim(char* s) {
    int len = strlen(s);
    while (len > 0 && (s [len-1] =='\n'||s [len-1]=='\r'||s [len-1] ==' '||s [len-1]==']')) s [--len] = 0;
    int i = 0;
    while (s [i] == ' ' || s [i] == '[') ++i;
    if (i) memmove(s, s+i, len-i+1);
}

// 分割字符串，获取 token 数量
int split(char* line, char tokens [][10]) {
    int n = 0;
    char* p = strtok(line, ",");
    while (p) {
        while (*p == ' ') ++p;
        strcpy(tokens [n++], p);
        p = strtok(NULL, ",");
    }
    return n;
}

// 根据层序数组构建二叉树
struct TreeNode* buildTree(char tokens [][10], int n) {
    if (n == 0) return NULL;
    struct TreeNode* nodes [n];
    for (int i = 0; i < n; ++i) {
        if (strcmp(tokens [i], "null") == 0) nodes [i] = NULL;
        else {
            nodes [i] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
            nodes [i]-> val = atoi(tokens [i]);
            nodes [i]-> left = nodes [i]-> right = NULL;
        }
    }
    int pos = 1;
    for (int i = 0; i < n && pos < n; ++i) {
        if (nodes [i]) {
            if (pos < n) nodes[i]-> left = nodes [pos++];
            if (pos < n) nodes[i]-> right = nodes [pos++];
        }
    }
    return nodes [0];
}

int main() {
    char line1 [256], line2 [256];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);

    trim(line1);
    trim(line2);

    char tokens1 [100][10], tokens2 [100][10];
    int n1 = split(line1, tokens1);
    int n2 = split(line2, tokens2);

    struct TreeNode* p = buildTree(tokens1, n1);
    struct TreeNode* q = buildTree(tokens2, n2);

    if (isSameTree(p, q)) printf("true\n");
    else printf("false\n");
    return 0;
}

2: 二叉树的中序遍历

给你一个二叉树的根节点root，检查它是否轴对称。

输入描述

一个节点序列

输出描述

真假

输入输出样例

输入

root = [1,2,2,3,4,4,3]

输出

true

输入

root = [1,2,2,null,3,null,3]

输出

false

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

// 二叉树节点结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 判断两棵子树是否互为镜像
bool isMirror(struct TreeNode * t1, struct TreeNode* t2) {
    if (! t1 && ! t2) return true;
    if (! t1 || ! t2) return false;
    if (t1-> val != t2-> val) return false;
    return isMirror(t1-> left, t2-> right) && isMirror(t1-> right, t2-> left);
}

// 检查二叉树是否轴对称
bool isSymmetric(struct TreeNode* root) {
    if (! root) return true;
    return isMirror(root-> left, root-> right);
}

// 去除字符串前后空白和方括号
void trim(char* s) {
    int len = strlen(s);
    while (len > 0 && (s [len-1] =='\n'||s [len-1]=='\r'||s [len-1] ==' '||s [len-1]==']')) s [--len] = 0;
    int i = 0;
    while (s [i] == ' ' || s [i] == '[') ++i;
    if (i) memmove(s, s+i, len-i+1);
}

// 分割字符串，获取 token 数量
int split(char* line, char tokens [][10]) {
    int n = 0;
    char* p = strtok(line, ",");
    while (p) {
        while (*p == ' ') ++p;
        strcpy(tokens [n++], p);
        p = strtok(NULL, ",");
    }
    return n;
}

// 根据层序数组构建二叉树
struct TreeNode* buildTree(char tokens [][10], int n) {
    if (n == 0) return NULL;
    struct TreeNode* nodes [n];
    for (int i = 0; i < n; ++i) {
        if (strcmp(tokens [i], "null") == 0) nodes [i] = NULL;
        else {
            nodes [i] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
            nodes [i]-> val = atoi(tokens [i]);
            nodes [i]-> left = nodes [i]-> right = NULL;
        }
    }
    int pos = 1;
    for (int i = 0; i < n && pos < n; ++i) {
        if (nodes [i]) {
            if (pos < n) nodes[i]-> left = nodes [pos++];
            if (pos < n) nodes[i]-> right = nodes [pos++];
        }
    }
    return nodes [0];
}

int main() {
    char line [256];
    fgets(line, sizeof(line), stdin);

    // 去掉“root = ”或其他前缀
    char *p = strchr(line, '[');
    if (! p) p = line;
    trim(p);

    char tokens [100][10];
    int n = split(p, tokens);

    struct TreeNode* root = buildTree(tokens, n);

    if (isSymmetric(root)) printf("true\n");
    else printf("false\n");
    return 0;
}

3: 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

输入描述：

一个节点序列

输出描述：

返回其根节点序列

样例

输入

root = [4,2,7,1,3,6,9]

输出

[4,7,2,9,6,3,1]

输入

root = [2,1,3]

输出

[2,3,1]

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#define _CRT_SECURE_NO_WARNINGS 
#include <iostream>
#include <queue>
#include <cstring>
#include <climits>
constexpr int MAXLEN = 10000;
using namespace std;

typedef struct Tnode {
    int data;
    struct Tnode * left = NULL, * right = NULL;
}Tnode, * Tree;

void changeStringToArray(char * str, int* array, int * arrayLength, int* nodenum) {
    int length = 0;
    char* token = strtok(str, ",");
    while (token != NULL) {
        if (strcmp(token, "null") == 0) {
            array [length++] = INT_MIN;
        }
        else {
            array [length++] = atoi(token);
            (*nodenum)++;
        }
        token = strtok(NULL, ",");
    }
    *arrayLength = length;
    int i = 0;
}

Tnode * buildTree(int* arr, int arrlen) {
    if (arrlen == 0) return NULL;
    Tnode* root = new Tnode;
    root-> data = arr [0];
    queue <Tnode*> q;
    q.push(root);
    int i = 1;
    while (! q.empty() && i < arrlen) {
        Tnode* cur = q.front();
        q.pop();
        if (i < arrlen && arr [i] != INT_MIN) {
            cur-> left = new Tnode;
            cur-> left-> data = arr [i];
            q.push(cur-> left);
        }
        i++;
        if (i < arrlen && arr [i] != INT_MIN) {
            cur-> right = new Tnode;
            cur-> right-> data = arr [i];
            q.push(cur-> right);
        }
        i++;
    }
    return root;
}

void swap(Tree T) {
    if (T == NULL) {
        return;
    }
    Tnode* temp = T-> left;
    T-> left = T-> right;
    T-> right = temp;
    swap(T-> left);
    swap(T-> right);
}

void levelprint(Tree T, int arrlen) {
    if (T == NULL || arrlen == 0) return;
    queue <Tnode*> tree;
    queue <int> output;
    tree.push(T);
    int i = 0;
    while (! tree.empty() && i < arrlen) {
        Tnode* t = tree.front();
        tree.pop();
        if (t == NULL) {
            output.push(INT_MIN);
        }
        else {
            output.push(t-> data);
            tree.push(t-> left);
            tree.push(t-> right);
            i++;
        }
    }
    while (! output.empty()) {
        if (output.front() == INT_MIN) {
            cout << "null";
        }
        else {
            cout << output.front();
        }
        output.pop();
        if (! output.empty()) {
            cout << ',';
        }
    }
}

int main() {
    char str [MAXLEN];
    cin >> str;
    int arr [MAXLEN];
    int arrlen, nodenum = 0;
    changeStringToArray(str, arr, &arrlen,&nodenum);
    Tree T;
    T = buildTree(arr, arrlen);
    swap(T);
    levelprint(T, nodenum);
    return 0;
}

4: 左叶子之和

题目描述

给定二叉树的根节点 root ，返回所有左叶子之和。

输入描述

一个节点序列

输出描述

返回其左叶子之和

输入输出样例

输入

root = [3,9,20,null,null,15,7]

输出

24

输入

root = [1]

输出

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
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
95
96
97
98
99
100
101
102
103
104
105
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 二叉树节点结构
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 判断是否为左叶子节点
bool isLeaf(struct TreeNode* node) {
    return node && ! node-> left && ! node-> right;
}

// 计算左叶子之和
int sumOfLeftLeaves(struct TreeNode* root) {
    if (! root) return 0;
    int sum = 0;
    
    // 如果左子节点是叶子节点，加入和
    if (isLeaf(root-> left)) {
        sum += root-> left-> val;
    }
    
    // 递归处理左右子树
    sum += sumOfLeftLeaves(root-> left);
    sum += sumOfLeftLeaves(root-> right);
    
    return sum;
}

// 辅助函数：构建二叉树
struct TreeNode* createNode(int value) {
    struct TreeNode * node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node-> val = value;
    node-> left = node-> right = NULL;
    return node;
}

// 处理输入字符串
void trim(char* s) {
    int len = strlen(s);
    while (len > 0 && (s [len-1] == '\n' || s [len-1] == '\r' || s [len-1] == ' ' || s [len-1] == ']')) 
        s [--len] = 0;
    int i = 0;
    while (s [i] == ' ' || s [i] == '[') ++i;
    if (i) memmove(s, s+i, len-i+1);
}

// 分割字符串
int split(char* line, char tokens [][10]) {
    int n = 0;
    char* p = strtok(line, ",");
    while (p) {
        while (*p == ' ') ++p;
        strcpy(tokens [n++], p);
        p = strtok(NULL, ",");
    }
    return n;
}

// 根据层序遍历数组构建二叉树
struct TreeNode* buildTree(char tokens [][10], int n) {
    if (n == 0) return NULL;
    
    struct TreeNode* nodes [n];
    for (int i = 0; i < n; i++) {
        if (strcmp(tokens [i], "null") == 0) {
            nodes [i] = NULL;
        } else {
            nodes [i] = createNode(atoi(tokens [i]));
        }
    }
    
    int pos = 1;
    for (int i = 0; i < n && pos < n; i++) {
        if (nodes [i]) {
            if (pos < n) nodes[i]-> left = nodes [pos++];
            if (pos < n) nodes[i]-> right = nodes [pos++];
        }
    }
    
    return nodes [0];
}

int main() {
    char line [256];
    fgets(line, sizeof(line), stdin);
    
    char* p = strchr(line, '[');
    if (! p) p = line;
    trim(p);
    
    char tokens [100][10];
    int n = split(p, tokens);
    
    struct TreeNode* root = buildTree(tokens, n);
    
    printf("%d\n", sumOfLeftLeaves(root));
    
    return 0;
}

5: 最小高度树

题目描述

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

输入描述

一个有序整数数组

输出描述

高度最小的二叉搜索树

输入输出样例

输入

root = [-10,-3,0,5,9]

输出

[0,-3,9,-10,null,5]

输入

root = [1]

输出

[1]

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
#define _CRT_SECURE_NO_WARNINGS 
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <climits>
constexpr int MAXLEN = 10000;
using namespace std;

typedef struct Tnode {
    int data;
    struct Tnode * left = NULL, * right = NULL;
} Tnode, * Tree;

void changeStringToArray(char* str, vector <int>& array) {
    char* token = strtok(str, ",");
    while (token != NULL) {
        if (strcmp(token, "null") == 0) {
            array.push_back(INT_MIN);
        }
        else {
            array.push_back(atoi(token));
        }
        token = strtok(NULL, ",");
    }
}
//二分法
Tnode* build(vector <int>& nums, int left, int right) {
    if (left > right) return NULL;
    int mid = left + (right - left+1) / 2;
    Tnode* root = new Tnode;
    root-> data = nums [mid];
    root-> left = build(nums, left, mid - 1);
    root-> right = build(nums, mid + 1, right);
    return root;
}

void levelprint(Tree T, int arrlen) {
    if (T == NULL || arrlen == 0) return;
    queue <Tnode*> tree;
    queue <int> output;
    tree.push(T);
    int i = 0;
    while (! tree.empty() && i < arrlen) {
        Tnode* t = tree.front();
        tree.pop();
        if (t == NULL) {
            output.push(INT_MIN);
        }
        else {
            output.push(t-> data);
            tree.push(t-> left);
            tree.push(t-> right);
            i++;
        }
    }
    while (! output.empty()) {
        if (output.front() == INT_MIN) {
            cout << "null";
        }
        else {
            cout << output.front();
        }
        output.pop();
        if (! output.empty()) {
            cout << ',';
        }
    }
}

int main() {
    char str [MAXLEN];
    cin.getline(str, MAXLEN);
    vector <int> arr;
    changeStringToArray(str, arr);
    int arrlen = arr.size();
    Tree T = build(arr, 0, arrlen - 1);
    levelprint(T, arrlen);
    return 0;
}

6: 填充每个节点的下一个右侧节点指针

题目描述 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {

int val;

Node *left;

Node *right;

Node *next;

}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

输入描述

给一个完美二叉树

输出描述

输出填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

输入输出样例

输入

root = [1,2,3,4,5,6,7]

输出

[1,#,2,3,#,4,5,6,7,#]

输入

root = []

输出

[]

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
95
96
97
98
99
100
101
102
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cstdlib>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
};
Node* BuildTree(vector <string> vec);
void _Print(Node* L);
int main(){
    vector <string> vec;
    char c;
    string s;
    while(1){
        c = cin.get();
        if(c ==','){
            vec.push_back(s);
            s.clear();
        }else if(c =='\n'){
            
            if(! s.empty())vec.push_back(s);
            break;
        }else{
            s+= c;
        }
    }
    Node* L;
    L = BuildTree(vec);
    _Print(L);
    return 0;
}
Node* BuildTree(vector <string> vec){
    queue <Node*> Q;
    Node* L = new Node;
    if(vec.size()== 0)return 0;
    L-> val = atoi(vec [0].c_str());
    L-> left = L-> right = 0;
    Q.push(L);
    Node* p;
    int i = 1;
    while(i < vec.size()){
        p = Q.front();
        Q.pop();
        while(! p){
            i+= 2;
            p = Q.front();
            Q.pop(); 
            for(int j = 0; j < 2; j++){
                Q.push(0);
            }
        }
        if(vec [i] == "#"){
            p-> left = 0;
            Q.push(0);
        }else{
            Node* t = new Node;
            t-> val = atoi(vec [i].c_str());
            t-> left = t-> right = 0;
            p-> left = t;
            Q.push(t);
        }
        i++;
        if(i >= vec.size())break;
        if(vec [i] == "#"){
            p-> right = 0;
            Q.push(0);
        }else{
            Node* t = new Node;
            t-> val = atoi(vec [i].c_str());
            t-> left = t-> right = 0;
            p-> right = t;
            Q.push(t);
        }
        i++;
    }
    return L;
}
void _Print(Node* L){
    if(L == 0)return;
    queue <Node*> Q;
    Q.push(L);
    int flag = 0;
    while(! Q.empty()){
        Node* p;
        int a = Q.size();
        for(int i = 0; i < a; i++){
            p = Q.front();
            Q.pop();
            if(flag)cout << ",";
            else flag = 1;
            cout <<p-> val;
            if(p-> left)Q.push(p-> left);
            if(p-> right)Q.push(p-> right);
        }
        cout << "," << "#";
    }
}

7: 二叉树的最近公共祖先

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

（一个节点也可以是它自己的祖先）。

输入描述

给一个二叉树

输出描述

输出它的最近公共近邻

输入输出样例

输入

root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

输出

3

输入

root = [1,2], p = 1, q = 2

输出

1

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
#define _CRT_SECURE_NO_WARNINGS 
#include <iostream>
#include <cstring>
#include <vector>
#include <climits>
constexpr int MAXLEN = 10000;
using namespace std;

void changeStringToArray(char * str, int* array, int* arrayLength) {
    int length = 1;//跳过 index = 0
    char* token = strtok(str, ",");
    while (token != NULL) {
        if (strcmp(token, "null") == 0) {
            array [length++] = INT_MIN;
        }
        else {
            array [length++] = atoi(token);
        }
        token = strtok(NULL, ",");
    }
    *arrayLength = length-1;
    int i = 0;
}

int find_zuxian(int* arr, int arrlen, int p, int q) {
    int indexp, indexq;
    for (int i = 1; i <= arrlen; i++) {
        if (arr [i] == p) {
            indexp = i;
        }
        if (arr [i] == q) {
            indexq = i;
        }
    }
    vector <int> plist, qlist;
    plist.push_back(arr [indexp]), qlist.push_back(arr [indexq]);
    while (indexp > 0) {
        indexp /= 2;
        plist.push_back(arr [indexp]);
    }
    while (indexq > 0) {
        indexq /= 2;
        qlist.push_back(arr [indexq]);
    }
    int res = 0;
    bool flag = false;
    for (int i = 0; (i < plist.size())&&(! flag) ; i++) {
        for (int k = 0; k < qlist.size(); k++) {
            if (plist [i] == qlist [k]) {
                res = plist [i];
                flag = true;
            }
        }
    }
    return res;
}

int main() {
    char str [MAXLEN];
    cin >> str;
    int arr [MAXLEN];
    int arrlen = 0;
    changeStringToArray(str, arr, &arrlen);
    int p, q;
    cin >> p >> q;
    cout << find_zuxian(arr, arrlen, p, q)<< endl;
    return 0;
}

8: 恢复二叉搜索树

题目描述

给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

输入描述

给一个二叉树

输出描述

恢复这棵树

输入输出样例

输入

root = [1,3,null,null,2]

输出

[3,1,null,null,2]

输入

Root = [3,1,4,null,null,2]

输出

[2,1,4,null,null,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
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#define _CRT_SECURE_NO_WARNINGS 
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <climits>
constexpr int MAXLEN = 10000;
using namespace std;

typedef struct Tnode {
    int data;
    struct Tnode * left = NULL, * right = NULL;
} Tnode, * Tree;

void changeStringToArray(char * str, int* array, int* arrayLength) {
    int length = 0;
    char* token = strtok(str, ",");
    while (token != NULL) {
        if (strcmp(token, "null") == 0) {
            array [length++] = -1;
        }
        else {
            array [length++] = atoi(token);
        }
        token = strtok(NULL, ",");
    }
    *arrayLength = length;
}

Tnode * buildTree(int* arr, int arrlen) {
    if (arrlen == 0) return NULL;
    Tnode* root = new Tnode;
    root-> data = arr [0];
    queue <Tnode*> q;
    q.push(root);
    int i = 1;
    while (! q.empty() && i < arrlen) {
        Tnode* cur = q.front();
        q.pop();
        if (i < arrlen && arr [i] != -1) {
            cur-> left = new Tnode;
            cur-> left-> data = arr [i];
            q.push(cur-> left);
        }
        i++;
        if (i < arrlen && arr [i] != -1) {
            cur-> right = new Tnode;
            cur-> right-> data = arr [i];
            q.push(cur-> right);
        }
        i++;
    }
    return root;
}

void inorder(Tree T, vector <int>& list) {
    if (T == NULL) return;
    inorder(T-> left, list);
    list.push_back(T-> data);
    inorder(T-> right, list);
}

void modify(Tree T, int indexm, int indexn, int m, int n, int* j) {
    if (T == NULL) return;
    modify(T-> left, indexm, indexn, m, n, j);
    (*j)++;
    if (*j == indexm) {
        T-> data = n;
    }
    else if (*j == indexn) {
        T-> data = m;
    }
    modify(T-> right, indexm, indexn, m, n, j);
}

void levelprint(Tree T, int arrlen) {
    if (T == NULL||arrlen== 0) return; 
    queue <Tnode*> tree;
    queue <int> output;
    tree.push(T);
    int i = 0;
    while (! tree.empty()&&i < arrlen) {
        Tnode* t = tree.front();
        tree.pop();
        if (t == NULL) {
            output.push(-1);
        }
        else {
            output.push(t-> data);
            tree.push(t-> left);
            tree.push(t-> right);
        }
        i++;
    }
    while (! output.empty()) {
        if (output.front() == -1) {
            cout << "null";
        }
        else {
            cout << output.front();
        }
        output.pop();
        if (! output.empty()) {
            cout << ',';
        }
    }
}

int main() {
    char str [MAXLEN];
    cin.getline(str, MAXLEN);
    int arr [MAXLEN];
    int arrlen;
    changeStringToArray(str, arr, &arrlen);
    Tree T = buildTree(arr, arrlen);
    vector <int> list;
    inorder(T, list);
    int first = -1, second = -1;
    for (int i = 0; i < list.size() - 1; i++) {
        if (list [i] > list [i + 1]) {
            if (first == -1) {
                first = i;      
                second = i + 1; 
            }
            else {
                second = i + 1; 
            }
        }
    }
    if (first != -1 && second != -1) {
        int j = 0;
        modify(T, first + 1, second + 1, list [first], list [second], &j);
    }
    levelprint(T, arrlen);
    return 0;
}

9: 奇偶数

题目描述

如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：

二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。

偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增

奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减

给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。

输入描述

给一个二叉树

输出描述

判断是否是奇偶树

输入输出样例

输入

root = [1,10,4,3,null,7,9,12,8,6,null,null,2]

输出

true

输入

root = [2,1,3]

输出

false

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAXN 2005

struct TreeNode {
    int val;
    struct TreeNode *left, * right;
};

// 用于层序遍历队列
struct TreeNode* queue [MAXN];
int front, rear;

// 创建新节点
struct TreeNode* newNode(int v) {
    struct TreeNode * node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node-> val = v;
    node-> left = node-> right = NULL;
    return node;
}

// 处理输入字符串，构建二叉树（层序输入，null 用-1 表示）
struct TreeNode * buildTree(char* s) {
    int vals [MAXN], n = 0;
    char* token = strtok(s, "[,]");
    while (token) {
        while (*token == ' ') ++token;
        if (strcmp(token, "null") == 0) vals [n++] = -1;
        else vals [n++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    if (n == 0 || vals [0] == -1) return NULL;
    struct TreeNode* nodes [MAXN];
    for (int i = 0; i < n; ++i)
        nodes [i] = (vals [i] == -1 ? NULL : newNode(vals [i]));
    int pos = 1;
    for (int i = 0; i < n && pos < n; ++i) {
        if (nodes [i]) {
            if (pos < n) nodes[i]-> left = nodes [pos++];
            if (pos < n) nodes[i]-> right = nodes [pos++];
        }
    }
    return nodes [0];
}

// 判断是否为奇偶树
bool isEvenOddTree(struct TreeNode* root) {
    if (! root) return true;
    front = rear = 0;
    queue [rear++] = root;
    int level = 0;
    while (front < rear) {
        int sz = rear - front;
        int prev = (level % 2 == 0) ? 0 : 0x7fffffff;
        for (int i = 0; i < sz; ++i) {
            struct TreeNode* node = queue [front++];
            int v = node-> val;
            // 偶数层：奇数且递增
            if (level % 2 == 0) {
                if (v % 2 == 0) return false;
                if (i > 0 && v <= prev) return false;
            } else { // 奇数层：偶数且递减
                if (v % 2 == 1) return false;
                if (i > 0 && v >= prev) return false;
            }
            prev = v;
            if (node-> left) queue [rear++] = node-> left;
            if (node-> right) queue [rear++] = node-> right;
        }
        level++;
    }
    return true;
}

int main() {
    char line [1000];
    fgets(line, sizeof(line), stdin);
    char *p = strchr(line, '[');
    if (! p) p = line;
    struct TreeNode* root = buildTree(p);
    printf(isEvenOddTree(root) ? "true\n" : "false\n");
    return 0;
}

10: 二叉树的子树大小

描述

现在给出一棵二叉树，希望你输出它的每一个结点为根的子树大小

输入

第一行一个正整数 n，表示给定的树的节点的数目，规定节点编号 1∼n，其中节点 1是树根。

接下来 n 行，每行两个正整数 li, ri ，分别表示节点 i 的左右孩子的编号。如果不存在左 / 右孩子，则以 −1 表示。两个数之间用一个空格隔开。

输出

一行，n个数，分别表示i号结点为根的子树的子树大小

样例

输入

1
2
3
4
5
3
2 3
-1 -1
-1 -1

输出

1
3 1 1
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 <stdio.h>

#define MAXN 100005

int lch [MAXN], rch [MAXN], sz [MAXN];
int n;

// 递归计算以 u 为根的子树大小
int dfs(int u) {
    if (u == -1) return 0;
    int cnt = 1;
    cnt += dfs(lch [u]);
    cnt += dfs(rch [u]);
    sz [u] = cnt;
    return cnt;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &lch [i], &rch [i]);
    }
    dfs(1);
    for (int i = 1; i <= n; ++i) {
        if (i > 1) printf(" ");
        printf("%d", sz [i]);
    }
    printf("\n");
    return 0;
}

11: 二叉树的子树和

描述

现在给出一棵二叉树，每个结点有一个权值，希望你依次输出每一个节点为根的子树的子树权值和

输入

第一行一个正整数 n，表示给定的树的节点的数目，规定节点编号 1∼n，其中节点 1是树根。

第二行 n 个正整数，用一个空格分隔，第 i 个正整数vi，代表节点 i 的权值。

接下来 n 行，每行两个正整数 li, ri ，分别表示节点 i 的左右孩子的编号。如果不存在左 / 右孩子，则以 −1 表示。两个数之间用一个空格隔开。

输出

一行，n个数，分别表示i号结点为根的子树的子树权值和

样例

输入

1
2
3
4
5
6
3
1 1000 1000
2 3
-1 -1
-1 -1

输出

1
2001 1000 1000
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
#include <stdio.h>
#include <stdlib.h>

#define MAXN 100005

int n;
int val [MAXN];
int lch [MAXN], rch [MAXN];
int ans [MAXN];

// 递归计算以 u 为根的子树和
int dfs(int u) {
    if (u == -1) return 0;
    int sum = val [u];
    sum += dfs(lch [u]);
    sum += dfs(rch [u]);
    ans [u] = sum;
    return sum;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &val [i]);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &lch [i], &rch [i]);
    }
    dfs(1);
    for (int i = 1; i <= n; ++i) {
        if (i > 1) printf(" ");
        printf("%d", ans [i]);
    }
    printf("\n");
    return 0;
}

12: 确定树的形态

描述

现在给出一棵二叉树的前序遍历和后序遍历，输出树的后序遍历

输入

第一行一个正整数 n，表示给定的树的节点的数目，规定节点编号 1∼n，其中节点 1是树根。

第二行 n 个正整数，用一个空格分隔，代表二叉树的前序遍历

第三行 n 个正整数，用一个空格分隔，代表二叉树的中序遍历

输出

一行，n个数，用一个空格分隔，表示二叉树的后序遍历

样例

输入

1
2
3
4
3
1 2 3
2 1 3

输出

1
2 3 1
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
#include <stdio.h>
#include <stdlib.h>

#define MAXN 1005

int preorder [MAXN], inorder [MAXN], postorder [MAXN];
int n, postidx;

// 递归重建二叉树并填充后序遍历
void build_postorder(int preL, int preR, int inL, int inR) {
    if (preL > preR) return;
    int root = preorder [preL];
    int i;
    // 在中序中找到根的位置
    for (i = inL; i <= inR; ++i) {
        if (inorder [i] == root) break;
    }
    int left_size = i - inL;
    // 左子树
    build_postorder(preL + 1, preL + left_size, inL, i - 1);
    // 右子树
    build_postorder(preL + left_size + 1, preR, i + 1, inR);
    // 填充后序
    postorder [postidx++] = root;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &preorder [i]);
    for (int i = 0; i < n; ++i) scanf("%d", &inorder [i]);
    postidx = 0;
    build_postorder(0, n-1, 0, n-1);
    for (int i = 0; i < n; ++i) {
        if (i) printf(" ");
        printf("%d", postorder [i]);
    }
    printf("\n");
    return 0;
}

13: 哈夫曼叔的带权路径长

描述

现在给出一棵二叉树，每个结点有一个权值，希望你构造赫夫曼树，并输出其对应的带权路径长度

输入

第一行一个正整数 n，表示给定的树的节点的数目，规定节点编号 1∼n。

第二行 n 个正整数，用一个空格分隔，第 i 个正整数vi，代表节点 i 的权值。

输出

一个数，表示对应赫夫曼树的带权路径长度

样例

输入

1
2
3
3
1 1000 1000

输出

1
3002
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
#include <stdio.h>
#include <stdlib.h>

#define MAXN 10005

// 小顶堆实现
typedef struct {
    int data [MAXN];
    int size;
} MinHeap;

void swap(int * a, int* b) {
    int t = *a; * a = *b; * b = t;
}

void heapify_up(MinHeap* h, int idx) {
    while (idx > 1 && h-> data [idx] < h-> data [idx/2]) {
        swap(&h-> data [idx], &h-> data [idx/2]);
        idx /= 2;
    }
}

void heapify_down(MinHeap* h, int idx) {
    int smallest = idx;
    int l = idx * 2, r = idx * 2 + 1;
    if (l <= h-> size && h-> data [l] < h-> data [smallest]) smallest = l;
    if (r <= h-> size && h-> data [r] < h-> data [smallest]) smallest = r;
    if (smallest != idx) {
        swap(&h-> data [idx], &h-> data [smallest]);
        heapify_down(h, smallest);
    }
}

void heap_push(MinHeap* h, int x) {
    h-> data [++h-> size] = x;
    heapify_up(h, h-> size);
}

int heap_pop(MinHeap* h) {
    int res = h-> data [1];
    h-> data [1] = h-> data [h-> size--];
    heapify_down(h, 1);
    return res;
}

int main() {
    int n;
    scanf("%d", &n);
    MinHeap heap = {.size = 0};

    for (int i = 0; i < n; ++i) {
        int v;
        scanf("%d", &v);
        heap_push(&heap, v);
    }

    int wpl = 0;
    while (heap.size > 1) {
        int a = heap_pop(&heap);
        int b = heap_pop(&heap);
        wpl += a + b;
        heap_push(&heap, a + b);
    }
    printf("%d\n", wpl);
    return 0;
}

串

1: A-B数对

描述

给出一串单调不下降的数以及一个数字 C，要求计算出所有A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入

输入共两行。

第一行，两个整数 N,C。

第二行，N个整数，作为要求处理的那串数。

输出

一行，表示该串数中包含的满足A−B=C 的数对的个数。

样例

输入

1
2
3
4 1
1 1 2 3

输出

1
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
#include <stdio.h>

#define MAXN 100000

int main() {
    int N, C;
    scanf("%d%d", &N, &C);
    int arr [MAXN];
    int cnt [200001] = {0};  // 假设输入数据不会超过 [-1e5,1e5]
    int base = 100000;      // 把负数映射到正数下标

    for (int i = 0; i < N; i++) {
        scanf("%d", &arr [i]);
        cnt [arr[i] + base]++;
    }

    int ans = 0;
    for (int i = 0; i < N; i++) {
        int b = arr [i] - C + base;
        if (b >= 0 && b <= 200000)
            ans += cnt [b];
    }

    printf("%d\n", ans);
    return 0;
}

2: 普通二叉树

描述

您需要写一种数据结构，来维护一些数（都是 1e9 以内的数字）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数 q 不超过 104：

  1. 查询值为x的数的排名（排名定义为比当前数小的数的个数 +1。若有多个相同的数，应输出最小的排名）。
  2. 查询排名为 x 的数。
  3. 求 x 的前驱（前驱定义为小于 x，且最大的数）。若未找到则输出−2147483647。
  4. 求 x 的后继（后继定义为大于 x，且最小的数）。若未找到则输出 2147483647。
  5. 插入一个数 x。
  6. 输入

第一行是一个整数 q，表示操作次数。

接下来 q 行，每行两个整数 op,x，分别表示操作序号以及操作的参数 x。

输出

输出有若干行。对于操作 1,2,3,4输出一个整数，表示该操作的结果。

样例

输入

1
2
3
4
5
6
7
8
9
7
5 1
5 3
5 5
1 3
2 2
3 3
4 3

输出

1
2
3
4
2
3
1
5

3: 队列安排

描述

一个学校里老师要将班上 N 个同学排成一列，同学被编号为1∼N，他采取如下的方法：

先将 1 号同学安排进队列，这时队列中只有他一个人；

2-N 号同学依次入列，编号为 i 的同学入列方式为：老师指定编号为 i 的同学站在编号为 1∼(i−1) 中某位同学（即之前已经入列的同学）的左边或右边；

最后，从队列中去掉 M(M<N） 个同学，其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。

输入

第 1 行为一个正整数 N，表示了有 N 个整数。

第 2∼N行，第 i 行包含两个整数 k,p，其中 k 为小于i 的正整数，p 为 0 或者 1。若 p 为0，则表示将 i 号同学插入到 k 号同学的左边，p 为 1 则表示插入到右边。

第 N+1 行为一个正整数 M，表示去掉的同学数目。

接下来 M行，每行一个正整数 x，表示将 x 号同学从队列中移去，如果 x 号同学已经不在队列中则忽略这一条指令。

输出

1 行，包含最多 N 个空格隔开的正整数，表示了队列从左到右所有同学的编号，行末换行且无空格。

样例

输入

1
2
3
4
5
6
7
8
4
1 0
2 1
1 0
2
3
3

输出

1
2 4 1
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
#include <stdio.h>
#define MAXN 100010

int left [MAXN], right [MAXN]; // 双向链表
int removed [MAXN];           // 标记是否被移除

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) left [i] = right [i] = 0;
    // 初始化 1 号同学，两端都是 0
    left [1] = right [1] = 0;

    for (int i = 2; i <= N; i++) {
        int k, p;
        scanf("%d%d", &k, &p);
        if (p == 0) {
            // 插入到 k 左边：l <-> k <-> r，变为 l <-> i <-> k <-> r
            left [i] = left [k];
            right [i] = k;
            if (left [k]) right [left[k]] = i;
            left [k] = i;
        } else {
            // 插入到 k 右边：l <-> k <-> r，变为 l <-> k <-> i <-> r
            right [i] = right [k];
            left [i] = k;
            if (right [k]) left [right[k]] = i;
            right [k] = i;
        }
    }

    // 删除操作
    int M, x;
    scanf("%d", &M);
    for (int i = 0; i < M; i++) {
        scanf("%d", &x);
        if (removed [x]) continue;
        if (left [x]) right [left[x]] = right [x];
        if (right [x]) left [right[x]] = left [x];
        removed [x] = 1;
    }

    // 找到最左端
    int head = 1;
    while (left [head]) head = left [head];

    // 输出
    int first = 1;
    for (int i = head; i > 0; i = right [i]) {
        if (! removed [i]) {
            if (! first) printf(" ");
            printf("%d", i);
            first = 0;
        }
    }
    printf("\n");
    return 0;
}

4: 明明的随机数

描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N个 1到 1000 之间的随机整数 （N<=100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入

输入有两行，第 1 行为 1 个正整数，表示所生成的随机数的个数 N。

第 2 行有 N个用空格隔开的正整数，为所产生的随机数。

输出

输出也是两行，第 1 行为 1 个正整数 M，表示不相同的随机数的个数。

第 2 行为 M 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

样例

输入

1
2
3
10
20 40 32 67 40 20 89 300 400 15

输出

1
2
8
15 20 32 40 67 89 300 400
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
#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void * b) {
    return *(int*)a - *(int*)b;
}

int main() {
    int N, arr [100], res [100], cnt = 0;
    int exist [1001] = {0}; // 标记 1~1000 是否出现

    scanf("%d", &N);
    for(int i = 0; i < N; i++) {
        int x;
        scanf("%d", &x);
        if (! exist [x]) {
            arr [cnt++] = x;
            exist [x] = 1;
        }
    }

    // 排序
    qsort(arr, cnt, sizeof(int), cmp);

    printf("%d\n", cnt);
    for(int i = 0; i < cnt; i++) {
        if (i) printf(" ");
        printf("%d", arr [i]);
    }
    printf("\n");
    return 0;
}

5: 奖学金

描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 5 名学生发奖学金。期末，每个学生都有 3 门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学 排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的 3 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前 5 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是:

7 279

5 279

这两行数据的含义是:总分最高的两个同学的学号依次是 7 号、5 号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为 7 的学生语文成绩更高一些。如果你的前两名的输出数据是:

5 279

7 279

则按输出错误处理，不能得分。

输入

共 n+1行。

第 1 行为一个正整数n（n≤300)，表示该校参加评选的学生人数。

第 2 到 n+1 行，每行有 3 个用空格隔开的数字，每个数字都在 0 到 100之间。第 j行的 3 个数字依次表示学号为 j-1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 1~n（恰好是输入数据的行号减 1）。

输出

共 5 行，每行是两个用空格隔开的正整数，依次表示前 5 名学生的学号和总分。

样例

输入1

1
2
3
4
5
6
7
8
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

输出1

1
2
3
4
5
6
6 265
4 264
3 258
2 244
1 237

输入2

1
2
3
4
5
6
7
8
9
10
8
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

输出2

1
2
3
4
5
8 265
2 264
6 264
1 258
5 258
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 <stdio.h>
#include <stdlib.h>

typedef struct {
    int id;     // 学号
    int sum;    // 总分
    int chinese;// 语文
} Student;

int cmp(const void *a, const void * b) {
    Student *x = (Student*)a;
    Student *y = (Student*)b;
    if (x-> sum != y-> sum) return y-> sum - x-> sum;        // 总分高优先
    if (x-> chinese != y-> chinese) return y-> chinese - x-> chinese; // 语文高优先
    return x-> id - y-> id;                                // 学号小优先
}

int main() {
    int n;
    scanf("%d", &n);
    Student stu [305];
    for (int i = 1; i <= n; ++i) {
        int c, m, e;
        scanf("%d%d%d", &c, &m, &e);
        stu [i-1].id = i;
        stu [i-1].chinese = c;
        stu [i-1].sum = c + m + e;
    }
    qsort(stu, n, sizeof(Student), cmp);
    for (int i = 0; i < 5; ++i)
        printf("%d %d\n", stu [i].id, stu [i].sum);
    return 0;
}

6: 纪念品分组

描述

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入

共 n+2行：

第一行包括一个整数 w，为每组纪念品价格之和的上限。

第二行为一个整数 n，表示购来的纪念品的总件数 G。

第 3 ∼n+2 行每行包含一个正整数 Pi 表示所对应纪念品的价格。

输出

一个整数，即最少的分组数目。

样例

输入

1
2
3
4
5
6
7
8
9
10
11
12
100
9
90
20
20
30
50
60
70
80
90

输出

1
6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void * b) {
    return *(int*)a - *(int*)b;
}

int main() {
    int w, n, p [30010];
    scanf("%d%d", &w, &n);
    for (int i = 0; i < n; ++i) scanf("%d", &p [i]);
    qsort(p, n, sizeof(int), cmp);
    int i = 0, j = n - 1, ans = 0;
    while (i <= j) {
        if (p [i] + p [j] <= w) i++; // 可以两件一组
        j--; // 最重的那件一定要发出去
        ans++;
    }
    printf("%d\n", ans);
    return 0;
}

7: 统计数字

描述

某次科研调查时得到了n个自然数，每个数均不超过1500000000(1.5×109

)。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

共n+1行。

第一行是整数n，表示自然数的个数；

第2至n+1每行一个自然数。

输出

共m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。

每行输出2个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

样例

输入

1
2
3
4
5
6
7
8
9
10
8
2
4
2
4
5
100
2
100

输出

1
2
3
4
2 3
4 2
5 1
100 2
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
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int num;
    int cnt;
} Item;

int cmp(const void * a, const void* b) {
    Item * x = (Item*)a;
    Item * y = (Item*)b;
    if (x-> num < y-> num) return -1;
    if (x-> num > y-> num) return 1;
    return 0;
}

int main() {
    int n;
    scanf("%d", &n);
    Item arr [10005];
    int size = 0;

    for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        int found = 0;
        for (int j = 0; j < size; ++j) {
            if (arr [j].num == x) {
                arr [j].cnt++;
                found = 1;
                break;
            }
        }
        if (! found) {
            arr [size].num = x;
            arr [size].cnt = 1;
            size++;
        }
    }

    qsort(arr, size, sizeof(Item), cmp);

    for (int i = 0; i < size; ++i)
        printf("%d %d\n", arr [i].num, arr [i].cnt);

    return 0;
}

8: 分数线划定

描述

世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的 150% 划定，即如果计划录取 m 名志愿者，则面试分数线为排名第 m ×150%（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。

输入

第一行，两个整数 n,m(5≤n≤5000,3≤m≤n)，中间用一个空格隔开，其中 n 表示报名参加笔试的选手总数，m 表示计划录取的志愿者人数。输入数据保证 m ×150% 向下取整后小于等于 n。

第二行到第 n+1行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号 k(1000≤k≤9999)和该选手的笔试成绩 s(1≤s≤100)。数据保证选手的报名号各不相同。

输出

第一行，有 2 个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。

从第二行开始，每行包含 2 个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。

样例

输入

1
2
3
4
5
6
7
8
6 3
1000 90
3239 88
2390 95
7231 84
1005 95
1001 88

输出

1
2
3
4
5
6
88 5
1005 95
2390 95
1000 90
1001 88
3239 88
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>
#include <stdlib.h>

typedef struct {
    int id;
    int score;
} Student;

int cmp(const void * a, const void* b) {
    Student *x = (Student*)a, *y = (Student*)b;
    if (x-> score != y-> score) return y-> score - x-> score; // 分数高的在前
    return x-> id - y-> id; // 分数相同按报名号升序
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    Student stu [5005];
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &stu [i].id, &stu [i].score);
    }

    qsort(stu, n, sizeof(Student), cmp);

    int cut = (int)(m * 1.5);
    int line = stu [cut-1].score;

    // 统计进入面试人数
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (stu [i].score >= line) cnt++;
    }

    printf("%d %d\n", line, cnt);
    for (int i = 0; i < n; ++i) {
        if (stu [i].score >= line)
            printf("%d %d\n", stu [i].id, stu [i].score);
    }
    return 0;
}

9: 合并果子

描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n-1次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1 ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 3 种果子，数目依次为 1 ， 2 ， 9 。可以先将 1 、 2 堆合并，新堆数目为 3 ，耗费体力为 3 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12 ，耗费体力为 12 。所以多多总共耗费体力 =3+12=15 。可以证明 15 为最小的体力耗费值。

输入

共两行。

第一行是一个整数 n(1≤n≤10000) ，表示果子的种类数。

第二行包含 n 个整数，用空格分隔，第 i 个整数ai(1≤ai≤20000) 是第 i 种果子的数目。

输出

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 2e31

样例

输入

1
2
3
3
1 2 9

输出

1
15
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
#include <stdio.h>
#include <stdlib.h>

#define MAXN 10010

// 小根堆实现
int heap [MAXN], heap_size = 0;

void swap(int *a, int * b) {
    int t = *a; * a = *b; * b = t;
}

void push(int x) {
    heap [++heap_size] = x;
    int i = heap_size;
    while (i > 1 && heap [i] < heap [i/2]) {
        swap(&heap [i], &heap [i/2]);
        i /= 2;
    }
}

int pop() {
    int ret = heap [1];
    heap [1] = heap [heap_size--];
    int i = 1;
    while (1) {
        int l = i *2, r = i* 2+1, minp = i;
        if (l <= heap_size && heap [l] < heap [minp]) minp = l;
        if (r <= heap_size && heap [r] < heap [minp]) minp = r;
        if (minp == i) break;
        swap(&heap [i], &heap [minp]);
        i = minp;
    }
    return ret;
}

int main() {
    int n, a;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a);
        push(a);
    }

    long long ans = 0;
    for (int i = 1; i < n; ++i) { // n-1 次合并
        int x = pop();
        int y = pop();
        ans += x + y;
        push(x + y);
    }
    printf("%lld\n", ans);
    return 0;
}
≡