本文主要是介绍Leetcode 56. 合并区间和Leetcode 240. 搜索二维矩阵 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- Leetcode 56. 合并区间
- 题目描述
- C语言题解和思路
- 解题思路
- Leetcode 240. 搜索二维矩阵 II
- 题目描述
- C语言题解和思路
- 解题思路
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 。
这篇关于Leetcode 56. 合并区间和Leetcode 240. 搜索二维矩阵 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!