第一题 P1147 连续自然数和
题目描述
解题报告
看到连续的区间求和，那么我得滑动窗口就想拿出来，这个题目的数据是两百万，滑动窗口的时间复杂度大概是O ( N ) O(N)O(N)，是完全没有问题的。
至于滑动窗口使用的细节，可以参考这篇文章喔，说简答一点，很像双指针。
【基础算法训练】——滑动窗口
两百万的的数据，暴力O ( N 2 ) O(N^2)O(N
2)，一般来说是会超时的，但是这儿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. 扁平化多级双向链表
题目描述
