首页 > 其他分享 >双指针+位运算+离散化+区间合并

双指针+位运算+离散化+区间合并

时间:2023-01-03 20:35:53浏览次数:47  
标签:运算 int 离散 ++ alls 区间 指针

双指针+位运算+离散化+区间合并

双指针算法

可以是两个指针分别指向两个序列,也可以是两个指针指向一个序列,维护一段区间

核心思想:将 \(O(n^2)\) 优化到 \(O(n)\)

本质上就是通过找到单调性进行优化

双指针算法算法模板:

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类:
    (1) 对于一个序列,用两个指针维护一段区间
    (2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作

最长连续不重复子序列

最长的不包含重复数字的连续子序列的长度

1 2 2 3 5 -> 2 3 5 len = 3

暴力做法:先枚举终点,再枚举起点(j为起点,i为终点)

for(int i = 0; i < n; i ++)
{
    for(int j = 0; j <= i; j ++)
    {
        if(check(j, i))
        {
            res = max(res, i - j + 1);
        }
    }
}

优化做法:

本质上还是枚举每一个i,看左边的j离他最远的话是在哪个位置

我们现在只需要枚举每一个i,然后判断j需不需要向后移动

//双指针算法
for(int i = 0; i < n; i ++)
{
    while(j <= i && check(j, i))	j ++;
    
    res = max(res, i - j + 1);
}
  1. 遍历数组\(a\)中的每一个元素\(a[i]\), 对于每一个\(i\),找到\(j\)使得双指针\([j, i]\)维护的是以\(a[i]\)结尾的最长连续不重复子序列,长度为\(i - j + 1\), 将这一长度与\(res\)的较大者更新给\(res\)。
  2. 对于每一个\(i\),如何确定\(j\)的位置:由于\([j, i - 1]\)是前一步得到的最长连续不重复子序列,所以如果\([j, i]\)中有重复元素,一定是\(a[i]\),因此右移\(j\)直到\(a[i]\)不重复为止(由于\([j, i - 1]\)已经是前一步的最优解,此时\(j\)只可能右移以剔除重复元素\(a[i]\),不可能左移增加元素,因此,\(j\)具有“单调性”、本题可用双指针降低复杂度。
  3. 用数组\(s\)记录子序列\(a[j - i]\)中各元素出现次数,遍历过程中对于每一个\(i\)有四步操作:输入\(a[i]\) -> 将\(a[i]\)出现次数\(s[a[i]]\)加1 -> 若\(a[i]\)重复则右移\(j\)(\(s[a[j]]\)要减1) -> 确定\(j\)及更新当前长度\(i - j + 1\)给\(r\)。

位运算

求n的二进制表示中第k位为几

n = 15 = (1111)2

  1. 先把第k位移到最后一位 n >> k
  2. 看个位是几 x & 1

lowbit:返回x的最后一位1

x= (1010)2 lowbit(x) = (10)2

x = (101000)2 lowbit(x) = (1000)2

lowbit(n) = n & -n = n & (~ x + 1)

可以用于求n里面1的个数

int lowbit(int x)
{
    return x & -x;
}


int res = 0;
while(x)	x -= lowbit(x), res ++;		//每次减去x的最后一位1
cout<<res;

// 或者
int cnt = 0;
while(x)
{
    if(x & 1)   cnt ++;
    x >>= 1;
}

位运算算法模板:

求n的二进制表示中第k位数字: n >> k & 1
返回n的最后一位1:lowbit(n) = n & -n

离散化

整数的离散化

一个数列,值很大,但是数量不多(数据范围在[0, 109] ,数量在[0, 105] )

a[] : 1 , 3 , 100, 2000, 500000 这几个下标的元素有用,其他都没有用

b[] : 0 , 1 , 2 , 3 , 4

问题:

  1. a中可能有重复元素,需要去重
  2. 如何算出a[i]离散化后的值是多少(二分)

需要先将所有要进行操作的数存进数组,在进行离散化

值域跨度很大,但是非常稀疏

将所有会用到的下标离散化映射到一个稠密数组内,在稠密数组内进行前缀和,考虑的是相对关系

注意点:

  1. 一定要注意映射到0开始还是1开始的序列!!!

离散化算法模板:

vector<int> alls; // 存储所有待离散化的值

sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于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; // 映射到1, 2, ...n
}

区间和

假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。

首先进行 n 次操作,每次操作将某一位置 x 上的数加 c。

接下来,进行 m次询问,每个询问包含两个整数 l 和 r,你需要求出在区间[l,r] 之间的所有数的和。

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

using namespace std;

const int N = 1e5 + 10;
typedef pair<int, int> PII;

int q[N * 3], s[N * 3];

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

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;
}

int main()
{
    int n, m, x, c, l, r;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++)
    {
        scanf("%d%d", &x, &c);
        add.push_back({x, c});
        alls.push_back(x);
    }
    for(int i = 0; i < m; i ++)
    {
        scanf("%d%d", &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 p : add)
    {
        q[find(p.first)] += p.second;
    }
    s[0] = q[0];						// 求前缀和
    for(int i = 1; i < alls.size(); i ++)
    {
        s[i] = s[i - 1] + q[i];
    }
    for(auto p : query)					// 查询操作
    {
        printf("%d\n", s[find(p.second)] - s[find(p.first) - 1]);
    }
    return 0;
}

unique函数

对于一个有序数列,如何判断不是重复的

  1. 是第一个元素
  2. 和前一个元素不一样, a[i] != a[i - 1]
vector<int>::iterator unique(vector<int> &a)
{
    int j = 0;
    for(int i = 0; i < a.size(); i ++)
        if(!i || a[i] != a[i - 1])
            a[j ++] = a[i];
    //a[0] ~ a[j - 1]中所有不重复的数
    return a.begin() + j;
}

区间合并

给很多区间,假如两个区间有交集,就合并为一个区间

  1. 按照所有区间的左端点排序

  2. 从左到右扫描所有的区间,再扫描的过程中进行处理

  3. 假如下一个起始点和终止点在当前区间内,就不变

    假如下一个起始点在当前区间内,但是终止点在当前区间外,就更新当前区间的右端点

    假如下一个起始点和终止点都在当前区间外,就将当前区间存入结果,继续扫描下一区间

  4. 或者进一步简化一下

    假如下一起始点在当前区间内,就让当前区间的右端点变成 当前右端点和下一终止点的较大值

    假如下一起始点在当前区间外,就将当前区间存入答案并继续扫描下一区间

区间合并算法模板:

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;
    
	//首先对原数组进行排序
    //pair是先对第一关键词排序,再对第二关键词排序
    sort(segs.begin(), segs.end());
	
    //先初始化区间为负无穷
    int st = -2e9, ed = -2e9;
    
    //遍历每一个区间,如果这个区间的右端点在下一个区间的起始点前面,就将该区间保存
    //然后更新当前区间
    //假如这个区间的右端点在下一区间的后面,就比较当前右端点和下一区间的右端点,取较大值作为区间右端点
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -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,离散,++,alls,区间,指针
From: https://www.cnblogs.com/xushengxiang/p/17023289.html

相关文章

  • const 一般类型/指针/引用 与临时对象
    const一般类型:其中i不能重新被赋值。 const指针:int*p1;这个指针代表,指针指向的内容可以改变,且指针本身可以改变指向。intconst*p2;/constint*p2; 这......
  • hdu:sort it(逆序对,离散化)
    ProblemDescription给定n(n<=100000)个正整数,希望对其从小到大排序,如果采用冒泡排序算法,请计算需要进行的交换次数。Input输入包含多组测试用例,每组用例由两行组成:第一行......
  • C++进阶(智能指针)
    智能指针原理C++程序设计中使用堆内存是非常频繁的操作,堆内存的申请和释放都由程序员自己管理。程序员自己管理堆内存可以提高了程序的效率,但是整体来说堆内存的管理是麻......
  • es6 解构赋值 扩展运算符 字符串模板 等
    解构赋值<template><div><h1>解构赋值</h1></div></template><script>exportdefault{name:"demo4",mounted(){//以前......
  • 运算符和表达式
    一、运算符1.含义C语言中,数据是程序处理的对象,运算是对数据进行加工的过程,体现数据之间的各种不同运算关系的符号就称为运算符。C语言中,除了控制语句和输入输出以外的几乎......
  • ygg的分数运算
    链接:https://ac.nowcoder.com/acm/contest/49343/Dygg的分数运算题目描述\[给定两个数a,b(a,b都是质数)。问是否可以通过对分数\frac{1}{a},\frac{1}{b}​......
  • 33_Java中的位运算
    Java中的位运算符一、位运算概述位运算就是直接对整数在内存中的二进制位进行操作分类:​ 逻辑位运算符:位与(&)、位或(|)、位异(^)、位取反(~)​ 移位运算:左移(<<......
  • 【快乐离散数学】命题逻辑 | 复合命题 | 等价命题 | Propositional Logic | Propositi
    WEEK1:PropositionalLogic,PropositionalEquivalences,PredicatesandQuantifiers,NestedQuantifiers.写在前面:本系列博客为复习离散的学习笔记,内容主要参考自 Kenne......
  • 运算符
    基本运算符算术运算符:+,-,*,/,%,++,--赋值运算符:=关系运算符:>,<,>=,<=,==,!=,instanceof逻辑运算符:&&,||,!位运算符:&,|,^,~,>>,<<,>>>条件运算符:?扩展赋值运算符:+=,-=,*=,/=各运算符优先......
  • 基于linux下的shell中的运算及应用实例
    运算方式及运算符号:运算符号意义(*标示常用)+,-加法,减法*,/,%乘法,除法,取余**幂运算++,--自增加,自减少<,<=,>,>=比较符号=,+=,-=,*=,......