leetcode中等题-贪心算法（C语言）

1.

解题记录： 1.根据示例可以发现，每次到达下一站i+1站的油量，是当前油量+gas[i]-cost[i]的结果，如果这个结果<0，说明没法走到下一站。 2.比较好理解的暴力法是每一次遍历都走一轮，若走完则输出start，若都无法走完就输出-1，这种情况复杂度为O（n²）。 3.可以思考一下，如果start站出发，最远可以走到i站，那么start站到i站之间的站都无法走完一圈，因为这之间的站如果能走完一圈，说明start站是能走到i+1站的，就矛盾了，所以start的下一次，就可以直接从start+i+1站开始查找，这种时间复杂度就只有O（n）。

C语言代码：

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
          
   
    int start = 0, i;//start记录开始索引位置
    while (start < gasSize)
    {
          
   //只需一轮遍历
        int gasbox = 0;//油量
        for (i = 0; i < gasSize; i++)
        {
          
   
            int index = (start + i) % gasSize;//循环取索引
            gasbox = gasbox + gas[index] - cost[index];
            if (gasbox < 0)
                break;
        }
        if (i == gasSize)
            return start;
        else
            start += (i + 1);//start只能走到i，那么start到i之间的索引都不能走完一圈
    }
    return -1;
}

2.

解题记录： 1.该题有点类似于56题合并区间，那题是合并，这题是“拆解”，思路是差不多的，都是先排序，再比较后一区间的最小值和当前区间的最大值。 2.不同之处在于这题需要按照数组的第二列排序，也就是按照区间的最大值排序，使用的思想就是贪心算法，这样可以使得范围较小的区间尽量排在前面。 3.每次比较，如果后一区间最小值比当前end值大，那么就没有重叠，num可以计数，直到比较完成，num的数就是不重叠的区间个数，区间总数相减得到的就是去除的区间个数。

C语言代码：

int cmp(const void *a, const void *b)
{
          
   //自定义的升序排序函数
//按第二列，也就是每个区间的最大值升序排序
    return (*(int**)a)[1] - (*(int**)b)[1];
}

int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize){
          
   
    int i, j, num = 1;//num记录有多少不重复的区间
    if (intervalsSize == 0 || intervalsSize == 1)
        return 0;
    //按区间最大值升值排序后可以使小范围的区间尽量排在前面
    qsort(intervals, intervalsSize, (*intervalsColSize) * sizeof(int), cmp);
    int end = intervals[0][1];
    for (i = 0; i < intervalsSize - 1; i++)
    {
          
   //每次比较后一区间的最小值和end值，若大则不重叠
        if (intervals[i+1][0] >= end)
        {
          
   
            num++;
            end = intervals[i+1][1];
        }
    }
    return intervalsSize - num;//总数-不重叠数即为需要去掉的区间数
}