C++基础算法离散化及区间合并篇

这篇具有很好参考价值的文章主要介绍了C++基础算法离散化及区间合并篇。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

📟作者主页:慢热的陕西人

🌴专栏链接:C++算法

📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言

主要讲解了双指针,位运算,离散化以及区间合并。

C++基础算法离散化及区间合并篇,C++算法,c++,算法,开发语言

Ⅴ. 双指针

是一种利用单调规律将二重循环的时间复杂度降为O(N)的算法;

例如:剑指 Offer 48. 最长不含重复字符的子字符串 - 力扣(LeetCode)

如果我们用暴力算法的话,肯定是需要O(N)的复杂度,但是我们采用双指针方式可以实现在O(N)的时间复杂度实现

代码:

    int lengthOfLongestSubstring(string s) 
    {
        int map[257] = { 0 };
        int res = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            map[s[i]]++;
            while(map[s[i]] > 1)
            {
                map[s[j]]--;
                ++j;
            }
            res = max(res, i - j + 1);
        }
        return res;
    }

Ⅵ. 位运算

位运算通常是利用二进制的一些性质展开的

例如:剑指 Offer 15. 二进制中1的个数 - 力扣(LeetCode)

class Solution {
public:
    uint32_t lowbit(uint32_t x)
    {
        return (x & ~x + 1);
    }
    int hammingWeight(uint32_t n) 
    {
        int sum = 0;
        while(lowbit(n)) n &= ~lowbit(n), sum++;
        return sum;
    }
};

其中lowbit(n)函数返回的是n的第一个1的数字:例如5(101),他就返回1;

Ⅶ.离散化:

离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。

通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小

有时候我们的数据范围是(0 , 10e9),但是数据的总数却可能只有(0, 10e5), 这时候我们没必要去开10e9的空间,只需要开最大10e5的空间所要离散化的数据映射到这个小空间里;

例如;{1000, 1111, 1200, 1100, 1250}

我们映射下来
[ 1000 − > 1 ] , [ 1100 − > 2 ] , [ 1111 − > 3 ] , [ 1200 − > 4 ] , [ 1250 − > 5 ] [1000->1],[1100->2],[1111->3],[1200->4],[1250->5] [1000>1],[1100>2],[1111>3],[1200>4],[1250>5]
所以我们要实现离散化需要做非常重要的两步:

①如何将离散化后的数据进行去重;

②如何计算出数据离散化后对应的值;

代码如下:

vector<int> alls;//存储待离散化的数据
sort(alls.begin(), alls.end());//排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); //①对排列好的数据进行去重

//②计算出数据离散化后对应的值
int find(int x)
{
    int l = 0; r = alls.size() - 1;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;//根据题意
}

例题:

C++基础算法离散化及区间合并篇,C++算法,c++,算法,开发语言

测试数据:

//输入
3 3
1 2
3 6
7 5
1 3
4 6
7 8
//输出
8
0
5

代码:

#include<iostream>
#include<vector>
#include<algorithm>

#define N 300010
using namespace std;

typedef pair<int, int> PII;

int a[N], s[N];

vector<int> alls;
vector<PII> add, query;

int n, m;//n次操作, m个区间

int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}
int main()
{

    cin >> n >>m;
    for (int i = 1; i <= n; ++i)
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }
    for (int i = 1; i <= m; ++i)
    {
        int l, r;
        cin >> l >> r;
        query.push_back({ l, r });
        alls.push_back(l);
        alls.push_back(r);
    }

    //去重操作
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    //处理加数
    for (auto item : add)
    {
        int pot = find(item.first);
        a[pot] += item.second;
    }
    //计算前缀和
    for (int i = 1; i <= alls.size(); ++i) s[i] = s[i - 1] + a[i];

    //处理请求
    for (auto item : query)
    {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

Ⅶ. 区间合并

给定多个区间,然后将有交集的区间合并(取并集);

处理如下图的功能:

C++基础算法离散化及区间合并篇,C++算法,c++,算法,开发语言

实现的思路步骤;

①先利用以区间的左端点为标准排序所有的区间。

②合并:

(1)先将第一个区间的端点作为标准stend;

(2)开始遍历后面的区间:

​ 如果区间的左端点小于标准end并且右端点小于标准的end那么就不用进行操作,直接遍历下一个区间;

​ 如果区间的左端点小于标准end并且右端点大于标准的end那么我们就更新标准的end为当前的区间的右端点;

​ 如果区间的左端点大于标准的end那么我们将当前的标准存储起来(已经称为一个合并后的区间),并且开始从(1)开始执行。

C++基础算法离散化及区间合并篇,C++算法,c++,算法,开发语言

代码:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

#define N 100010;

typedef pair<int, int>  PII;

int n;

vector<PII> segs;

void merge(vector<PII>& segs)
{
	vector<PII> res;
	sort(segs.begin(), segs.end()); // 按照左端点进行排序

	int st = -2e9, ed = -2e9;
	for (auto seg : segs)
		if (ed < seg.first)//判断是否要产生新的区间
		{
			if (ed != -2e9) res.push_back({ st, ed });//已经满足合并区间的条件,所以将这个区间存储起来
			st = seg.first, ed = seg.second; //即将开始合并新的区间,要将第一个区间的端点作为标准
		}
		else ed = max(ed, seg.second); //判断合并区间的右端点
	
	if (st != -2e9) res.push_back({ st, ed }); // 将最后一个区间存储到答案中

	segs = res;
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		int l, r;
		cin >> l >> r;
		segs.push_back({ l, r });
	}
	 merge(segs);
	cout << segs.size();

	return 0;
}

到这本篇博客的内容就到此结束了。
如果觉得本篇博客内容对你有所帮助的话,可以点赞,收藏,顺便关注一下!
如果文章内容有错误,欢迎在评论区指正

C++基础算法离散化及区间合并篇,C++算法,c++,算法,开发语言文章来源地址https://www.toymoban.com/news/detail-602511.html

到了这里,关于C++基础算法离散化及区间合并篇的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 陷波器的离散化及仿真验证

                                 (1) 其中,wo​是所谓“中心频率”,也就是你想要“陷掉”的频率。而 ζ 则是“陷阱”的宽度。 根据公式可以发现,当输入信号频率很小(s=0)或者很大( s=+∞)的时候,上面式子的值是1;当输入信号频率刚好等于 s=jωo的时候,分子是0,

    2024年02月13日
    浏览(29)
  • 合并区间【贪心算法】

    合并区间 以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

    2024年02月10日
    浏览(41)
  • 【算法详解】力扣56.合并区间

    力扣链接:力扣56.合并区间 以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [start, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。 示例 1: 输入: intervals = [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,1

    2024年01月19日
    浏览(34)
  • 【贪心算法part05】| 435.无重叠区间、763.划分字母区间、56.合并区间

    目录 🎈LeetCode435. 无重叠区间   🎈LeetCode763.划分字母区间 🎈LeetCode 56.合并区间 链接:435.无重叠区间 给定一个区间的集合  intervals  ,其中  intervals[i] = [starti, endi]  。返回  需要移除区间的最小数量,使剩余区间互不重叠  。    链接:763.划分字母区间 给你一个字符串

    2024年02月16日
    浏览(47)
  • Leecode56:合并区间(贪心算法)

    第一眼看到这个题目觉得应该是比较第一个值的大小,因为如果第n个值比n-1个值的右边还小于等于,那么说明区间可以连起来。但是不会写比较强!! Arrays.sort()函数里, Arrays.sort(shuzu, Comparatorint[](){ }); 千万记得排序后分清楚哪个是原本的哪个是当前的!!以及新加一个

    2024年02月07日
    浏览(46)
  • 贪心算法part5 | ● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间

    重叠问题都需要先排好序,再贪心 搞清楚左右区间,重叠的条件。 要找出最少删除的数量,也就是找出重叠空间的数量,然后用长度减去即可。 这里提供一种与452.用最少数量的箭引爆气球 (opens new window)、435.无重叠区间 (opens new window)相同的思路。 统计字符串中所有字符的

    2024年02月09日
    浏览(60)
  • 【算法之贪心算法IV】leetcode56. 合并区间

    力扣题目链接 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中 points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间的气球。你不知道气球的确切 y 坐标。 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭

    2024年02月11日
    浏览(55)
  • 算法训练day36|贪心算法 part05(重叠区间三连击:LeetCode435. 无重叠区间763.划分字母区间56. 合并区间)

    题目链接🔥🔥 给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。 示例 1: 输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后,剩下的区

    2024年02月09日
    浏览(59)
  • Day 36 贪心算法 part05 : 435. 无重叠区间 763.划分字母区间 56. 合并区间

    56. 合并区间 以数组  intervals  表示若干个区间的集合,其中单个区间为  intervals[i] = [starti, endi]  。请你合并所有重叠的区间,并返回  一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间  。 示例 1: 示例 2: 提示: 1 = intervals.length = 104 intervals[i].length == 2 0 =

    2024年02月09日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包