心双2024数据结构1001-1005题解-xiwwwix's blog

写在前面：因为本菜鸡水平比较有限，题解仅供参考~

一般使用C++语言（因为py被ban了，而且C太难用了2333），为了锻炼代码水平，medium及以下题目不使用STL，不过medium以上可能也不一定做得出来（？）

自认代码风格还凑合（不过大括号不换行，而且习惯万能头），不太爱写注释（有时可能会gpt帮忙生成一些）

如果有其他问题，请随时联系我修改~

1001. A+B Problem

(/ω＼)是一道A+B！

#include <bits/stdc++.h>

int main() {
	long long a,b;
	scanf("%lld %lld",&a,&b);
	printf("%lld",a+b);
	return 0;
}

1002. A+B Problem Templated

ψ(｀∇´)ψ是另一道A+B！
需要注意的是只需要完成函数的定义即可~

  class Solution {
public:
	/**
	* [完成A+B的计算]
	* @param  a [整数A]
	* @param  b [整数B]
	* @return   [A+B的值]
	*/
	int solve(int a, int b) {
		return a+b;
	}
};

1003. 数据结构开课啦

PPT上有答案，需要注意的是答案一行一个，提交的时候记得选择text作为语言

数据结构
数据结构
数据结构
树
存储
多
多对多

1004. 线性表插入删除操作

大的来了
题面略显抽象，没有给出q的范围，而且没有特意说明k是0索引还是1索引，只能说要求全靠脑补 + 根据样例猜

分析一下题目，发现主要的任务就是写两个函数，实现：

删除第k个元素
在第k个元素后面插入元素x

不难想到使用链表以保证删除和插入元素的效率，最坏情况下每次删除和插入的位置都在尾部，理论复杂度O(nq)

一些在写代码过程中的想法：
1.可以声明一个无意义的head结点，这样就可以把“删除第$k$个元素理解成“从head结点出发，移动k次后删除当前结点”，插入元素同理，降低思维和编码难度
2.注意读题，k有可能是不合法的，也即k大于当前链表长度，或者说遍历到结点不存在。所以在遍历删除和插入中，需要加入判断条件nowNode != NULL，防止越界
另一种更高效的方式是维护一个变量len用于保存链表长度，如果判断出len < k，则直接输出-1（删除）或者忽略（插入），这样还可以减少遍历的次数，运行时间应该会更短

以下是参考代码，使用kimi辅助生成了注释

#include <bits/stdc++.h>
using namespace std;

// 定义链表的节点结构
struct Node {
    int data; // 节点存储的数据
    Node* nextNode; // 指向下一个节点的指针
};

// 创建一个新的节点并初始化数据
Node* createNode(int num) {
    Node* newNode = new Node; // 使用 new 创建一个新的 Node 对象
    newNode->data = num; // 设置节点的数据
    newNode->nextNode = NULL; // 设置节点的下一个指针为 NULL
    return newNode; // 返回新创建的节点
}

// 初始化头节点，初始值为0
Node* head = createNode(0); 

// 删除操作
void Delete(int k) {
    Node* preNode = head; // 指向当前节点的前一个节点
    Node* nowNode = head; // 指向当前节点
    // 移动 nowNode 到第 k 个节点
    for (int i = 0; i < k && nowNode != NULL; i++) {
        preNode = nowNode;
        nowNode = nowNode->nextNode;
    }
    // 如果 nowNode 为 NULL，说明 k 超出了链表长度
    if (nowNode == NULL) {
        printf("%d\n", -1);
        return;
    }
    // 输出被删除的节点的数据
    printf("%d\n", nowNode->data);
    // 如果删除的是头节点
    if (nowNode == head) {
        head = head->nextNode; // 将头节点移动到下一个节点
    } else {
        // 否则，将前一个节点的 next 指向当前节点的下一个节点
        preNode->nextNode = nowNode->nextNode;
    }
    // 删除当前节点，释放内存
    delete nowNode;
}

// 插入操作
void Insert(int k, int x) {
    Node* nowNode = head; // 指向当前节点
    // 移动 nowNode 到第 k 个节点的前一个节点
    for (int i = 0; i < k && nowNode != NULL; i++) {
        nowNode = nowNode->nextNode;
    }
    // 创建一个新节点
    Node* newNode = createNode(x);
    // 如果 nowNode 为 NULL，说明插入位置在链表末尾
    if (nowNode == NULL) {
        newNode->nextNode = NULL;
    } else {
        // 将新节点插入到链表中
        newNode->nextNode = nowNode->nextNode;
    }
    // 将新节点链接到链表中
    if (nowNode == NULL) {
        head = newNode; // 如果插入到链表头部
    } else {
        nowNode->nextNode = newNode;
    }
}

// 主函数
int main() {
    int n, q, a;
    cin >> n; // 读取链表的长度
    Node* preNode = head; // 初始化前一个节点为头节点
    // 构建链表
    for (int i = 0; i < n; i++) {
        cin >> a; // 读取节点数据
        Node* node = createNode(a); // 创建新节点
        preNode->nextNode = node; // 将新节点链接到链表
        preNode = node; // 更新前一个节点为当前节点
    }
    cin >> q; // 读取操作的数量
    int cmd, k, x;
    // 执行操作
    for (int j = 0; j < q; j++) {
        cin >> cmd; // 读取操作命令
        if (cmd == 1) {
            cin >> k >> x; // 读取插入操作的参数
            Insert(k, x); // 执行插入操作
        } else if (cmd == 2) {
            cin >> k; // 读取删除操作的参数
            Delete(k); // 执行删除操作
        }
    }
    return 0;
}

其他小知识：在C++中可以用new代替malloc用于创建结构体哦！（￣︶￣）↗　

1005. 线性表的比较

省流：比较字典序

我的理解大致是这样的：从头开始比较相同位置i上A数组和B数组的值的大小，如果有不一样则直接返回结果；
如果一直比到较短的数组结束，两个数组目前所有位置上的数都一样，则较长的数组大
感觉这种理解方式比较好写好调

#include <bits/stdc++.h>

using namespace std;
int nums1[100003];
int nums2[100003]; 

int main() {
    int m,n; 
    int flag = 1; //定义一个标志变量flag，初始值为1，用来标记是否已经输出结果
    scanf("%d %d",&m,&n); 
    for (int i = 0; i < m; i++) { 
        scanf("%d",&nums1[i]);
    }
    for (int i = 0; i < n; i++) { 
        scanf("%d",&nums2[i]);
    }

    int point = 0; //定义一个变量point，用来记录当前比较的索引位置
    while (point < n && point < m) { //当point小于两组数字的长度时，进行循环比较
        if (nums1[point] < nums2[point]) { // 如果第一组数字在当前索引位置的值小于第二组
            printf("%d",-1); 
            flag = 0; // 设置flag为0，表示已经输出了结果
            break; //跳出循环，当然你如果直接return 0也可以
        } else if (nums1[point] > nums2[point]) { // 如果第一组数字在当前索引位置的值大于第二组
            printf("%d",1);
            flag = 0; // 设置flag为0，表示已经输出了结果
            break;
        }
        point++; // 如果两组数字在当前索引位置的值相等，增加索引
    }
    if (flag) { // 如果flag仍为1，说明没有在循环中输出结果
        if (n == m) { // 如果两组数字的个数相等
            printf("%d",0); 
        } else if (m > n) { // 如果第一组数字的个数大于第二组
            printf("%d",1); 
        } else { // 如果第一组数字的个数小于第二组
            printf("%d",-1); 
        }
    }
    return 0;
}

时间复杂度：瓶颈在读入，需要O(m+n)；最坏情况下，遍历到比较短的那个数组结束即可，O(min(m,n))