55. 跳跃游戏/ 1109. 航班预订统计

55. 跳跃游戏

• 相关标签 ： 数组， 贪心算法

/*
思路： 
1 暴力的话
    可以 写个递归 每次 递归当前 从 1 到 最大长度
        递归出口就是 当前点 是最后一个点  理论上会超时 -- 结果确实超时了  pass  70/75
        
2. 换思路 

拿 第二个举例 
0 1 2 3 4 
----------
3 2 1 0 4


curIdx = 0 
    1(1)
        1(2)
            0
        2(3)
            0
    2(2)
        1(3)
            0
    3(3)
        0 看不出  =_=
        
0 1 2 3 4 
----------
2 3 1 1 4

curIdx = 0 
    1(1)
        1(2)
            1(3)
                1(4) OK
        2(3)
            1(4) OK
        3(4) OK 
    
    2(2)
        1(3)
            1(4) OK  看大有很多重叠的 
可能可以DP 从 后往前 
DP[i] 就表示 是否可以到达把 

行不通 

那 DP[i] 就表示 当前点的最大跳跃距把 如果 DP[n-1]> 1 的话 那么 DP[n] 可以到达 

*/



// void recur(int* nums, int numsSize, int curIdx, int *res)
// {
//     if (curIdx >= numsSize) {
//         return;
//     }
//     // exit
//     if (curIdx == numsSize - 1) {
//         *res = 1;
//     }
    
//     //curIdx = 0, maxjumplen = nums[0] = 2, jump 0 +1 or o + 2
//     for (int i = 1; i <= nums[curIdx]; i++) {
//         recur(nums, numsSize, curIdx + i, res);
//     }
// }

// bool canJump(int* nums, int numsSize){
//     int res = 0;
//     recur(nums, numsSize, 0, &res);
//     return res;
// }



#define BUFLEN 1000000
#define MAX(x,y) ((x > y) ? x : y)
bool canJump(int* nums, int numsSize){
    
    if (numsSize == 1) {
        return true;
    }
    
    int dp[BUFLEN] = {0};
    // dp 0 ~ n-1
    for (int i = 0; i < numsSize -1 ; i++) {
        dp[i + 1] = MAX(dp[i] - 1, nums[i]); 
        if (dp[i + 1] == 0) { // 过程中 如果有 值为0  那么直接退出
            return false;
        }
    }

    return dp[numsSize - 1] > 0;
}

1109. 航班预订统计

• 相关标签 ： 数组 数学

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

/*
1. 暴力的话呢 就。。。 pass 60/63 哎 考试的时候还不如写个超时方法呢。。。。
*/
// int* corpFlightBookings(int** bookings, int bookingsSize, int* bookingsColSize, int n, int* returnSize){
    
//     int *res = (int *)malloc(sizeof(int) * n);
//     memset(res, 0, sizeof(int) * n);
//     *returnSize = n;
//     int a, b, c;
//     for (int i = 0; i < bookingsSize; i++) {
//         a = bookings[i][0];
//         b = bookings[i][1];
//         c = bookings[i][2];
        
//         for (int j = a; j <= b; j ++) {
//             res[j - 1] += c;
//         }
//     }
    
//     return res;

// }

// 2. n2 不行 那就是 只能0（n)了 意味着 对 i,j K只能有O（1） 的操作 
// 那我们 可以把 i 记录在表里面 反正 后面 重新遍历一次 都会累加上 
/*
1   2   3   4   5
10
    20
    25
------------------
10  55  55  55  55


但是 就 [1,2,5]来说 ， 他到 3 这边就不应该在 加10 了 
1   2   3   4   5
10      -10
    20
    25
------------------
10  55  45  45  45

同理 [2,3,20 ]也一样 他在 4 就不应该在累加了 
1   2   3   4   5
10      -10
    20      -20
    25
------------------
10  55  45  25  25

[2,5,25]就不需要了 因为 b == 5 == n

*/
int* corpFlightBookings(int** bookings, int bookingsSize, int* bookingsColSize, int n, int* returnSize){
    
    int *res = (int *)malloc(sizeof(int) * n);
    memset(res, 0, sizeof(int) * n);
    *returnSize = n;
    int a, b, c;
    
    for (int i = 0; i < bookingsSize; i++) {
        a = bookings[i][0];
        b = bookings[i][1];
        c = bookings[i][2];
        
        res[a - 1] += c;
        if (b != n) {
            res[b] -= c;
        }   
    }
    
    for (int i = 1; i < n; i++) {
        res[i] += res[i - 1]; //加上之前的累加值
    }

    return res;

}