java数据结构与算法刷题-----LeetCode1109：航班预订统计

1. 思路分析

差分数组，具体看代码注释

2. 代码
   

class Solution {
    /**
        差分数组
        让差分数组直接成为结果
        对差分数组求前缀和即可得到原数组
        ===============题目示例如下====================
        航班编号        1   2   3   4   5
        预订记录 1 ：   10  10
        预订记录 2 ：       20  20
        预订记录 3 ：       25  25  25  25
        总座位数：      10  55  45  25  25
        因此，answer = [10,55,45,25,25]


        推导过程如下，不好理解，反正就是arr[1]的正确答案 = arr[0]+arr[1],arr[2] = arr[0]+arr[1]+arr[2],依次类推...
        满足这个公式就可以,比较复杂，不如换一种理解思路（正紧的推导放在下面）
        =====================简单的理解思路
        bookings[i] = [上飞机, 下飞机, 多少人]。终点站不上不下，只统计还在飞机的人数
        1~2,10。这个为例
        第一站上飞机10个人，第2站下飞机10人。也就是第三站少了10个人，他们还是坐到了第二站的
        第四、五站，没下人
        因此[+10,+0,-10,+0,+0]就是结果
        ====================第二次
        2~3,20。
        第2站上飞机20个，第3站下20个，也就是第3站少了20个
        结合第一个结果进行计算
        [10,0,-10,0,0]
        [+0,+20,+0,-20,+0]得到结果
        [10,20,-10,-20,0]
        ===================第三次
        2~5,25
        第2站上25个，第5站是终站，不上不下
        [10,20,-10,-20,0]
        [+0,+25,+0,+0,+0]
        [10,45,-10,-20,0]
        ==================接下来进行分析（正紧的推导放在下面）================
        第一次，区间1~2，都是10。我们要保证差分数组每个元素最终结果等于前缀和。因此，构建时arr[1] = arr[0]+arr[1] = 10 因此arr[1] 应该为0，arr[2] = 0 = arr[0]+arr[1]+arr[2] => arr[2]+10 = 0 => arr[2] = -10
            arr[3] = 0,arr[4] = 0;同理
        第二次，区间2~3，都是20，依然保证最终结果为前缀和，arr[1] = 30 =  10+20，arr[1] = 20。
                arr[2] = 20 = arr[0] + arr[1] + arr[2] => arr[2]+30 = 20 => arr[2] = -10。
                arr[3] = 0 = arr[3]+10-10+20 => arr[3] = -20
        第三次，区间2~5，都是25，保证前缀和
                arr[1] = 55 = arr[0]+arr[1] => arr[1]+10 = 55 => arr[1] = 45
                arr[2] = 45 = arr[2] + 10 + 45 => arr[2] = -10
                arr[3] = 25 = arr[3] + 45 => arr[3] = -20
                arr[4] = 25 = arr[4] + 10 + 45 -10 -20 => arr[4] = 0
        5这个位置正好是最后一个元素，无需计算，因为它正好是前面的前缀和
        最后的差值数组应该是[10,45,-10,-20,0]

        
     */
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int answer[] = new int[n];
        //answer[1,2,10],[2,3,20],[2,5,25]
        /**
            i=0, [10,0 ,-10,0  ,0]
            i=1, [10,20,-10,-20,0]
            i=2, [10,45,-10,-20,0]
         */
        for (int i = 0;i< bookings.length;i++){
            answer[bookings[i][0]-1]+=bookings[i][2];//上飞机直接记录
            //下飞机，下一站再减人。终点站n不上不下
            if (bookings[i][1]<n) answer[bookings[i][1]] -= bookings[i][2];
        }
        /**
                 [10,45,-10,-20,0]
            i=1, [10,55,-10,-20,0]
            i=2, [10,55, 45,-20,0]
            i=3, [10,55, 45, 25,0]
            i=4, [10,55, 45, 25,25]
         */
        for (int i = 1;i<n;i++){
            answer[i]+=answer[i-1];
        }
        return answer;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

刷题一定要坚持，总结套路，不单单要把题做出来，要举一反三，也要参考别人的思路，学习别人解题的优点，找出你觉得可以优化的点。

1. 单链表解题思路：双指针、快慢指针、反转链表、预先指针

1. 双指针：对于单链表而言，可以方便的让我们遍历结点，并做一些额外的事
2. 快慢指针：常用于找链表中点，找循环链表的循环点，一般快指针每次移动两个结点，慢指针每次移动一个结点。
3. 反转链表：通常有些题，将链表反转后会更好做，一般选用三指针迭代法，递归的空间复杂度有点高
4. 预先指针：常用于找结点，比如找倒数第3个结点，那么定义两个指针，第一个指针先移动3个结点，然后两个指针一起遍历，当第一个指针遍历完成，第二个指针指向的结点就是要找的结点

2. 数组解题思路：双指针、三指针，下标标记

1. 双指针：多用于减少时间复杂度，快速遍历数组
2. 三指针：多用于二分查找，分为中间指针，左和右指针
3. 下标标记：常用于在数组范围内找东西，而不想使用额外的空间的情况，比如找数组长度为n，元素取值范围为[1,n]的数组中没有出现的数字，遍历每个元素，然后将对应下标位置的元素变为负数或者超出[1,n]范围的正数，最后没有发生变化的元素，就是缺少的值。
4. 差分数组：对差分数组求前缀和即可得到原数组

1. 用差值，作为下标，节省空间找东西。比如1900年到2000年，就可以定义100大小的数组，每个数组元素下标的查找为1900。
2. 前缀和数组，对于数组 [1,2,2,4]，其差分数组为 [1,1,0,2]，差分数组的第 ii个数即为原数组的第 i-1 个元素和第 i个元素的差值，也就是说我们对差分数组求前缀和即可得到原数组

5. 前缀和：假设有一个数组arr[1,2,3,4]。然后创建一个前缀和数组sum，记录从开头到每个元素区间的和。第一个元素是0。第二个元素，保存第一个和sum[1] = sum[0]+arr[0]，第二个元素，保存第二个和sum[2] = sum[1]+arr[1]

3. 栈解题思路：倒着入栈，双栈

1. 倒着入栈：适用于出栈时想让输出是正序的情况。比如字符串’abc’，如果倒着入栈，那么栈中元素是（c,b,a）。栈是先进后出，此时出栈，结果为abc。
2. 双栈：适用于实现队列的先入先出效果。一个栈负责输入，另一个栈负责输出。