【蓝桥杯每日一题】3.28

f狐o狸x

发布于 2025-03-29 09:56:21

5900

代码可运行

文章被收录于专栏：【数据结构实战篇】【数据结构实战篇】

运行总次数：0

代码可运行

喵~ 今天要学习的算法是双指针，也被称为滑动窗口是⼀种优化暴⼒枚举策略的⼿段：

• 当我们发现在两层 for 循环的暴⼒枚举过程中，两个指针是可以不回退的，此时我们就可以利⽤两个指针不回退的性质来优化时间复杂度。

一、唯一的雪花

题目链接

UVA11572 唯一的雪花 Unique Snowflakes

题目描述

解题思路

例如题目中给的输入样例，我们可以按照以下方法来搞定此题：

第一步：先初始化左右指针

第二步：通过右指针向前走开始进窗口

第三步：通过题意判断出窗口

第四部：更新结果，重复上述步骤，直到遍历完全部数组

解题代码

#include <iostream>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

int n;
LL a[N];


int main()
{
	int T; cin >> T;
	while (T--)
	{
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];

		// 初始化
		int left = 1, right = 1, ret = 0;
		unordered_map<int, int> mp;
		while (right <= n)
		{
			// 进窗口
			mp[a[right]]++;
			// 判断
			while (mp[a[right]] > 1)
			{
				mp[a[left]]--;
				left++;
			}
			// 更新结果
			ret = max(ret, right - left + 1);
			right++;
		}
		cout << ret << endl;
	}

	return 0;
}

二、逛画展

题目链接

P1638 逛画展 - 洛谷

题目描述

解题思路

这题其实就是给你一串数字，让你找到包括所有数字种类的最小子串

解题代码

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int a[N], mp[N];

int n, m;

int kind;

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];

	// 初始化
	int left = 1, right = 1,begin = 1 , ret = n;
	while (right <= n)
	{
		// 进窗口
		if (mp[a[right++]]++ == 0) kind++;
		// 判断
		while (kind == m)
		{
			// 更新结果
			int len = right - left ;
			if (len < ret)
			{
				ret = len;
				begin = left;
			}
			// 出窗口
			if (mp[a[left++]]-- == 1) kind--;
		}

	}
	cout << begin << " " << begin + ret - 1 << endl;
	return 0;
}

三、字符串

题目链接

字符串

题目描述

解题思路

这题和上一题是一样的，只是把数字改成字符串了

解题代码

#include <iostream>

using namespace std;

const int N = 30;

int mp[N];
int kind;

int main()
{
    string s; cin >> s;
    int n = s.size();
    // 初始化
    int left = 0, right = 0, ret = n;
    while(right < n)
    {
        // 进窗口
        if(mp[s[right++] - 'a']++ == 0) kind++;
        // 判断
        while(kind == 26)
        {
            // 更新结果
            int len = right - left;
            ret = min(ret, len);
            // 出窗口
            if(mp[s[left++] - 'a']-- == 1) kind--;
        }
    }
    cout << ret << endl;
    return 0;
}

四、丢手绢

题目链接

丢手绢

题目描述

解题思路

这个题依然可以用双指针来解决，只不过是从一条直线变成了一个环而已

解题代码

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

LL a[N];

int n;

int main()
{
    cin >> n;
    LL sum;
    for(int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        sum += a[i];
    }
    LL mid = sum / 2;
    // 初始化
    LL left = 1, right = 1, ret = 0, len = 0;
    while(right <= n)
    {
        // 进窗口
        if(len <= mid) 
        {
            len += a[right++];
        }
        // 判断
        while(len > mid)
        {
            // 更新结果
            ret = max(sum - len, ret);
            // 出窗口
            len -= a[left++];
        }
        if(ret > mid) ret = sum - ret;
        ret = max(ret, len);
    }
    cout << ret << endl;
    return 0;
}

总之，对于双指针这类型的题目就四步：1. 初始化 2. 进窗口 3. 判断出窗口 4. 更新结果

明天我们将学习二分算法，感兴趣的朋友记得关注我哟~

886~

"今天的bug是明天的经验值"

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-03-28，如有侵权请联系 cloudcommunity@tencent.com 删除

优化