已结束

[labuladong]

本期打卡已结算完成。报名最新一期的打卡活动 点这里

[yihaozhong]

370. Range Addition https://leetcode.com/problems/range-addition/solutions/3858867/array-diff-1/

[KenanHuang]

https://leetcode.cn/problems/corporate-flight-bookings/solutions/2372111/chai-fen-qiu-jie-by-qq540453543-li1x/

[Cathy830]

https://leetcode.com/problems/range-addition/solutions/3860347/range-addition-in-java-using-difference-arrays/

[PINKDDDD]

https://leetcode.com/problems/car-pooling/solutions/3860341/car-pooling/ https://leetcode.com/problems/corporate-flight-bookings/solutions/3860364/corpflightingbokkings/

[dh0072]

Q370. Range Addition https://leetcode.com/problems/range-addition/discuss/3860551/Java-O(N-%2B-K)-solution

[Reset0808]

https://leetcode.cn/problems/range-addition/solutions/2372386/chai-fen-shu-zu-by-2ba4zmutle-6fdu/

[wusidong]

https://leetcode.cn/problems/corporate-flight-bookings/solutions/2372403/chai-fen-shu-zu-by-gei-wei-lai-de-zi-ji-lc36a/

[jojoss]

[1094. Car Pooling] https://leetcode.com/problems/car-pooling/solutions/3860686/pre-difference-array/

[ghost]

https://leetcode.cn/problems/corporate-flight-bookings/solutions/2372462/hang-ban-yu-ding-chai-fen-by-alan-aa-vv94/

[GodisinHisHeaven]

https://leetcode.com/problems/corporate-flight-bookings/solutions/3860718/python3-differential-array-solution/

[Chao200]

1094： https://leetcode.cn/problems/car-pooling/solutions/2372522/solution1094-pin-che-by-xiaochao200-h9ph/

1109： https://leetcode.cn/problems/corporate-flight-bookings/solutions/2372465/solution1109-hang-ban-yu-ding-tong-ji-by-wsnc/

[chen-huanxin]

1094：https://leetcode.cn/problems/car-pooling/solutions/2372523/cppchai-fen-shu-zu-0804-1094-pin-che-by-n5vw9/

[zexianw12]

1109 https://leetcode.cn/problems/corporate-flight-bookings/solutions/2372560/li-yong-chai-fen-shu-zu-jie-jue-hang-ban-0zgw/

[macksonyli21826]

https://leetcode.cn/problems/range-addition/solutions/2372645/problem-370-qu-jian-jia-fa-by-hachi-loku-9ula/

[ShaodongGu]

Q1094 https://leetcode.com/problems/car-pooling/solutions/3861136/diff-array/

[hxingjie]

1109.https://leetcode.cn/problems/corporate-flight-bookings/solutions/2372600/hang-ban-yu-ding-tong-ji-by-betodea-u9ey/ 1094.https://leetcode.cn/problems/car-pooling/solutions/2372676/pin-che-by-betodea-uqzb/

[KarlZhu-SE]

https://leetcode.com/problems/car-pooling/solutions/3861282/difference-list-python3/

[Bamoon622]

https://leetcode.com/problems/corporate-flight-bookings/solutions/3860349/using-difference-array/

[wangyin717]

1109. 航班预订统计 https://leetcode.cn/problems/corporate-flight-bookings/solutions/2372764/1109-hang-ban-yu-ding-tong-ji-by-wangyin-68ho/
1110. 拼车 https://leetcode.cn/problems/car-pooling/solutions/2372812/1094-pin-che-by-wangyin717-uh24/

[Catboss1999]

https://leetcode.cn/problems/corporate-flight-bookings/solutions/2372889/chai-fen-shu-zu-de-dian-xing-ying-yong-b-7622/

[sdyin]

1109.航班预订统计 https://leetcode.cn/problems/corporate-flight-bookings/solutions/2372937/1109hang-ban-yu-ding-tong-ji-ti-jie-by-s-r78p/

[Susan19996]

1094 https://leetcode.com/problems/car-pooling/ 1109 https://leetcode.com/problems/corporate-flight-bookings/ 370 https://leetcode.com/problems/range-addition/submissions/

[javaSnacks]

1094 https://leetcode.cn/problems/car-pooling/solutions/2373036/1094-pin-che-by-su-su-shu-shu-vads/

[guabigwind]

拼车： https://leetcode.cn/problems/car-pooling/solutions/2373076/pin-che-by-guabigwind-cexk/

[Adrian0999]

https://leetcode.com/problems/corporate-flight-bookings/solutions/3862427/the-best-solution-i-have-seen-sofar/

[Jingzhenzxz]

https://leetcode.cn/problems/car-pooling/solutions/2373281/chai-fen-shu-zu-by-distracted-buck5nb-vbec/

思路

差分数组和原数组包含的信息是相同的，只是形式不同而已。差分数组中每一个元素都是前面的元素的和，它自带递推的结构。递推的特点是只需要知道第一个元素的信息就可以得到后面的信息，即第一个对象的信息会影响后面的所有对象的信息。而常规数组的各个元素之间的关系是独立的。

复杂度

• 时间复杂度：O(n)

• 空间复杂度：O(n)

Code

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        // 0 <= fromi < toi <= 1000
        int[] nums = new int[1001];
        // 把常规数组转换成差分数组
        Difference diff = new Difference(nums);
        for (int[] trip : trips) {
            // 根据题意修改差分数组，注意第 trip[2] 站乘客已下车
            diff.increment(trip[1], trip[2] - 1, trip[0]);
        }
        // 把修改后的差分数组转换成常规数组
        int[] res = diff.result();
        // 检查修改后的数组是否满足题意，即是否每个元素都小于 capacity
        for (int i = 0; i < res.length; i++) {
            if (res[i] > capacity) {
                return false;
            }
        }
        return true;
    }
}

class Difference {
    private int[] diff;

    // 构造差分数组
    public Difference(int[] nums) {
        int n = nums.length;
        diff = new int[n];
        diff[0] = nums[0];
        for (int i = 1; i < n; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    // 修改差分数组
    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;
    }
}

[txhj1996]

https://leetcode.cn/problems/corporate-flight-bookings/solution/hang-ban-tong-ji-by-6ifted-vvrightj26-9s26/

[AlanKang98]

https://leetcode.cn/problems/car-pooling/solutions/2373433/chai-fen-shu-zu-by-alank-usyd-v3wx/

[ImmersiveAngela]

1094.拼车 https://leetcode.cn/problems/car-pooling/solutions/2373466/pin-che-chai-fen-fa-by-immersiveangela-u2as/

[jiuxi521]

https://leetcode.cn/problems/corporate-flight-bookings/solutions/2373511/chai-fen-shu-zu-by-lean-in-c-pj98/

[LexieZhou]

https://leetcode.com/problems/corporate-flight-bookings/solutions/3863451/java-smart-solutions/

[azDev120]

1109: https://leetcode.com/problems/corporate-flight-bookings/solutions/3863497/java-array-method/

[skyc26]

https://leetcode.cn/problems/corporate-flight-bookings/solutions/2373560/1109-hang-ban-yu-ding-tong-ji-chai-fen-s-e395/

[xueyanyun]

def get_modifyed_array(length: int, updates: List[List[int]]) -> List[int]:
    nums = [0] * length
    df = Difference(nums)

    for update in updates:
        i, j, val = update[0], update[1], update[2]
        df.increment(i, j, val)
    return df.result()

class Difference:
    def __init__(self, nums:List):
        self.diff = [0] * len(nums)
        self.diff[0] = nums[0]

        for i in range(1, len(nums)):
            self.diff[i] = nums[i] - nums[i-1]

    def increment(self, i:int, j:int, val:int)-> Node:
        self.diff[i] += val
        # 当 j+1 >= diff.length 时，nums[i]及以后的整个数组都进行修改，那么就不需要再给diff数组减val了
        if j+1 < len(self.diff):
            self.diff[j+1] += -val

    def result(self)->List[int]:
        res = [0] * len(self.diff)

        res[0] = self.diff[0]
        for i in range(1, len(self.diff)):
            res[i] = res[i-1] + diff[i]
        return res

[yayideng]

https://leetcode.cn/problems/corporate-flight-bookings/solutions/2373648/chai-fen-by-7aughing-i3habhasyh-l8kk/

[Rayden-Xu]

航班预订 https://leetcode.cn/problems/corporate-flight-bookings/solutions/2373667/gou-jian-chai-fen-shu-zu-huan-yuan-yuan-q3s0j/ 核心思想：在开始位置(i-1)加上 k，在结束位置的下一个位置(j-1)减去 k。这样，当我们最终累加差分数组来获得原数组时，只有开始和结束位置之间的航班会真正增加 k 个座位。

    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0] * (n + 1)
# 构造差分数组
        for i, j, k in bookings:
            diff[i - 1] += k  # 所有开始位置之后的元素+上k，i-1是索引值 比如(3,5,10) 这里其实是索引2的元素也就是第三个元素开始 
            if j < n:  # 目的是conner case，如果j是最后一个元素 那么第j+1的元素 [j] 就会越界，所以要确保索引j的元素也就是第j+1个元素是小于数组长度的，
                diff[j] -= k
让i开始的数组全部加k，j+1之后的数组全部减k
        for i in range(n + 1): 遍历 diff数组
            diff[i] += diff[i - 1] diff的前后相加还原原数组
        return diff[:-1]
#还原原数组，因为构造的数组比原数组多1位，所以最后返回把末尾元素剔除。

原数组是 [3,5,8]，它的差分数组是 [3,2,3]。转换回原数组的过程如下： 第1个元素：3 (不变) 第2个元素：3 + 2 = 5 第3个元素：5 + 3 = 8

[vanessacz]

Range Addition: https://leetcode.com/problems/range-addition/solutions/3864804/java-solution-using-difference-array/

[cs-gavin-huang]

https://leetcode.com/problems/car-pooling/solutions/3864955/car-pooling/

[ljrirene]

https://leetcode.com/problems/range-addition/solutions/3865402/difference-array/

[DannyT70]

https://leetcode.cn/problems/corporate-flight-bookings/solutions/2374047/chai-fen-shu-zu-1-by-sleepy-shawffi-o7su/

[Xiaolin8991]

https://leetcode.cn/problems/range-sum-query-immutable/solutions/2374144/python3ti-jie-by-xiao-lin-mz-nes1/

[Pikalili]

https://leetcode.com/problems/car-pooling/solutions/3866027/topic/

[Sadwy]

LC1094. https://leetcode.com/problems/car-pooling/solutions/3866106/topic/

[Abbyyuan01]

https://leetcode.cn/problems/corporate-flight-bookings/solutions/2374274/chai-fen-shu-zu-by-abbyyuan01-4139/

[ConnieLuksc]

https://leetcode.com/problems/car-pooling/solutions/3866415/using-net-difference-to-solve-car-pooling-python/

[Fuyu143]

https://leetcode.com/problems/car-pooling/solutions/3863063/similar-to-range-addition/

[guaZong]

https://leetcode.cn/problems/car-pooling/solutions/2374588/chai-fen-shu-zu-jie-ti-by-gua-xi-xi-8-6zhg/

[imzhuting]

https://leetcode.cn/problems/corporate-flight-bookings/solutions/2374615/chai-fen-shu-zu-by-emilia-8-wbrz/

[tonyzhu163]

https://leetcode.com/problems/range-addition/discuss/3918190/LC-370-Python

[SuperChaoChao666]

370. 区间加法 https://leetcode.cn/problems/range-addition/solutions/2374651/shi-yong-gong-ju-lei-gou-zao-chai-fen-sh-av98/