差分数组
2023-04-22 10:59:00 时间
题目 | 难度 | 要点 |
---|---|---|
拼车 | ● | 不需要构造原始数组,直接判断即可 |
航班预定统计 | ● | 构造原始数组 |
区间加法 | ● | 构造原始数组 |
差分数组中,diff[i] 就是 nums[i] 和 nums[i-1] 之差;diff[0] = nums[0];
拼车
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
Diff diff = new Diff(1001);
for (int[] trip: trips) {
diff.inc(trip[0], trip[1], trip[2]);
}
return diff.check(capacity);
}
}
class Diff {
private int size;
private int[] diff;
public Diff(int size) {
this.size = size;
this.diff = new int[size];
}
public void inc(int val, int start, int end) {
diff[start] += val;
diff[end] -= val;
}
public boolean check(int capacity) {
int sum = diff[0];
for (int i = 1; i < diff.length; i++) {
if (sum > capacity) {
return false;
}
sum += diff[i];
}
return sum <= capacity;
}
}
航班预定统计
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
Diff diff = new Diff(n);
for (int[] booking: bookings) {
diff.inc(booking[2], booking[0] - 1, booking[1] - 1);
}
return diff.revert();
}
}
class Diff {
private int size;
private int[] diff;
public Diff(int size) {
this.size = size;
this.diff = new int[size];
}
public void inc(int val, int start, int end) {
diff[start] += val;
if (end + 1 < diff.length) {
diff[end + 1] -= val;
}
}
public int[] revert() {
int[] sum = new int[diff.length];
sum[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
sum[i] = sum[i - 1] + diff[i];
}
return sum;
}
}
区间加法
class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
Diff diff = new Diff(length);
for (int[] update: updates) {
diff.inc(update[0], update[1], update[2]);
}
return diff.revert();
}
}
class Diff {
private int size;
private int[] diff;
public Diff(int size) {
this.size = size;
this.diff = new int[size];
}
public void inc(int start, int end, int val) {
diff[start] += val;
if (end + 1 < diff.length) {
diff[end + 1] -= val;
}
}
public int[] revert() {
int[] sum = new int[diff.length];
sum[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
sum[i] = sum[i - 1] + diff[i];
}
return sum;
}
}
相关文章
- HCIP-GRE与MGRE
- 剑指 Offer 58 - II. 左旋转字符串
- WebSecurityConfigurerAdapter已弃用
- toString方法使用
- 项目中pom.xml文件变灰且中间有横杠改怎么解决?
- 二分查找法
- jdk11 下载与安装(非常详细,一步不落!!!)
- 力扣中77 组合
- RocketMq常见面试题
- 2022最新最全IntelliJ IDEA 的安装与配置
- MySQL8超详细安装教程
- RazorEngine实现代码生成器
- IntelliJ IDEA 2022.1 安装教程
- 【Spring】一文带你吃透AOP面向切面编程技术(上篇)
- 关于sys的包管理
- 99复习
- Java IO流 - 缓冲流的详细使用介绍
- IDEA 2022 创建 Spring Boot 项目详解
- SpringMVC WEB项目文件夹上传下载解决方案
- diff -Naur