离散化与区间合并两种算法的理解与解题 + 美团笔试题(二维区间合并)_zhutouasam的博客-程序员秘密

技术标签: 算法  java  数据结构与算法  数据结构  

---------------刷算法题的乐趣就是在刷题过程中,学习并且掌握了新知识,巩固了旧知识,这很nice!!! 就是一个小的知识点关查资料就要十个网页窗口,除了有点费脑子之外就是怕红红的ce----------------


前言

y1s1,java语言有点太过正经了,,,

一、离散化算法

1.概念

简单来说:有一个数组,下标有:1,400,300000, 100000000 …。 但是我们总不可能把整个数组表示出来,又因为数组其中有些是没有储存元素 的,所以我们可以利用离散化算法,把所有的没有元素的数组空间去掉。而且如果当题目是数轴 有负数 也会感到无从下手。

离散化的本质,是映射,将间隔很大的点,映射到相邻的数组元素中。减少对空间的需求,也减少计算量。

2.做题思想

  1. 用一个数组来装下标
  2. 对装下标的数组进行排序,去重
  3. 开一个Pair类的数组 k(first)装下标 , v(second)装原本所在下标的值。
  4. 根据题目解题( 构造一个函数(二分查找) 用来找离散后的下标) find函数是重点!!

3.解题模板

借用yxc大佬的模板(C++版本二)

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
}

模板看不懂没关系,通过题目理解!!!
上菜上菜!! :::

4.例题

题目描述

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

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

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

输入格式
第一行包含两个整数n和m。

接下来 n 行,每行包含两个整数x和c。

再接下里 m 行,每行包含两个整数l和r。

输出格式
共m行,每行输出一个询问中所求的区间内数字和。
数据范围
109≤x≤109,
≤n,m≤105,
109≤l≤r≤109,
10000≤c≤10000

样例
输入样例:

3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例:
8
0
5

答案:

import java.util.*;
import javafx.util.*;
public class Test01 {
    
    //300010是因为(n次操作 + m次询问)的最大值是3*100000, +10是怕数组出界 
    static int N = 300010;
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        //用来存储 数组下标 的数组
        List<Integer> alls = new ArrayList<>();
        //根据题意  需要一个数组来储存 下标 和 所加的值
        List<Pair<Integer, Integer>> adds = new ArrayList<>();
        // 这个数组用来储存 区间
        List<Pair<Integer, Integer>> query = new ArrayList<>();
        int[] a = new int[N];
        int[] s = new int[N];

        //根据题意进行 n 次操作,每次操作将某一位置x上的数加c
        while (n -- > 0) {
    
            int x = sc.nextInt();
            int c = sc.nextInt();
            adds.add(new Pair<>(x, c));
            //将需要离散化的 x(下标) 储存到数组
            alls.add(x);
        }
        //根据题意进行 m 次询问,每个询问包含两个整数l和r,分别为每个区间的左右端点
        while (m -- > 0) {
    
            int l = sc.nextInt();
            int r = sc.nextInt();
            query.add(new Pair<>(l, r));
            //将需要离散化的 l,r(下标) 储存到数组
            alls.add(l);
            alls.add(r);
        }
        //将数组进行排序
        Collections.sort(alls);
        // unique是把 存下标的数组 里面重复的下标删去
        // list.subList(a, b) 这个方法是数组从[0, unique - 1]截取出来的子数组
        //所以unique的返回值 不需要 减一
        alls = alls.subList(0, unique(alls));
        
        // *****重点*****
        for (Pair<Integer, Integer> item : adds) {
    
            //注意这里不是返回原来的数组存储的那个下标!!!
            //请把目光看向 构造的 find 方法
            int index = find(alls, item.getKey());
            a[index] = item.getValue();
        }
        //前缀和计算
        for (int i = 1; i <= alls.size(); i ++)
            s[i] = s[i - 1] + a[i];
        
        //用find方法把 原来存储区间左右端点的值 转化为 离散化排好序的数组里面找对应的下标
        for (Pair<Integer, Integer> item : query) {
    
            int l = find(alls, item.getKey());
            int r = find(alls, item.getValue());
            System.out.println(s[r] - s[l - 1]);
        }
    }

    public static int find(List<Integer> list, int x) {
    
        int l = 0;
        //这里的右边界是 给某个位置加值 的数组的大小
        //就是 我们离散化的数组
        int r = list.size() - 1;
        //二分查找模板
        while (r > l) {
    
            int mid = l + r >> 1;
            if (x <= list.get(mid))
                r = mid;
            else
                l = mid + 1;
        }
        //返回值加一是因为待会要进行 前缀和计算 ,为了处理边界问题!
        return l + 1;
    }

    //因为Java没有unique方法 我们需要自己写
    public static int unique(List<Integer> list) {
    
        int index = 0;
        //当这个数是第一个数,或者这个数与它的前一个数不相等时,他才是唯一的数
        for (int i = 0; i < list.size(); i ++) {
    
            if (i == 0 || list.get(i) != list.get(i - 1))
                list.set(index ++, list.get(i));
        }
        return index;
    }
}

我尽力了 。。。。
如果前缀和不懂的,可以看一下我的上一篇博客:前缀和与差分思想 哈哈哈!
有什么不懂请到评论区讨论吧,语文基础比较差有什么地方说错请帮忙指出来,谢谢你!


二、区间合并

1.概述

Emmmmm,就是将包含的 或者 相交的区间 合并。


2.解题步骤

  1. 先将所有区间进行从左到右排序(使区间之间只有剩下三种情况:相等 相交 相离)
  2. 进行合并

3.解题模板

yxc大佬 yyds!!!

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    
    vector<PII> res;
    //因为C++中sort函数有对PII的有效:先判定first, 如果first相同,则判断second
    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;
}



说实话,学习算法思想还是题目管用,上菜!!!::::

4.例题

4.1、题目描述
给定 n 个区间 [li,ri],要求合并所有有交集的区间。

注意如果在端点处相交,也算有交集。

输出合并完成后的区间个数。

例如:[1,3]和[2,6]可以合并为一个区间[1,6]。

输入格式
第一行包含整数n。

接下来n行,每行包含两个整数 l 和 r。

输出格式
共一行,包含一个整数,表示合并区间完成后的区间个数。

数据范围
1≤n≤100000,
−109≤li≤ri≤109
输入样例:
5
1 2
2 4
5 6
7 8
7 9
输出样例
3


import java.util.*;
import javafx.util.*;

public class Test01 {
    
   public static void main(String[] args) {
    
       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
       List<Pair<Integer, Integer>> list = new ArrayList<>();
       while (n -- > 0) {
    
           int l = sc.nextInt();
           int r = sc.nextInt();
           list.add(new Pair<>(l, r));
       }
       list = merge(list);
       System.out.println(list.size());
   }

   public static List<Pair<Integer, Integer>> merge(List<Pair<Integer, Integer>> segs) {
    

   	   //我采用匿名内部类构造一个比较器,用来比较Pair这个类
       Collections.sort(segs, new Comparator<Pair<Integer, Integer>>(){
    
           @Override
           public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) {
    
           	//返回1表示顺序不变,-1表示顺序相反
               if (p1.getKey() > p2.getKey()) return 1;
               else if (p1.getKey() < p2.getKey()) return -1;
               else {
    
                   if (p1.getValue() >= p2.getValue()) return 1;
                   else return -1;
               }
           }
       });

       Integer st = Integer.MIN_VALUE;
       Integer ed = Integer.MIN_VALUE;
       List<Pair<Integer, Integer>> res = new ArrayList<>();
   	
   	   //直接套用模板
       for (Pair<Integer, Integer> seg : segs) {
    
           if (ed < seg.getKey()) {
    
               if (st != Integer.MIN_VALUE)
                   res.add(new Pair<>(st, ed));
               st = seg.getKey();
               ed = seg.getValue();
           }
           else
               ed = max(ed, seg.getValue());
       }
       if (st != Integer.MIN_VALUE)
           res.add(new Pair<>(st, ed));

       return res;
   }

   public static Integer max(Integer a, Integer b) {
    
       if (a >= b)
           return a;
       else
           return b;
   }
}

是不是感到无压力? 趁热打铁来一道19年的美团笔试题吧!!!
上菜!!!!::::
在 acwing.com 这个网站的第759道题

4.2、题目描述

在二维平面上有一个无限的网格图形,初始状态下,所有的格子都是空白的。

现在有 n 个操作,每个操作是选择一行或一列,并在这行或这列上选择两个端点网格,把以这两个网格为端点的区间内的所有网格染黑(包含这两个端点)。

问经过 n 次操作以后,共有多少个格子被染黑,重复染色同一格子只计数一次。

输入格式
第一行包含一个正整数 n。

接下来 n 行,每行包含四个整数 x1,y1,x2,y2,表示一个操作的两端格子坐标。

若 x1=x2 则是在一列上染色,若 y1=y2 则是在一行上染色。

保证每次操作是在一行或一列上染色。

输出格式
包含一个正整数,表示被染黑的格子的数量。

数据范围
1≤n≤10000,
−109≤x1,y1,x2,y2≤109
输入样例
3
1 2 3 2
2 5 2 3
1 4 3 4
输出样例:
8

因为是二维的,所以要思考的有需要怎么把区间装进数组,该怎么装方便些,怎么进行查重!
想不出的直接看到代码的末尾!

import java.util.*;
public class test02 {
    
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<seg> rows = new ArrayList<>();
        List<seg> cols = new ArrayList<>();

        while (n -- > 0) {
    
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            if (x1 == x2)
                cols.add(new seg(x1, Math.min(y1, y2), Math.max(y1, y2)));
            else
                rows.add(new seg(y1, Math.min(x1, x2), Math.max(x1, x2)));
        }
        long num = 0;
        num = merge(rows) + merge(cols);
        for (seg row : rows)
            for (seg col : cols)
            	//查重
                if (row.k >= col.sml && row.k <= col.big && col.k >= row.sml && col.k <= row.big) {
    -- num ;}

        System.out.println(num);

    }

    public static long merge(List<seg> list) {
    
        long num = 0;
        List<seg> res = new ArrayList<>();
        list.sort((s1, s2) -> {
    
            if (s1.k != s2.k)
                return s1.k - s2.k;
            else if (s1.sml != s2.sml)
                return s1.sml - s2.sml;
            else
                return s1.big - s2.big;
        });

        int st = Integer.MIN_VALUE;
        int ed = Integer.MIN_VALUE;
        int k = list.get(0).k;
        for (seg item : list) {
    
            if (k == item.k) {
    
                if (ed < item.sml) {
    
                    if (st != Integer.MIN_VALUE) {
    
                        res.add(new seg(k, st, ed));
                        //求出染的格子个数
                        num += ed - st + 1;
                    }
                    st = item.sml;
                    ed = item.big;
                }
                else
                    ed = Math.max(ed, item.big);
            } else {
    
                if (st != Integer.MIN_VALUE) {
    
                    res.add(new seg(k, st, ed));
                    num += ed - st + 1;
                }
                k  = item.k;
                st = item.sml;
                ed = item.big;
            }
        }

        if (st != Integer.MIN_VALUE) {
    
            res.add(new seg(k, st, ed));
            num += ed - st + 1;
        }

        list.clear();
        list.addAll(res);// 等同于 list = res
        return num;
    }

    static class seg{
    
        int k;
        int sml;
        int big;

        public seg(int k, int sml, int big){
    
            this.k = k;
            this.sml = sml;
            this.big = big;
        }
    }
}
我们需要构造一个类,来存相同的行(列)和 当前行(列)的区间 
查重就是 当一个数符合 :  在相同行的情况下, 这个相同行 大于 列的区间最小值, 小于 列的区间最大值
					   在相同列的情况下,这个相同列 大于行的区间最小值, 小于 行的区间最大值!
			说到底就是 在有效的行列区间重合的部分。 看图

在这里插入图片描述
谢谢您的阅读


自我总结

两天三道题 累了。。。。
说真的,Java语言太正经了。。
通过这三道题,我学会了:

  1. 知道Pair这个类,并会使用
  2. 使用匿名内部类和对比较器的使用(从一开始不知道怎么排数组-> Collections.sort -> list.sort)越来越灵活了!!!
  3. 认识到Integer等的常量 Integer.MIN_VALUE=>最小值 (复习了Integer 从-128 ~ 127是储存在堆中的常量池中)
  4. 学会 离散化算法 和 区间合并 !
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45576579/article/details/119830725

智能推荐

适合程序员 ZB 的杯子 |每日趣闻_CSDN 程序人生的博客-程序员秘密

往 期 趣 闻 ☞噗!一图读懂程序员职业发展道路 |每日趣闻☞编程语言的鄙视链,谁不服就进来评论!|每日趣闻☞曝光程序员的桌面!有点心酸 |每日趣闻☞程序员才是真段子手,不信?点进来!...

带左右箭头的图片轮播_weixin_30505225的博客-程序员秘密

轮播图实现效果见下图,图片能自己轮播,点击左右按钮进行翻页轮播,鼠标悬停图片或者标题上,停止轮播;效果图为:html&lt;!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"&gt;&lt...

JVM配置参数详解_jvm 配置 -xx:newsize、-xx:maxnewsize 配置__抱歉打扰了的博客-程序员秘密

一、堆参数设置-XX:+PrintGC 使用这个参数,虚拟机启动后,只要遇到GC就会打印日志-XX:+UseSerialGC 配置串行回收器-XX:+PrintGCDetails 可以查看详细信息,包括各个区的情况-Xms:设置Java程序启动时初始化堆大小-Xmx:设置Java程序能获得最大的堆大小-Xmx20m -Xms5m -XX:+Print...

蓝牙BLE芯片PHY6222之GPIO按键操作_hal_pwrmgr_register_不打开的雨伞的博客-程序员秘密

蓝牙BLE芯片PHY6222之GPIO按键操作按键唤醒IO初始化按键中断唤醒回调按键唤醒IO初始化void key_init(void){ uint8 i; key_state.key[0].pin = GPIO_P14; key_state.key[0].idle_level = HAL_HIGH_IDLE; hal_gpio_pin_init(P14, IE); hal_gpio_pull_set(P14, GPIO_PULL_UP_S); k

学习笔记----字符串分割_s.substr(i, j-i)_本本人的博客-程序员秘密

1, 字符串的分割算法(标准库版) void split(const string& s,char c,vector& v){string::size_type i = 0;string::size_type j = s.find(c);while (j != string::n

Pytorch 之神经网络_import torch import torchvision.datasets as dsets _川师_King的博客-程序员秘密

加载数据——Data Loaderimport torchimport torchvision.datasets as dsetsimport torchvision.transforms as transformsimport osimport syspath = os.path.split(os.path.abspath(os.path.realpath(sys.argv[0])))[0] + os.path.seppath = path[:-10] + '/data/'#/******

随便推点

HTML密码正则表达式结构,JavaScript动态检测密码强度原理及实现方法详解_Suvo Sarkar的博客-程序员秘密

本文实例讲述了JavaScript动态检测密码强度原理及实现方法。分享给大家供大家参考,具体如下:在注册账户,设置密码时,会出现密码强度动态检测,网上看了一些帖子,大多只写了具体的实现过程,而没有对原理的分析过程。下面着重讲一下其原理。原理分析通常实现密码强度动态判断有两种方案实现:正则。但其效率低一点,难度也大一些。字符串,函数和运算符。这里用第二种方案,但是如何判断一个密码串是强还是弱呢?一般...

小程序onReactbottom事件无效问题_onreachbottom 失效_Suger、张的博客-程序员秘密

小程序上拉刷新需要在.json文件中设置好触发onReactbottom事件的距离(滚动条距离底部多少尺寸时触发)我在项目中设置为50可以做到无缝衔接"enablePullDownRefresh": true //允许上拉或者下拉事件"onReachBottomDistance":50 //距离底部多远触发1.css样式设置导致内容高度...

ByteBuffer.get() 与 InputStream.read()_bytebuffer.get() & 0x0ff;_铁头乔的博客-程序员秘密

在使用 ByteBuffer 替换 InputStream 时,遇到了一个问题,就是 InputStream 的 read 方法与 ByteBuffer 的 get 方法是不一样的,在遇到小于 0 的 byte 就会出错。InputStream 的 read() 方法读取一个 byte,这是一个无符号整数,范围 0~255 /** * Reads the next byte of ...

软件测试的面试题_糖心baby的博客-程序员秘密

一、UAT测试和预生产测试有什么区别?UAT测试其实也是验收测试,它是需要真实的用户来参与的测试。预生产测试其实是从测试环境到生产环境 的一个过渡,预生产环境会和我们的生产环境在配置上是一样的,那预生产测试环境的作用其实就是在更新新版本到正式环境之前,在预生产环境走一下基本的流程二、如何用jmeter做性能测试,并给出报告呢?1.我们先要做需求的分析,你要确定你们的这个产品的功能以及架构,还有我们的这个用户的这个分布的一个情况,通过这些,你能制定你的这个测试目标;2.你就要开始搭建这个测试环境,因为

CNN中的深度可分离卷积、组卷积、逐层卷积、空洞卷积、转置卷积、可变形卷积_cdknight_happy的博客-程序员秘密

参考:https://zhuanlan.zhihu.com/p/28749411https://blog.csdn.net/Chaolei3/article/details/793745631 普通卷积CNN中的普通卷积是三维卷积,每个卷积核的通道数和输入数据通道数相同,卷积核的个数为输出数据的通道数。具体的计算过程为在各通道进行卷积核和对应感受野输入数据的对应位置相乘再相加操作,得到一个...

最近招聘时,收到的简历上所发现的问题_weixin_30835933的博客-程序员秘密

长话短说。从去年开始,给以前的公司和现在的公司招人。收到了不少简历。在收到的简历中,发现有一些简历存在着一些非技术性的共通问题:1. 格式问题明明是Doc的简历,但是打开后发现和文本文档没什么区别。什么格式都没有。这让阅读简历人从何下手啊?2. 字符对齐问题标题明明居中的,偏偏要抖两个字符;段首缩进的,参差不齐。段落内应该用对齐线对齐的,非要用空格对齐,狗啃过的一样。3. ...

推荐文章

热门文章

相关标签