2.18日学习总结
题目一：
AC代码 ：
#include <stdio.h>
#include <stdlib.h>
// 构建操作序列的函数
char* b(int* t, int s, int n, int* rs) {
char* r = (char*)malloc((2 * n + 1) * sizeof(char));
int i = 0; // 结果数组的索引
int c = 1; // 当前从 list 中读取的数字
int j = 0; // 目标数组的索引
while (j < s) {
r[i++] = 'P';
if (t[j] == c) {
j++;
} else {
r[i++] = 'O';
}
c++;
}
r[i] = '\0';
*rs = i;
return r;
}
int main() {
int t1[] = {1, 3};
int n1 = 3;
int rs1;
char* r1 = b(t1, sizeof(t1) / sizeof(t1[0]), n1, &rs1);
printf("操作序列 1: %s\n", r1);
free(r1);
int t2[] = {1, 2, 3};
int n2 = 3;
int rs2;
char* r2 = b(t2, sizeof(t2) / sizeof(t2[0]), n2, &rs2);
printf("操作序列 2: %s\n", r2);
free(r2);
int t3[] = {1, 2};
int n3 = 4;
int rs3;
char* r3 = b(t3, sizeof(t3) / sizeof(t3[0]), n3, &rs3);
printf("操作序列 3: %s\n", r3);
free(r3);
return 0;
}题解：
我们有一个目标数组 target 和一个整数 n。存在一个从 1 到 n 的有序数字列表 list = {1, 2, 3, ..., n}。我们要从这个 list 里按顺序一个个取出数字，通过 “Push”（把数字放进数组）和 “Pop”（把数组里最后一个数字移除）这两个操作，来构建出目标数组 target。最后要输出完成这个构建过程所用到的操作序列。
1.思路
我们可以从 list 的第一个数字（也就是 1）开始，依次去尝试构建目标数组。每拿到一个数字，就先把它 “Push” 进数组。然后检查这个数字是不是目标数组里我们当前需要的数字，如果是，那就接着去构建目标数组的下一个数字；如果不是，就把刚 “Push” 进去的数字 “Pop” 出来，再去处理 list 里的下一个数字，直到成功构建出整个目标数组。
2.函数b
char* b(int* t, int s, int n, int* rs) {
char* r = (char*)malloc((2 * n + 1) * sizeof(char));
int i = 0; // 结果数组的索引
int c = 1; // 当前从 list 中读取的数字
int j = 0; // 目标数组的索引
while (j < s) {
r[i++] = 'P';
if (t[j] == c) {
j++;
} else {
r[i++] = 'O';
}
c++;
}
r[i] = '\0';
*rs = i;
return r;
} t：指向目标数组的指针，也就是我们要构建出来的数组。
s：目标数组的长度。
n：表示数字列表的上限，数字列表是从 1 到 n。
rs：一个指向整数的指针，用于存储最终操作序列的长度。
3.内存分配：
char* r = (char*)malloc((2 * n + 1) * sizeof(char)); 这里使用 malloc 函数为存储操作序列的字符数组 r 分配内存。2 * n + 1 是考虑到最坏情况下，每个数字都可能进行一次 "Push" 和一次 "Pop" 操作，再加上字符串结束符 '\0' 的空间。
4. 变量初始化：
i：用于记录结果数组 r 的当前索引位置，初始化为 0。
c：表示当前从数字列表 {1, 2, ..., n} 中读取的数字，初始化为 1。
j：目标数组 t 的当前索引，初始化为 0，从目标数组的第一个元素开始处理。
5. 循环
while (j < s) {
r[i++] = 'P';
if (t[j] == c) {
j++;
} else {
r[i++] = 'O';
}
c++;
}每次循环开始，先进行 "Push" 操作，将字符 'P' 存入结果数组 r 中，并将索引 i 加 1。
判断当前读取的数字 c 是否等于目标数组 t 中当前索引 j 对应的元素：
如果 相等，说明我们成功将目标数组中的一个元素构建出来了，将目标数组的索引 j 加 1，准备处理下一个元素。
如果不相等，说明这个数字不是我们当前需要的，那么就进行 "Pop" 操作，将字符 'O' 存入结果数组 r 中，并将索引 i 加 1。
无论是否进行 "Pop" 操作，都将当前读取的数字 c 加 1，去处理数字列表中的下一个数字。
6.字符串结束处理
r[i] = '\0';
*rs = i;
return r;在结果数组的末尾添加字符串结束符 '\0'，使其成为一个合法的 C 字符串。
通过指针 rs 更新操作序列的长度。
最后返回存储操作序列的字符数组指针 r。
7.主函数
int main() {
int t1[] = {1, 3};
int n1 = 3;
int rs1;
char* r1 = b(t1, sizeof(t1) / sizeof(t1[0]), n1, &rs1);
printf("操作序列 1: %s\n", r1);
free(r1);
int t2[] = {1, 2, 3};
int n2 = 3;
int rs2;
char* r2 = b(t2, sizeof(t2) / sizeof(t2[0]), n2, &rs2);
printf("操作序列 2: %s\n", r2);
free(r2);
int t3[] = {1, 2};
int n3 = 4;
int rs3;
char* r3 = b(t3, sizeof(t3) / sizeof(t3[0]), n3, &rs3);
printf("操作序列 3: %s\n", r3);
free(r3);
return 0;
}-
测试用例定义：
定义了三组不同的测试用例，每组包含目标数组和对应的n值。 -
调用函数并输出结果：
- 对于每组测试用例，调用
b函数生成操作序列，并将结果存储在对应的字符数组指针（如r1、r2、r3）中。 - 使用
printf函数输出操作序列。
- 对于每组测试用例，调用
-
内存释放：
使用free函数释放为操作序列分配的内存，避免内存泄漏。
题目二：
AC代码：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
// 函数用于计算结果数组
int* d(int* n, int s, int* r) {
// 为结果数组分配内存
int* a = (int*)malloc(s * sizeof(int));
// 遍历数组 n 中的每个元素
for (int i = 0; i < s; i++) {
a[i] = 0; // 初始化 a[i] 为 0
// 再次遍历数组，寻找值相同但索引不同的元素
for (int j = 0; j < s; j++) {
if (n[j] == n[i] && j != i) {
// 若找到，将 |i - j| 累加到 a[i] 中
a[i] += abs(i - j);
}
}
}
// 设置返回数组的大小
*r = s;
return a;
}
int main() {
int n1[] = {1, 3, 1, 1, 2};
int s1 = sizeof(n1) / sizeof(n1[0]);
int r1;
int* a1 = d(n1, s1, &r1);
printf("结果数组 1: ");
for (int i = 0; i < r1; i++) {
printf("%d ", a1[i]);
}
printf("\n");
free(a1);
int n2[] = {0, 5, 3};
int s2 = sizeof(n2) / sizeof(n2[0]);
int r2;
int* a2 = d(n2, s2, &r2);
printf("结果数组 2: ");
for (int i = 0; i < r2; i++) {
printf("%d ", a2[i]);
}
printf("\n");
free(a2);
return 0;
}题解：
通过定义一个函数 d 来计算结果数组，然后在 main 函数中进行测试并输出结果。
1. 函数d
int* d(int* n, int s, int* r) {
// 为结果数组分配内存
int* a = (int*)malloc(s * sizeof(int));
// 遍历数组 n 中的每个元素
for (int i = 0; i < s; i++) {
a[i] = 0; // 初始化 a[i] 为 0
// 再次遍历数组，寻找值相同但索引不同的元素
for (int j = 0; j < s; j++) {
if (n[j] == n[i] && j != i) {
// 若找到，将 |i - j| 累加到 a[i] 中
a[i] += abs(i - j);
}
}
}
// 设置返回数组的大小
*r = s;
return a;
} n：指向输入数组的指针，这个数组就是题目中的 nums 数组。
s：输入数组的长度，也就是 nums 数组有多少个元素。
r：一个指向整数的指针，用于返回结果数组的长度。
2.内存分配：
int* a = (int*)malloc(s * sizeof(int));这里使用 malloc 函数为结果数组 a 分配内存，分配的内存大小是 s 个整数的空间，因为结果数组的长度和输入数组的长度是一样的。
3.双循环计算 arr 数组的值：
外层循环 for (int i = 0; i < s; i++) 遍历输入数组的每一个元素。对于每个元素 n[i]，先把 a[i] 初始化为 0，因为如果没有找到满足条件的 j，a[i] 就应该是 0。
内层循环 for (int j = 0; j < s; j++) 再次遍历整个输入数组，目的是找到所有满足 n[j] == n[i] 且 j != i 的 j。
当找到满足条件的 j 时，使用 abs(i - j) 计算 i 和 j 之间的距离（取绝对值），然后把这个距离累加到 a[i] 中。
4.主要部分：
1.
定义了一个数组 n1 作为第一个测试用例，计算它的长度 s1。
调用 d 函数计算结果数组 a1，并把结果数组的长度存储在 r1 中。
使用 printf 函数输出结果数组 a1 的每个元素。
最后使用 free 函数释放为 a1 分配的内存，防止内存泄漏。
2.
定义了另一个数组 n2 作为第二个测试用例，同样计算它的长度 s2。
调用 d 函数计算结果数组 a2，并把结果数组的长度存储在 r2 中。
使用 printf 函数输出结果数组 a2 的每个元素。最后使用 free 函数释放为 a2 分配的内存。