以下代码的运行的时间是多少》#include<iostream> using namespace std; const int N = 1e5 + 10; int m; int e[N], l[N], r[N]; int idx; //! 初始化 void init() { l[1] = 0, r[0] = 1;//* 初始化 第一个点的右边是 1 第二个点的左边是 0 idx = 2;//! idx 此时已经用掉两个点了 } //* 在第 K 个点右边插入一个 X void add(int k, int x) { e[idx] = x; l[idx] = k; r[idx] = r[k]; //todo 这边的 k 不加 1 , 输入的时候 k+1 就好 l[r[k]] = idx; r[k] = idx; idx++; }//! 当然在 K 的左边插入一个数 可以再写一个 , 也可以直接调用我们这个函数,在 k 的左边插入一个 数 等价于在 l[k] 的右边插入一个数 add(l[k],x) //*删除第 k个 点 void remove(int k) { r[l[k]] = r[k]; l[r[k]] = l[k]; } int main(void) { ios::sync_with_stdio(false); cin >> m; init(); while(m--) { string op; cin >> op; int k, x; if(op=="R") { cin >> x; add(l[1], x); //! 0和 1 只是代表 头和尾 所以 最右边插入 只要在 指向 1的 那个点的右边插入就可以了 } else if(op=="L")//! 同理 最左边插入就是 在指向 0的数的左边插入就可以了 也就是可以直接在 0的 有右边插入 { cin >> x; add(0, x); } else if(op=="D") { cin >> k; remove(k + 1); } else if(op=="IL") { cin >> k >> x; add(l[k + 1], x); } else { cin >> k >> x; add(k + 1, x); } } for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' '; return 0; }
时间: 2024-04-14 21:31:43 浏览: 23
无法确定代码的运行时间,因为代码的运行时间取决于输入数据的规模和具体的操作。要确定代码的运行时间,需要知道输入数据和每个操作的时间复杂度。
在代码中,主要有以下几个操作:
1. 初始化:时间复杂度为O(1),因为只是对一些变量进行赋值。
2. 插入操作:时间复杂度为O(1),因为只是进行一些指针的操作,不涉及遍历。
3. 删除操作:时间复杂度为O(1),同样只是进行一些指针的操作。
4. 输出操作:时间复杂度为O(n),其中n为插入的元素个数,因为需要遍历链表来输出元素。
因此,整个代码的运行时间取决于输入数据的规模和具体操作的次数。无法准确估计代码的运行时间,需要根据实际情况进行测试。
相关问题
#include <iostream>#include <cstring>using namespace std;const int N = 1e6 + 10, MOD = 1e9 + 7;int n;int dp[N];int main(){ cin >> n; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i ++) dp[i] = (dp[i - 1] + dp[i - 2]) % MOD; cout << dp[n] << endl; return 0;}请将这段代码时间复杂度降低并展示给我
这段代码已经是 $O(n)$ 的时间复杂度,不过可以使用滚动数组进一步优化空间复杂度,将空间复杂度降为 $O(1)$。如下所示:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MOD = 1e9 + 7;
int n;
int a = 1, b = 1, c;
int main() {
cin >> n;
if (n == 0) cout << 1 << endl;
else if (n == 1) cout << 1 << endl;
else {
for (int i = 2; i <= n; i++) {
c = (a + b) % MOD;
a = b;
b = c;
}
cout << b << endl;
}
return 0;
}
```
在这个版本中,我们只使用了三个变量 a、b 和 c,避免了使用数组来存储所有的 dp 值,从而将空间复杂度降低为 $O(1)$。
#include <iostream> #include <algorithm> #include <string> #include <cstdio> #include <cmath> #include <set> #include <map> using namespace std; //const int N = 1e5 + 10; //typedef long long ll; int main() { int t; cin >> t; while (t--) { int n; set<string>a; string s; cin >> n >> s; int t = 0; for (int i = 0; i < s.size(); i++) { t = s.find(s[t]); a.insert(s.substr(i, 1)); } for (int i = 0; i < a.size(); i++) cout << a[i]; cout << endl; } return 0; }有什么问题
这段代码存在一些问题:
1. 在第二个 for 循环中,使用了下标访问 set 容器,这是错误的,因为 set 容器不支持下标访问。
2. 在第二个 for 循环中,使用了 a.size(),这也是错误的,因为 set 容器没有 size() 方法,应该使用 a.size()。
3. 在第一个 for 循环中,应该使用 s.substr(i, 1) 而不是 s.substr(0, t+1),因为后者会将 s 的前 t+1 个字符作为子串,而不是从 i 开始的一个字符。
4. 在第一个 for 循环中,应该将 a.insert() 放在 t = s.find(s[t]) 的后面,因为插入的是 s.substr(i, 1),插入顺序应该是从前往后。
修正后的代码如下:
```c++
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
set<string> a;
string s;
cin >> n >> s;
int t = 0;
for (int i = 0; i < s.size(); i++) {
a.insert(s.substr(i, 1));
t = s.find(s[t]);
}
for (auto it = a.begin(); it != a.end(); it++) cout << *it;
cout << endl;
}
return 0;
}
```
相关推荐
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)