【基础算法训练】—— 双向链表

• • 第一题 P1147 连续自然数和
  • • 题目描述
    • 解题报告
    • 参考代码(C++版本)
  • 第二题 1472. 设计浏览器历史记录
  • • 题目描述
    • 解题报告
    • 参考代码(C++版本)
  • 第三题 430. 扁平化多级双向链表
  • • 题目描述
    • 解题报告
    • 参考代码(C++版本)

第一题 P1147 连续自然数和 题目描述

原题传送门

解题报告

看到连续的区间求和，那么我得滑动窗口就想拿出来，这个题目的数据是两百万，滑动窗口的时间复杂度大概是 O ( N ) O(N) O(N)，是完全没有问题的。
至于滑动窗口使用的细节，可以参考这篇文章喔，说简答一点，很像双指针。
【基础算法训练】——滑动窗口
两百万的的数据，暴力 O ( N 2 ) O(N^2) O(N2)，一般来说是会超时的，但是这儿Ac了，不太理解，难道是因为会跳出循环蛮

参考代码(C++版本)

#include  

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 %dn",l,r);
		while(sum > n)
		{
			//当前窗口的值大了，将左端点剔除用于调和 
			sum -= l;
			l ++;
		}
		//有可能剔除之后，也就是窗口滑动之后，出现了适合的解 
		if(sum == n) printf("%d %dn",l,r);
	}
	return 0;
}

看到别人用暴力Ac了，浅放一下， 我觉得暴力应该Ac不了吧~

#include  

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 %dn",i,end_);
		
	} 
	return 0;
}

第二题 1472. 设计浏览器历史记录 题目描述

原题传送门

解题报告

原本想的老老实实使用双向链表来表示在页面中前进，在页面中后退，但是发现可以使用数组来存储数据，在数组中向前、向后移动只需要修改索引就好，此时就个更加方便咱们的操作了。

参考代码(C++版本)

class BrowserHistory {
public:
    vector 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];

    }
};

第三题 430. 扁平化多级双向链表 题目描述

原题传送门

解题报告 参考代码(C++版本)