差分数组技巧

差分数组技巧一、差分数组适用题型,和技巧前缀和数组:适用于原始数组不会被修改的情况下,频繁查询某个区间的累加和差分数组:主要适⽤场景是频繁对原始数组的某个区间的元素进⾏增减(比如:给你和数组arr,然后再下标0-4之间各元素加一,2-5之间各个元素减2,求最终的原数组)差分数组技巧1.构建差分数组(diff),diff[0]=nums[0],之后diff[i]=nums[i]-nums[i-1]int[]diff=newint[nums.length];//构造差分数组diff[0]=n

大家好,又见面了,我是你们的朋友全栈君。

一、差分数组适用题型,和技巧

  • 前缀和数组:适用于原始数组不会被修改的情况下,频繁查询某个区间的累加和
  • 差分数组:主要适⽤场景是频繁对原始数组的某个区间的元素进⾏增减(比如:给你和数组arr,然后再下标0-4之间各元素加一,2-5之间各个元素减2,求最终的原数组)
  • 差分数组技巧
    1.构建差分数组(diff),diff[0]=nums[0],之后diff[i]=nums[i]-nums[i-1]
int[] diff = new int[nums.length];
// 构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) { 
   
 diff[i] = nums[i] - nums[i - 1];
}

在这里插入图片描述

2.根据差分树组反推原数组(res):res[0]=diff[0],res[i]=res[i-1]+diff[i]

int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) { 
   
 res[i] = res[i - 1] + diff[i];
}

在这里插入图片描述

3.这样构造差分数组 diff,就可以快速进⾏区间增减的操作,如果你想对区间 nums[i…j] 的元素全部加3,那么只需要让 diff[i] += 3,然后再让 diff[j+1] -= 3 即可:
在这里插入图片描述

  • 构建差分数组类
// 差分数组⼯具类
class Difference { 
   
 	// 差分数组
 	private int[] diff;
 
 	/* 输⼊⼀个初始数组,区间操作将在这个数组上进⾏ */
 	public Difference(int[] nums) { 
   
 		assert nums.length > 0;//若是空数组则抛异常
 		diff = new int[nums.length];
 		// 根据初始数组构造差分数组
 		diff[0] = nums[0];
 		for (int i = 1; i < nums.length; i++) { 
   
 			diff[i] = nums[i] - nums[i - 1];
 		}
 	}
 	/* 给闭区间 [i,j] 增加 val(可以是负数)*/
 	public void increment(int i, int j, int val) { 
   
 		diff[i] += val;
 		if (j + 1 < diff.length) { 
   
 			diff[j + 1] -= val;
 		}
	}
	/* 返回结果数组 */
 	public int[] result() { 
   
 		int[] res = new int[diff.length];
 		// 根据差分数组构造结果数组
 		res[0] = diff[0];
 		for (int i = 1; i < diff.length; i++) { 
   
 			res[i] = res[i - 1] + diff[i];
 		}
 		return res;
 	}
}

二、区间加法

在这里插入图片描述

  • 解题:
    1.只需将差分数组类导入
    2.在编写以下代码:
int[] getModifiedArray(int length, int[][] updates) { 
   
 	// nums 初始化为全 0
 	int[] nums = new int[length];
 	// 构造差分解法
 	Difference df = new Difference(nums); 
 	for (int[] update : updates) { 
   
 		int i = update[0];
 		int j = update[1];
 		int val = update[2];
 		df.increment(i, j, val);
  	}
  	return df.result();
}

三、航班预订系统

  • 航班预定系统
    在这里插入图片描述
  • 分析:
    1.给你输⼊⼀个⻓度为 n 的数组 nums,其中所有元素都是 0。再给你输⼊⼀个 bookings,⾥⾯是若⼲三元组(i,j,k),每个三元组的含义就是要求你给 nums 数组的闭区间 [i-1,j-1] 中所有元素都加上 k。请你返回最后的 nums 数组是多少?
    2.题目说座位是从1开始的,但差分树组是从0开始的所以这里的i,j都得-1.
  • 解题:
    1.只需将差分数组类导入
    2.在编写以下代码:
// 差分数组⼯具类
class Difference { 
   
    // 差分数组
    private int[] diff;
    //构建拆分数组
    public Difference(int nums[]){ 
   
        assert nums.length >0;
        diff=new int[nums.length];
        diff[0]=nums[0];
        for(int i=1;i<nums.length;i++){ 
   
            diff[i]=nums[i]-nums[i-1];
        }
    }
    /* 给闭区间 [i,j] 增加 val(可以是负数)*/
    public void increment(int i, int j, int val) { 
   
        diff[i]+=val;
        if(j+1<diff.length){ 
   
            diff[j+1]-=val;
        }
    }
    public int[] reslut(){ 
   
        int res[]=new int[diff.length];
        res[0]=diff[0];
        for(int i=1;i<diff.length;i++){ 
   
            res[i]=res[i-1]+diff[i];
        }       
        return res;
    }  
}
class Solution { 
   
    public int[] corpFlightBookings(int[][] bookings, int n) { 
   
        int nums[]=new int [n];
        Difference df=new Difference(nums);
        for(int arr[]:bookings){ 
   
            int i=arr[0]-1;
            int j=arr[1]-1;
            int val=arr[2];
            df.increment(i,j,val);
        }
        return df.reslut();
    }
}
  • 优化:
    1.没有导入数据之前所有数据都是0,所以num[s]=new int[n],将nums看成差分树组,然后遍历航班信息
    2.最后再根据差分数组返回结果

class Solution { 
   
    public int[] corpFlightBookings(int[][] bookings, int n) { 
   
        int nums[]=new int [n];
        for(int arr[]:bookings){ 
   
            int i=arr[0]-1;
            int j=arr[1]-1;
            int val=arr[2];
            nums[i]+=val;
            if(j+1<n){ 
   
                nums[j+1]-=val;
            }
        }
        for (int i = 1; i < n; i++) { 
   
            nums[i] += nums[i - 1];
        }
        return nums;
    }
}

在这里插入图片描述

四、拼车

  • 拼车
    在这里插入图片描述
    在这里插入图片描述
  • 分析:
    1.trips[i] 代表着⼀组区间操作,旅客的上⻋和下⻋就相当于数组的区间加减;只要结果数组中的元素都⼩于 capacity,就说明可以不超载运输所有旅客。
    2.第j站时旅客已经下车了则,j要减1
    3.差分树组的大小为站的个数可以自己写函数算
    4.构建完差分年数组,在反推原结果时可以顺便比较与车乘载人数capacity相比较(因为for循环是从i开始的,第一次上车人数超过时需要重新考虑)
  • 解题:
class Solution { 
   
    public boolean carPooling(int[][] trips, int capacity) { 
   
        int max=0;
        //计算此次中到达最远的栈的编号
        for(int[] trip : trips){ 
   
            max = Math.max(trip[2], max);
        }
        //nums看做差分数组
        int nums[]=new int [max];
        //遍历信息 构建差分树组
        for(int trip[]:trips){ 
   
            int val=trip[0];
            //处理第一次人数大于乘载量的情况
            if(capacity<val) 
                return false;
            //路程是trip[1]-trip[2]-1
            int i=trip[1];
            int j=trip[2]-1;
            
            nums[i]+=val;
            if(j+1<max){ 
   
                nums[j+1]-=val;
            }
            
        }
        //各个
        int res[]=new int[max];
        res[0]=nums[0];
        for(int i=1;i<max;i++){ 
   
            res[i]=nums[i]+res[i-1];
            if(res[i]>capacity) return false;
        }
        return true;
    }
}

在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/140603.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • SQL Server 2000安装教程图解

    SQLServer2000安装教程图解、、、下面网盘链接中的SQL2000数据库在Win7和Win10系统上安装都是可以正常使用的,只不过是Win10上安装的话,需要先替换一下原来C盘中的一个文件而已怎么替换请参考这个:http://www.cnblogs.com/iLoveBurning/p/8639711.html此版本针对XP和Win7系统的,Win…

  • 冰蝎下的反弹shell连接msfconsole

    冰蝎下的反弹shell连接msfconsole文章目录前言一、使用木马getshell1.搭建环境二、冰蝎配置三、kali监听总结前言好久没碰美少妇(MSF)了,恰巧昨天在群里水群,有个表哥问为什么msf监听不到数据。为此我带着表哥的疑问进行了简单的研究。大体的流程和思路我简单记录一下。其中的坑还是不少的,希望这篇文章对初识冰蝎的表哥们有点用处。一、使用木马getshell冰蝎之所以强还是在于他的动态二进制加密。这里呢,在冰蝎下载的包中给出了官方的webshell。在server文件夹下。这里呢,我踩过一个坑。不知道是我电脑配置的问题还是就

  • 51单片机最小系统解读

    51单片机最小系统解读提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录前言一、51单片机最小系统模块构成二、电源电路1.电源引脚三、时钟电路1.外部晶振引脚2.晶振(时钟电路)3.时钟电路小tips四、复位电路1.按键复位2.上电复位总结前言在学习51单片机的时候我们最先接触到的就是单片机最小系统,单片机最小系统又叫最小应用系统,顾名思义就是能够使单片机实现简单运行的最少原件的组合。提示:以下将以51单片机最小系统为例进行介绍一、51单片机最小系统模块构成二、电源电路一个系统的

  • 面试被问selenium自动化模型,你了解多少?

    面试被问selenium自动化模型,你了解多少?

  • 魔兽世界正式服模拟(战地模拟器破解版)

    背景:从06年玩魔兽到现在也13年了。5.48的时候在国外读研、时间特别多,在艾苏恩的“魔兽夜店”lm公会(永远记得这段快乐的时光),围攻奥格达到了我的顶峰(带团),回国后找工作6.X没玩。从7.x就开始咸鱼,H都没通。现在也得结婚成家了。以后更加咸鱼了,指不定哪天就AFK。差不多06年的时候就混迹于大芒果、藏宝湾这两个网站,虽然是高中生,那时候用家里的破电脑就开始搭建单机版,改数据库。晚上在自己…

  • 华为云搭建MQTT服务器

    华为云搭建MQTT服务器文章目录安装emqx查看服务器架构下载EMQX压缩包解压EMQX启动服务启动emqx服务状态查询修改服务器安全策略结果测试EMQX管理后台测试MQTXX测试安装emqxemqx提供一个可视化的控制台接口,使用比较方便,所以首推使用emqx作为服务器软件。查看服务器架构首先查看自己服务器的架构,在命令行中输入:dpkg–print-architecture结果如下:下载EMQX压缩包前往EMQX的官网下载对应版本的压缩包https://www.emqx.io/downloads/brok

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号