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

- 双指针算法
：
1.核心
优化时间？两个指针扫描一个序列，时间花费是O(n);
for(int i=0,j=0;i 
模板： 
for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
 
题目一
  
做法：
 第一步：先想一下朴素做法，也就是暴力做法
 java 
package 大学菜;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 最长不重复子序列 {
    static int num = 100010;
    static int[] A = new int[num];
    static int[] S = new int[num];
    static int[] G = new int[num];
    static int[] B = {1, 2, 2, 3, 5};
    //hash表的使用，在原来的地方加一
    public static int find(int[] A,int l,int r){
        //
        int res = 0;
        for(int i=0,j=0;i1){
                S[A[j]]--;//这个是一开始的i，所以这个i此时已经不在这个，当前的i=0
                j++;
            }
            res = Math.max(res,i-j+1);
        }
        return res;
    }
    public static void main(String[] args) throws IOException {
       //双指针算法来找
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        //
        //5
        //1 2 2 3 5
        String str1 = reader.readLine();
        int n = Integer.valueOf(str1);
        //接收数组
        String[] str2 = reader.readLine().split(" ");
        for(int i=0;i 
第二步：
 看看有没有单调关系，进行缩小时间复杂度，重复元素的判断。：
 暴力判断是每次都是j=0；i=0;而更好的做法是j不用重新从零判断，从i当前的位置判断。
 check函数是用来判断是否存在重复元素。
 就是使用hashmap的方法进行使用在同样的值的地方进行数组上面的++。 
- 位运算 
二进制的转换：
 x 变成二进制
 -x 取反
 +1
 x &(-x+1) = 最后的一位1 的运算
 //应用到数据可以检查有多少个1，每次剪掉1； 
c++(lowbit运算)使用java进行实现 
    public static int lowbit(int x){//与运算
        return (x & -x);
    }
 
题目：
  
代码： 
package 大学菜;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class 二进制中的1个数 {
    static int num = 10010;
    public static int lowbit(int x){//与运算
        return (x & -x);
    }
    public static void main(String[] args) throws IOException {
        //int
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String str = reader.readLine();
        int n = Integer.valueOf(str);
        //数组
        String[] str1 = reader.readLine().split(" ");
        for(int i=0;i 
题目：
 人类做题：
 dfs的过程 
- 离散化 
值的跨度特别大，导致的空间浪费。 
要进行离散化----数据个数的映射-
 从稀疏到密集的变化。
 1.去重
 2.
 模板 
vector alls; // 存储所有待离散化的值
//java--键值对
class Pairs{
    int l,r;
    public Pairs(int fir,int sec){
        this.l = fir;
        this.r = sec;

    }
}
//c++
sort(alls.begin(), alls.end()); // 将所有值排序
//java
Collections.sort(alls);
//
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

作者：yxc
 

 题目：
 
 去掉重复元素： 
题目：
 代码： 
package 大学菜;

import java.util.*;

//3 3
//1 2
//3 6
//7 5
//1 3
class Pairs{
    int l,r;
    public Pairs(int fir,int sec){
        this.l = fir;
        this.r = sec;

    }
}

public class 离散化2 {
    static int le = 300010;
    static int[] A = new int[le];//存储原先的数
    static int[] S = new int[le];//存储前缀和
    //unique函数
    public static int unique(List list){//此时alls已经是有序的，使用什么方法进行重复
        //双指针
        int j =0;
        for(int i=0;i list){
        //二分查找
        int l = 0;
        int r = list.size()-1;//不是下标，是大小
        while (l>1;
            if(list.get(mid)<=x){
                l = mid;
            }else {
                r = mid-1;
            }
        }
        return l+1;//下标
    }
    //数轴点：第一次的输入的x,第二输入的l,r。
    //存储区间点加操作的的，点和值（x,c）
    //存储区间点求和操作的，左右区间（l,r）
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        int m = sc.nextInt();
        //定义结构体
        List alls = new ArrayList<>();//放所有的x,l,r
        //定义成对存放的数据
        List xc = new ArrayList<>();
        List lr = new ArrayList<>();
        //n
        for(int i=0;i 
 
- 区间合并： 
很快求并集区间 ，快速进行求解区间段个数。
 模板： 
c++： 
// 将所有存在交集的区间合并
void merge(vector &segs)//存储
{
    vector res;

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

作者：yxc

 
java： 
class Pair2s{
    int fir;
    int sec;
    public Pair2s(int fir,int sec){
        this.fir=fir;
        this.sec=sec;
    }
}
Pair2s[] pa= new Pair2s[n];//数组里面放的是pair类型的数组
//对数组进行排序
Arrays.sort(pa,(o1, o2) -> {return o1.fir - o2.fir;});//sheng序排xu
//比较端点
int num = 0;
int max = Integer.MIN_VALUE;
for(int i=0;i=说明有交集或者正好借接住区间，需要	合并，max需要变化到，此时的有端点。
    }
 return num;
}
 
题目：
 
 代码： 
package 大学菜;

import java.lang.reflect.Array;
import java.util.*;


class Pair2s{
    int fir;
    int sec;
    public Pair2s(int fir,int sec){
        this.fir=fir;
        this.sec=sec;
    }
}
public class 区间合并 {
    public static int hebing(Pair2s[] pa,int n){
        //对数组进行排序
        Arrays.sort(pa,(o1, o2) -> {return o1.fir - o2.fir;});//生序排序
        //比较端点
        int num = 0;
        int max = Integer.MIN_VALUE;
        for(int i=0;i=说明有交集或者正好借接住区间，需要合并，max需要变化到，此时的有端点。
        }
        return num;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Pair2s[] pa= new Pair2s[n];//数组里面放的是pair类型的数组
        for(int i=0;i
双指针-位运算--离散化--区间合并

Java相关栏目本月热门文章
