Leetcode 56. 合并区间和Leetcode 240. 搜索二维矩阵 II

Leetcode 56. 合并区间

题目描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

C语言题解和思路

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int cmp(int** a,int** b){
    return (a[0][0] > b[0][0]);   
}
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){

int **ret = (int **)malloc(sizeof(int *) * intervalsSize);
*returnColumnSizes = (int *)malloc(sizeof(int) * intervalsSize);
for(int i = 0; i < intervalsSize; i++)
{
    ret[i] = malloc(sizeof(int) * 2); 
    returnColumnSizes[0][i]=2;
}
qsort(intervals,intervalsSize,sizeof(intervals[0]),cmp);
int count = 1;
ret[0][0] = intervals[0][0];
ret[0][1] = intervals[0][1];
for(int i = 1;i<intervalsSize;i++)
{
    if(ret[count - 1][1] < intervals[i][0])
    {
        ret[count++] = intervals[i];
    }
    else
    {
        if(ret[count - 1][1] < intervals[i][1])
        {
            ret[count - 1][1] = intervals[i][1];
        }
    }
}
*returnSize = count;
return ret;
}

解题思路

首先创建用来返回的数组 ret 并通过for循环给它开辟空间。

用qsort函数将二维数组 intervals 按第一个数字的大小进行升序排序。

先将数组 intervals 的第一行传给数组 ret ，遍历数组 intervals 的每一行，如果该行的第一个数大于 ret 数组最新一行的第二个数，将 intervals 数组该行传入 ret 数组中；否则再去判断数组 intervals 该行的第二个数是否大于数组 ret 该行的第二个数，如果是，将数组 intervals 该行的第二个数赋值给数组 ret 该行的第二个数。

将记录数组 ret 传入次数的变量 count 的值赋给指针returnSize。

返回数组 ret 。

Leetcode 240. 搜索二维矩阵 II

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -109 <= matrix[i][j] <= 109
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -109 <= target <= 109

C语言题解和思路

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    int i = matrixSize - 1, j = 0;
    while (i >= 0 && j< *matrixColSize)
    {
        if (matrix[i][j] == target)
        {
            return true;
        }
        else if (matrix[i][j] > target)
        {
            i--;
        }
        else
        {
            j++;
        }
    }
    return false;
}

解题思路

从左下角开始遍历数组，如果数组该位置的值大于 target ，向上查找，如果数组该位置的值小于于 target ，向右查找，如果数组该位置的值等于 target ，返回 true 。

如果遍历到第一行或最后一列还没找到 target ，循环结束，返回 false 。