图源：文心一言
考研笔记整理~🥝🥝
之前的博文链接在此：数据结构02：线性表[顺序表+链表]_线性链表-CSDN博客~🥝🥝
本篇作为线性表的代码补充，每道题提供了优解和暴力解算法，供小伙伴们参考~🥝🥝
- 第1版：无情地Push Chat GPT老师写代码、分析GPT老师写的代码并思考弱智解~🧩🧩
编辑：梅头脑🌸
参考用书：王道考研《2024年 数据结构考研复习指导》
📇目录
🧵2010统考真题
🧩题目
🌰优解
📇优解思路
⌨️优解代码
#include <iostream>
using namespace std;
// 反转数组中指定范围的元素
void reverse(int arr[], int start, int end) {
// 使用双指针法将数组中指定范围的元素进行反转
// start 指向要反转的范围的起始位置，end 指向要反转的范围的末尾位置
while (start < end) {
// 交换 start 和 end 位置的元素
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
// 向中间移动双指针
start++;
end--;
}
}
// 执行循环左移操作
void rotateLeft(int arr[], int n, int p) {
// 将左移位数取模以确保它在数组长度范围内
p = p % n;
if (p == 0) return; // 如果左移位数为0，直接返回，不需要进行操作
reverse(arr, 0, p - 1); // 反转前半部分
reverse(arr, p, n - 1); // 反转后半部分
reverse(arr, 0, n - 1); // 整体反转
}
int main() {
const int n = 10; // 数组长度为10
const int p = 3; // 左移3位
int arr[n] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // 初始化数组元素
rotateLeft(arr, n, p); // 执行左移操作
// 输出结果
cout << "左移后的数组为: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}⌨️优解演算
🌰暴力解
📇暴力解思路
⌨️暴力解代码
#include <iostream>
using namespace std;
void rotateLeft(int arr[], int n, int p) {
int temp[p]; // 创建一个临时数组用于存储前p个元素
// 复制前p个元素到临时数组中
for (int i = 0; i < p; i++) {
temp[i] = arr[i];
}
// 将后面的元素向前移动p个位置
for (int i = p; i < n; i++) {
arr[i - p] = arr[i];
}
// 将临时数组中的元素复制回原数组末尾
for (int i = 0; i < p; i++) {
arr[n - p + i] = temp[i];
}
}
int main() {
const int n = 10; // 数组长度为10
const int p = 3; // 左移3位
int arr[n] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // 初始化数组元素
rotateLeft(arr, n, p); // 执行左移操作
// 输出结果
cout << "左移后的数组为: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}⌨️暴力解演算
🧵2011统考真题
🧩题目
🌰优解
📇优解思路
⌨️优解代码
#include <iostream>
using namespace std;
// 函数：findMedianSortedArrays
// 参数：两个升序数组A和B，以及它们的长度La和Lb
// 返回值：两个数组的中位数
double findMedianSortedArrays(int A[], int B[], int La, int Lb) {
// 确保La小于等于Lb，方便后续处理
if (La > Lb) {
swap(A, B);
swap(La, Lb);
}
// 初始化左边界和右边界，以及两数组的中位数的位置（结果向下取整）
int left = 0, right = La;
int halfLen = (La + Lb + 1) / 2;
// 使用二分查找在数组A中找到合适的位置
while (left < right) {
int i = left + (right - left) / 2;
int j = halfLen - i;
int round = 1;
// cout << "Round " << round++ << ":" << endl;
// cout << "i = " << i << ", j = " << j << endl;
// 通过比较A[i]和B[j-1]来调整i的位置
if (A[i] < B[j - 1])
left = i + 1;
else
right = i;
// cout << "After comparison, left = " << left << ", right = " << right << endl << endl;
}
// 计算中位数所在的位置
int i = left, j = halfLen - left;
// 计算四个关键值，用于求解中位数
int AleftMax = (i == 0) ? INT_MIN : A[i - 1]; //如果i等于0（也就是A的左边界），那么将AleftMax设为整型的最小值 INT_MIN（通常是-2147483648）。否则，将AleftMax设为A中下标为i-1的元素的值。
int ArightMin = (i == La) ? INT_MAX : A[i];
int BleftMax = (j == 0) ? INT_MIN : B[j - 1];
int BrightMin = (j == Lb) ? INT_MAX : B[j];
// cout << "Final values:" << endl;
// cout << "i = " << i << ", j = " << j << endl;
// cout << "AleftMax = " << AleftMax << ", ArightMin = " << ArightMin << endl;
// cout << "BleftMax = " << BleftMax << ", BrightMin = " << BrightMin << endl;
// 根据数组总长度的奇偶性返回中位数
if ((La + Lb) % 2 == 1)
return max(AleftMax, BleftMax);
else
return (max(AleftMax, BleftMax) + min(ArightMin, BrightMin)) / 2.0;
}
int main() {
int A[] = {11, 13, 15, 17, 19}; // 第一个升序数组
int B[] = {2, 4, 6, 8, 20}; // 第二个升序数组
int La = sizeof(A) / sizeof(A[0]); // 第一个数组的长度，将数组占用内存的总字节数除以第一个元素占用的字节数，我们得到了数组中元素的个数，也就是数组的长度。
int Lb = sizeof(B) / sizeof(B[0]); // 第二个数组的长度
double median = findMedianSortedArrays(A, B, La, Lb); // 调用函数计算中位数
cout << "中位数是: " << median << endl; // 输出中位数
return 0;
}⌨️优解演算
🌰暴力解
📇暴力解思路
⌨️暴力解代码
#include <iostream>
#include <vector>
using namespace std;
double findMedianSortedArrays(int A[], int B[], int La, int Lb) {
// 将数组A和数组B合并到一个新的数组C中
vector<int> C;
int i = 0, j = 0;
while (i < La && j < Lb) {
if (A[i] <= B[j]) {
C.push_back(A[i]);
i++;
} else {
C.push_back(B[j]);
j++;
}
}
while (i < La) {
C.push_back(A[i]);
i++;
}
while (j < Lb) {
C.push_back(B[j]);
j++;
}
// 计算合并后数组C的长度
int Lc = C.size();
// 计算中位数的位置
int mid = Lc / 2;
if (Lc % 2 == 1) {
return C[mid];
} else {
return (C[mid - 1] + C[mid]) / 2.0;
}
}
int main() {
int A[] = {11, 13, 15, 17, 19};
int B[] = {2, 4, 6, 8, 20};
int La = sizeof(A) / sizeof(A[0]);
int Lb = sizeof(B) / sizeof(B[0]);
double median = findMedianSortedArrays(A, B, La, Lb);
cout << "中位数是: " << median << endl;
return 0;
}⌨️暴力解演算
🧵2013统考真题
🧩题目
🌰优解
📇优解思路
⌨️优解代码
#include <iostream>
using namespace std;
int findMajorityElement(int A[], int n) {
int candidate = -1;
int count = 0;
// 第一轮遍历，选出候选主元素
for (int i = 0; i < n; i++) {
// cout << "candidate = A[" << i << "] = " << candidate << ", count = " << count << endl;
if (count == 0) {
candidate = A[i];
count = 1;
} else {
if (A[i] == candidate) {
count++;
} else {
count--;
}
}
}
// 第二轮遍历，确认候选主元素是否真的是主元素
count = 0;
for (int i = 0; i < n; i++) {
if (A[i] == candidate) {
count++;
}
}
// cout << "count = " << count << endl;
if (count > n / 2) {
return candidate;
} else {
return -1;
}
}
int main() {
int A[] = {0, 5, 5, 3, 5, 7, 5, 5};
int B[] = {0, 5, 5, 3, 5, 1, 5, 7};
int La = sizeof(A) / sizeof(A[0]);
int Lb = sizeof(B) / sizeof(B[0]);
int resultA = findMajorityElement(A, La);
int resultB = findMajorityElement(B, Lb);
if (resultA != -1) {
cout << "数组A的主元素是：" << resultA << endl;
} else {
cout << "数组A没有主元素" << endl;
}
if (resultB != -1) {
cout << "数组B的主元素是：" << resultB << endl;
} else {
cout << "数组B没有主元素" << endl;
}
return 0;
}⌨️优解演算
🌰暴力解
📇暴力解思路
⌨️暴力解代码
#include <iostream>
#include <unordered_map>
using namespace std;
int findMajorityElement(int A[], int n) {
// 使用哈希表 counter 统计每个元素的出现次数
unordered_map<int, int> counter;
// 第一次遍历，统计每个元素的出现次数
for (int i = 0; i < n; i++) {
counter[A[i]]++;
}
// 测试：输出哈希表的值
// cout << "Counter:" << endl;
// for (auto& pair : counter) {
// cout << pair.first << ": " << pair.second << endl;
// }
// 找到出现次数最多的元素
int maxCount = 0;
int majorityElement = -1;
for (auto& pair : counter) { // 声明一个名为 pair 的变量，它的类型会根据 counter 中的元素类型自动推断（因为我们使用了 auto）。pair 实际上是一个键值对，包括一个键（pair.first）和一个值（pair.second）。
// 测试：输出所有参数的值
// cout << "pair.first = " << pair.first << ", pair.second = " << pair.second << endl;
// cout << "maxCount = " << maxCount << ", majorityElement = " << majorityElement << endl;
if (pair.second > maxCount) { // 比较当前键值对的值（也就是元素出现的次数 pair.second）和 maxCount 的大小
maxCount = pair.second; // 如果当前元素出现的次数大于 maxCount，则更新 maxCount 和 majorityElement
majorityElement = pair.first; // 将当前元素作为候选主元素
}
}
// 检查出现次数是否大于总长度的一半
if (maxCount > n / 2) {
return majorityElement;
} else {
return -1;
}
}
int main() {
int A[] = {0, 5, 5, 3, 5, 7, 5, 5};
int B[] = {0, 5, 5, 3, 5, 1, 5, 7};
int La = sizeof(A) / sizeof(A[0]);
int Lb = sizeof(B) / sizeof(B[0]);
int resultA = findMajorityElement(A, La);
int resultB = findMajorityElement(B, Lb);
if (resultA != -1) {
cout << "数组A的主元素是：" << resultA << endl;
} else {
cout << "数组A没有主元素" << endl;
}
if (resultB != -1) {
cout << "数组B的主元素是：" << resultB << endl;
} else {
cout << "数组B没有主元素" << endl;
}
return 0;
}⌨️暴力解演算
🧵2018统考真题
🧩题目
🌰优解
📇优解思路
⌨️优解代码
#include <iostream>
#include <vector>
using namespace std;
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
// 将数组元素放置到其对应的位置上
for (int i = 0; i < n; ++i) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
swap(nums[i], nums[nums[i] - 1]);
}
}
// 再次遍历数组，找出第一个不符合规则的位置
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1; // 如果数组本身符合规则，则返回数组长度加1
}
int main() {
vector<int> arr1 = {-5, 3, 2, 3};
vector<int> arr2 = {1, 2, 3};
int missing1 = firstMissingPositive(arr1);
int missing2 = firstMissingPositive(arr2);
cout << "数组{-5, 3, 2, 3}中未出现的最小正整数是：" << missing1 << endl;
cout << "数组{1, 2, 3}中未出现的最小正整数是：" << missing2 << endl;
return 0;
}🧵2020统考真题
🧩题目
🌰优解
📇优解思路
⌨️优解代码
#include <iostream>
#include <vector>
#include <climits> // 在本示例中，INT_MAX 和 INT_MIN 分别用于初始化最小距离变量为最大可能值，以便在计算距离时进行比较，并找到最小值。
using namespace std;
int minDistanceTriplet(vector<int>& S1, vector<int>& S2, vector<int>& S3) {
int minDistance = INT_MAX;
int i = 0, j = 0, k = 0;
int size1 = S1.size(), size2 = S2.size(), size3 = S3.size();
while (i < size1 && j < size2 && k < size3) {
int a = S1[i], b = S2[j], c = S3[k];
int currentDistance = abs(a - b) + abs(b - c) + abs(c - a);
minDistance = min(minDistance, currentDistance);
// 找到与当前 a 最接近的 b
if (a <= b && a <= c) {
i++;
} else if (b <= a && b <= c) {
j++;
} else {
k++;
}
}
return minDistance;
}
void printTriplet(int a, int b, int c) {
cout << "三元组为: (" << a << ", " << b << ", " << c << ")" << endl;
}
int main() {
vector<int> S1 = {-1, 0, 9};
vector<int> S2 = {-25, -10, 10, 11};
vector<int> S3 = {2, 9, 17, 30, 41};
int minDist = minDistanceTriplet(S1, S2, S3);
cout << "最小距离为: " << minDist << endl;
// 输出三元组
// 遍历三元组的索引，根据索引取得对应元素输出
for (int i = 0; i < S1.size(); ++i) {
for (int j = 0; j < S2.size(); ++j) {
for (int k = 0; k < S3.size(); ++k) {
int a = S1[i], b = S2[j], c = S3[k];
int currentDistance = abs(a - b) + abs(b - c) + abs(c - a);
if (currentDistance == minDist) {
printTriplet(a, b, c);
}
}
}
}
return 0;
}🌰暴力解
📇暴力解思路
⌨️暴力解代码
#include <iostream>
#include <vector>
#include <climits> // 在本示例中，INT_MAX 和 INT_MIN 分别用于初始化最小距离变量为最大可能值，以便在计算距离时进行比较，并找到最小值。
using namespace std;
int minDistanceTriplet(vector<int>& S1, vector<int>& S2, vector<int>& S3) {
int minDistance = INT_MAX;
for (int i = 0; i < S1.size(); ++i) {
for (int j = 0; j < S2.size(); ++j) {
for (int k = 0; k < S3.size(); ++k) {
int a = S1[i], b = S2[j], c = S3[k];
int currentDistance = abs(a - b) + abs(b - c) + abs(c - a);
minDistance = min(minDistance, currentDistance);
}
}
}
return minDistance;
}
void printTriplet(int a, int b, int c) {
cout << "三元组为: (" << a << ", " << b << ", " << c << ")" << endl;
}
int main() {
vector<int> S1 = {-1, 0, 9};
vector<int> S2 = {-25, -10, 10, 11};
vector<int> S3 = {2, 9, 17, 30, 41};
int minDist = minDistanceTriplet(S1, S2, S3);
cout << "最小距离为: " << minDist << endl;
// 输出三元组
// 遍历三元组的索引，根据索引取得对应元素输出
for (int i = 0; i < S1.size(); ++i) {
for (int j = 0; j < S2.size(); ++j) {
for (int k = 0; k < S3.size(); ++k) {
int a = S1[i], b = S2[j], c = S3[k];
int currentDistance = abs(a - b) + abs(b - c) + abs(c - a);
if (currentDistance == minDist) {
printTriplet(a, b, c);
}
}
}
}
return 0;
}🔚结语
博文到此结束，写得模糊或者有误之处，欢迎小伙伴留言讨论与批评，督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等，博主会顶锅前来修改~😶🌫️
我是梅头脑，本片博文若有帮助，欢迎小伙伴动动可爱的小手默默给个赞支持一下，收到点赞的话，博主肝文的动力++~🌟🌟