差分法(在区间范围内增加数值)

差分法(在区间范围内增加数值)

 

 话不多说,直接看差别,下面用的暴力法,上面是用差分法,数学问题,其实也没太看懂具体什么原理

看程序,只能有一点粗浅的认识

差分法(在区间范围内增加数值)

 

 

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

首先看第五行,只把所有要变化区间的头增加这些值

第七行,是将区间变化区间的末端后一个元素减掉增加值

再看第十行,将现有的数组所有元素后面的加上前一个元素的值,前面已经对末端后一个提前减值,所以不会有多加的现象

差分法(在区间范围内增加数值)

上一篇:SSO单点登录-CAS验证


下一篇:[LeetCode] 437. 路径总和 III