构造差分数组
int* constructDifferenceArray(int* nums, int length) {
int* diff = (int*)malloc(length * sizeof(int));
diff[0] = nums[0];
for (int i = 1; i < length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
return diff;
}
通过这个 diff 差分数组是可以反推出原始数组 nums 的，代码逻辑如下：
// 构造结果数组
int* constructResultArray(int* diff, int length) {
int* res = (int*)malloc(length * sizeof(int));
res[0] = diff[0];
for (int i = 1; i < length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
这样构造差分数组 diff，就可以快速进⾏区间增减的操作，如果你想对区间 nums[i..j] 的元素全部加
3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可
原理很简单，回想 diff 数组反推 nums 数组的过程，diff[i] += 3 意味着给 nums[i..] 所有的元素都
加了 3，然后 diff[j+1] -= 3 ⼜意味着对于 nums[j+1..] 所有元素再减 3，那综合起来，是不是就是对
nums[i..j] 中的所有元素都加 3 了？
只要花费 O(1) 的时间修改 diff 数组，就相当于给 nums 的整个区间做了修改。多次修改 diff，然后通过
diff 数组反推，即可得到 nums 修改后的结果。
区间加法
#include <stdio.h>
#include <stdlib.h>
// 结构体表示差分数组
typedef struct {
int* array;
int length;
} Difference;
// 初始化差分数组
Difference* initDifferenceArray(int length) {
Difference* df = (Difference*)malloc(sizeof(Difference));
df->array = (int*)malloc(length * sizeof(int));
df->length = length;
for (int i = 0; i < length; i++) {
df->array[i] = 0;
}
return df;
}
// 实现 increment 函数
void increment(Difference* df, int start, int end, int val) {
df->array[start] += val;
if (end + 1 < df->length) {
df->array[end + 1] -= val;
}
}
// 计算结果数组
int* result(Difference* df) {
int* res = (int*)malloc(df->length * sizeof(int));
int sum = 0;
for (int i = 0; i < df->length; i++) {
sum += df->array[i];
res[i] = sum;
}
return res;
}
int* getModifiedArray(int length, int updates[][3], int updatesLength) {
// 初始化差分数组
Difference* df = initDifferenceArray(length);
// 构造差分数组
for (int i = 0; i < updatesLength; i++) {
int start = updates[i][0];
int end = updates[i][1];
int val = updates[i][2];
increment(df, start, end, val);
}
// 计算结果数组
int* res = result(df);
// 释放内存
free(df->array);
free(df);
return res;
}
int main() {
int updates[3][3] = { {1, 3, 2}, {2, 4, 3}, {0, 2, -2} };
int length = 5;
int updatesLength = sizeof(updates) / sizeof(updates[0]);
// 获取修改后的数组
int* modifiedArray = getModifiedArray(length, updates, updatesLength);
// 输出修改后的数组
printf("修改后的数组：");
for (int i = 0; i < length; i++) {
printf("%d ", modifiedArray[i]);
}
printf("\n");
// 释放内存
free(modifiedArray);
return 0;
}
航班预订统计
一样
拼车
你是⼀个开公交⻋的司机，公交⻋的最⼤载客量为 capacity，沿途要经过若⼲⻋站，给你⼀份乘客⾏程表
int[][] trips，其中 trips[i] = [num, start, end] 代表着有 num 个旅客要从站点 start 上⻋，
到站点 end 下⻋，请你计算是否能够⼀次把所有旅客运送完毕（不能超过最⼤载客量 capacity）。
#include <stdio.h>
#include <stdlib.h>
// 结构体表示差分数组
typedef struct {
int* array;
int length;
} Difference;
// 初始化差分数组
Difference* initDifferenceArray(int length) {
Difference* df = (Difference*)malloc(sizeof(Difference));
df->array = (int*)malloc(length * sizeof(int));
df->length = length;
for (int i = 0; i < length; i++) {
df->array[i] = 0;
}
return df;
}
// 实现 increment 函数
void increment(Difference* df, int start, int end, int val) {
df->array[start] += val;
if (end + 1 < df->length) {
df->array[end + 1] -= val;
}
}
// 计算结果数组
int* result(Difference* df) {
int* res = (int*)malloc(df->length * sizeof(int));
int sum = 0;
for (int i = 0; i < df->length; i++) {
sum += df->array[i];
res[i] = sum;
}
return res;
}
// 判断是否能完成乘客运送
int carPooling(int trips[][3], int tripsLength, int capacity) {
// 初始化差分数组
Difference* df = initDifferenceArray(1001);
// 构造差分数组
for (int i = 0; i < tripsLength; i++) {
int val = trips[i][0];
int start = trips[i][1];
int end = trips[i][2] - 1;
increment(df, start, end, val);
}
// 计算结果数组
int* res = result(df);
// 客车自始至终都不应该超载
for (int i = 0; i < 1001; i++) {
if (capacity < res[i]) {
free(df->array);
free(df);
free(res);
return 0;
}
}
free(df->array);
free(df);
free(res);
return 1;
}
int main() {
int trips[3][3] = {{2, 1, 5}, {3, 3, 7}, {3, 8, 10}};
int capacity = 4;
int tripsLength = sizeof(trips) / sizeof(trips[0]);
// 是否能完成乘客运送
int result = carPooling(trips, tripsLength, capacity);
// 输出结果
if (result) {
printf("能够一次把所有旅客运送完毕\n");
} else {
printf("不能一次把所有旅客运送完毕\n");
}
return 0;
}