[差分数组] LeetCode789 得分最高的最小轮调
2024-10-16 14:33:57
LeetCode 得分最高的最小轮调
今天当然CV了因为今天比较忙,所以直接走算法,因为什么都不做的话并不符合社会主义核心价值观,今天小学一手查分数组。
题目:并不存在CV了还写什么题解
算法背景:
本着一切从简的原则,今天就直接开门见山的说了,查分数组就是为了解决大量数据的批量操作问题,场景:现在又很大的一组数组,然后让我们从1到100W加1,那么我们如果一个一个做的话o(n)的复杂度对于这个题目背景来说显然很不人道,所以在这里引入了一个人道的数组,array[y] 来记做查分数组,对于数组的每个元素,array[i] = original[i]-original[i-1](特别的当i==0的时候Original[i-1]记做0)那么我们将得到一个数组时原先数组的邻位差(一般高位减地位),而在这时我们回到原先的问题,当1~100W的位置的数同时加a的时候,显然其中查分数组只有两位发生变化,为了规范化的标记两个查分数组变化位置我们将原来的变化左右区间的端点值分为计为low位和high为,那么差分数组此时的变化就记做array[low] + a ;array[heigh+1] + a;
获取元数组的值 :array[i] = original[i]-original[i-1]直接用介个公式自己吧 Original 移动到等号的一侧,答案那是显而易见。
最新文章
- to_date &; to_char
- python 3 学习笔记 (三)
- 从感知器到SVM
- StringByAppendingPathComponent和stringByAppendingString的区别
- thinkphp的html模板中if的使用
- Android学习笔记02
- SQL server 时间处理自连接
- powermockito “mock public 方法内部 Private方法的问题”
- WPF中DataGrid的ComboBox的简单绑定方式(绝对简单)
- CoreAnimation3-专用图层
- linux安装Eclipse c++环境
- Spring cloud之Eureka(二)注册中心高可用
- Tensorflow object detection API ——环境搭建与测试
- nodeJs express mongodb 建站(mac 版)
- Windows10家庭版连接远程桌面出现credssp加密oracle修正问题
- 数据库构架设计中的Shared Everthting、Shared Nothing、和Shared Disk
- C语言上机练习二
- Go语言学习之8 goroutine详解、定时器与单元测试
- day7 回顾
- linux下时间问题---date