目录
💓第一题 P1147 连续自然数和
💒题目描述
🌟解题报告
看到连续的区间求和，那么我得滑动窗口就想拿出来，这个题目的数据是两百万，滑动窗口的时间复杂度大概是 O ( N ) O(N) O(N)，是完全没有问题的。
至于滑动窗口使用的细节，可以参考这篇文章喔，说简答一点，很像双指针。
【基础算法训练】——滑动窗口
两百万的的数据，暴力 O ( N 2 ) O(N^2) O(N2)，一般来说是会超时的，但是这儿Ac了，不太理解，难道是因为会跳出循环蛮🌻参考代码(C++版本)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int n;
cin >> n;
int l = 1;
int sum = 0;
//移动滑窗右端点
for(int r = 1;r < n;r++)
{
sum += r;//把窗口右端加入
if(sum == n) printf("%d %d\n",l,r);
while(sum > n)
{
//当前窗口的值大了，将左端点剔除用于调和
sum -= l;
l ++;
}
//有可能剔除之后，也就是窗口滑动之后，出现了适合的解
if(sum == n) printf("%d %d\n",l,r);
}
return 0;
}
看到别人用暴力Ac了，浅放一下， 我觉得暴力应该Ac不了吧~
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int n;
cin >> n;
int end_ = 0;
for(int i = 1; i <= n/2;i++)
{
LL sum = 0;
for(int j = i; j <= n/2+1;j++)
{
end_ = j;
sum += j;
if(sum >= n) break;
}
if(sum == n)
printf("%d %d\n",i,end_);
}
return 0;
}
💓第二题 1472. 设计浏览器历史记录
💒题目描述
🌟解题报告
原本想的老老实实使用双向链表来表示在页面中前进，在页面中后退，但是发现可以使用数组来存储数据，在数组中向前、向后移动只需要修改索引就好，此时就个更加方便咱们的操作了。
🌻参考代码(C++版本)
class BrowserHistory {
public:
vector<string> ans; // 开一个string数组来记录访问过的网址
int idx = -1; // 表示数组中，当前访问的是第几个网址
BrowserHistory(string homepage) {
//初始化用于记录的数组
ans.clear();
//将当前的主页面加到数组中
ans.push_back(homepage);
//更新访问的指针
idx = 0;
}
void visit(string url) {
// 浏览历史前进的记录全部删除
while(ans.size() > idx + 1)
ans.pop_back();
ans.push_back(url);//将访问的网址加入到数组
idx ++;
}
string back(int steps) {
// 后退的steps不能超过homepage,倘若超过了，直接回到初始化的主页面
if(steps > idx) idx = 0;
//后退到相应的数组下标
else idx -= steps;
//返回答案
return ans[idx];
}
string forward(int steps) {
// 前进的steps不能超过历史记录的最大值
if(steps > ans.size()-1-idx)
idx = ans.size()-1;
//模拟在数组中前进
else idx += steps;
//返回答案
return ans[idx];
}
};
/**
* Your BrowserHistory object will be instantiated and called as such:
* BrowserHistory* obj = new BrowserHistory(homepage);
* obj->visit(url);
* string param_2 = obj->back(steps);
* string param_3 = obj->forward(steps);
*/
💓第三题 430. 扁平化多级双向链表
💒题目描述
🌟解题报告
🌻参考代码(C++版本)
