博弈论
题目描述
运行代码
#include<iostream> #include<vector> using namespace std; int main(){ int n; cin >> n; vector<int> d(n,0); for(int i = 0;i < n;i++){ cin >> d[i]; } vector<int> in(1000,0); for(int k = 1;k<=3;k++){ for(int i=0;i<=n-k;i++){ int t = 0; for(int j=i;j<i+k;j++){ t = 10*t+d[j]; } in[t] = 1; } } for(int i = 0;i < 1000;i++) if(in[i] == 0){ cout << i << endl; return 0; } return 0; }
代码思路
- 输入处理:
- 首先，程序接收一个整数
n，表示数字序列的长度。 - 然后，程序读取接下来的
n个整数并存储在一个名为d的vector（动态数组）中。
- 初始化标记数组:创建一个大小为1000的
vectorin，并将其所有元素初始化为0。这个数组用来标记长度为1至3位的整数是否在给定序列中出现过。由于最大的3位数是999，因此1000的大小足够覆盖所有可能的情况。 - 检查数字序列:对于长度为1、2、3的子序列，程序遍历所有可能的起始位置
i：计算从位置i开始，长度为k（当前循环的长度）的子序列对应的整数t。这是通过将子序列中的每个数字乘以相应位值（10的幂）并求和得到的。将计算出的整数t在in数组中标记为1，表示这个数值已经在输入序列中出现过了。 - 寻找未出现的最小整数:
- 遍历
in数组，找到第一个值为0的元素的索引，这代表了未在输入序列中出现过的最小正整数。 - 一旦找到这样的索引，立即输出该索引（即对应的整数），并结束程序。
- 返回:如果遍历完整个
in数组都没有找到未出现的整数（理论上这种情况不应该发生，但代码逻辑没有直接处理这种特殊情况），程序会正常结束。
改进思路
- 减少内存使用：目前使用了一个大小为1000的
vector来标记数字是否出现，其实最大只需要到n的长度变化的所有组合即可，特别是当n远小于3时。可以通过动态调整in的大小或者使用更高效的数据结构如set或unordered_set来改进。 - 优化寻找未出现数字的步骤：当前实现是线性查找
in数组中值为0的第一个元素，若大多数数字都已出现，则效率较低。可以在遍历过程中直接记录第一个未出现的数字，减少后续查找步骤。 - 增加对极端情况的处理：例如，当输入序列为空或全为0时，原始代码可能表现得不够直观或正确。
改进代码
#include <iostream> #include <vector> #include <unordered_set> using namespace std; int main() { int n; cin >> n; vector<int> d(n, 0); // 输入数字序列 for (int i = 0; i < n; ++i) { cin >> d[i]; } // 使用unordered_set存储已出现的数字，自动去重且查找效率高 unordered_set<int> appeared; // 检查数字序列，添加长度为1到3的数字到集合中 for (int k = 1; k <= min(3, n); ++k) { // 添加边界条件避免n<k时的无效迭代 for (int i = 0; i <= n - k; ++i) { int t = 0; for (int j = i; j < i + k; ++j) { t = 10 * t + d[j]; } appeared.insert(t); } } // 寻找未出现的最小正整数 int i = 1; while (appeared.find(i) != appeared.end()) { ++i; } cout << i << endl; return 0; }
- 通过使用
unordered_set来存储已出现的数字，提高了查找未出现数字的效率。 - 通过直接在遍历过程中寻找未出现的最小整数，避免了最后单独的查找循环，使得代码更加简洁。
- 增加了对输入序列长度的边界检查，确保了代码的健壮性。
注意点：
改进代码为AI生成，并且这个代码的数据通过率97%，无法通过所有测试数据
