leetcode1109. 航班预订统计

刺骨的言语ヽ痛彻心扉 2022-09-09 11:53 164阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_16_color_FFFFFF_t_70_g_se_x_16]  
思路

1.  暴力
2.  前缀和

暴力解

int* corpFlightBookings(int** bookings, int bookingsSize, int* bookingsColSize, int n, int* returnSize){ 
        int i,min_v = 65536,max_v=0;
        int *res = (int*)malloc(n*sizeof(int));
        memset(res,0,sizeof(int)*n);
        int t=0;
        for(i=0;i<bookingsSize;i++){ 
            for(t = bookings[i][0];t<=bookings[i][1];t++){ 
                res[t-1]+=bookings[i][2];
            }
        }
        *returnSize = n;
        return res;
    }

前缀和  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_18_color_FFFFFF_t_70_g_se_x_16]

int* corpFlightBookings(int** bookings, int bookingsSize, int* bookingsColSize, int n, int* returnSize){ 
        int i,min_v = 65536,max_v=0;
        int *res = (int*)malloc(n*sizeof(int));
        memset(res,0,sizeof(int)*n);
        int t=0;
        for(i=0;i<bookingsSize;i++){ 
            res[bookings[i][0]-1]+=bookings[i][2];
            if(bookings[i][1]<n)
                res[bookings[i][1]]-=bookings[i][2];
        }
        for(i=1;i<n;i++)
            res[i] = res[i]+res[i-1];
        *returnSize = n;
        return res;
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/3d8879d221a34d668ca824f3d2e12aff.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/e0ae6464ecfa44b29bd9b0e0b3a78042.png