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

2024-04-13 02:28

本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/898899

相关文章

Python实现合并与拆分多个PDF文档中的指定页

《Python实现合并与拆分多个PDF文档中的指定页》这篇文章主要为大家详细介绍了如何使用Python实现将多个PDF文档中的指定页合并生成新的PDF以及拆分PDF,感兴趣的小伙伴可以参考一下... 安装所需要的库pip install PyPDF2 -i https://pypi.tuna.tsingh

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

使用Apache POI在Java中实现Excel单元格的合并

《使用ApachePOI在Java中实现Excel单元格的合并》在日常工作中,Excel是一个不可或缺的工具,尤其是在处理大量数据时,本文将介绍如何使用ApachePOI库在Java中实现Excel... 目录工具类介绍工具类代码调用示例依赖配置总结在日常工作中,Excel 是一个不可或缺的工http://

使用Python创建一个能够筛选文件的PDF合并工具

《使用Python创建一个能够筛选文件的PDF合并工具》这篇文章主要为大家详细介绍了如何使用Python创建一个能够筛选文件的PDF合并工具,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录背景主要功能全部代码代码解析1. 初始化 wx.Frame 窗口2. 创建工具栏3. 创建布局和界面控件4

CSS3 最强二维布局系统之Grid 网格布局

《CSS3最强二维布局系统之Grid网格布局》CS3的Grid网格布局是目前最强的二维布局系统,可以同时对列和行进行处理,将网页划分成一个个网格,可以任意组合不同的网格,做出各种各样的布局,本文介... 深入学习 css3 目前最强大的布局系统 Grid 网格布局Grid 网格布局的基本认识Grid 网

Python自动化办公之合并多个Excel

《Python自动化办公之合并多个Excel》在日常的办公自动化工作中,尤其是处理大量数据时,合并多个Excel表格是一个常见且繁琐的任务,下面小编就来为大家介绍一下如何使用Python轻松实现合... 目录为什么选择 python 自动化目标使用 Python 合并多个 Excel 文件安装所需库示例代码

使用Python合并 Excel单元格指定行列或单元格范围

《使用Python合并Excel单元格指定行列或单元格范围》合并Excel单元格是Excel数据处理和表格设计中的一项常用操作,本文将介绍如何通过Python合并Excel中的指定行列或单... 目录python Excel库安装Python合并Excel 中的指定行Python合并Excel 中的指定列P

基于C#实现PDF文件合并工具

《基于C#实现PDF文件合并工具》这篇文章主要为大家详细介绍了如何基于C#实现一个简单的PDF文件合并工具,文中的示例代码简洁易懂,有需要的小伙伴可以跟随小编一起学习一下... 界面主要用于发票PDF文件的合并。经常出差要报销的很有用。代码using System;using System.Col

Python视频剪辑合并操作的实现示例

《Python视频剪辑合并操作的实现示例》很多人在创作视频时都需要进行剪辑,本文主要介绍了Python视频剪辑合并操作的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录介绍安装FFmpegWindowsMACOS安装MoviePy剪切视频合并视频转换视频结论介绍

不删数据还能合并磁盘? 让电脑C盘D盘合并并保留数据的技巧

《不删数据还能合并磁盘?让电脑C盘D盘合并并保留数据的技巧》在Windows操作系统中,合并C盘和D盘是一个相对复杂的任务,尤其是当你不希望删除其中的数据时,幸运的是,有几种方法可以实现这一目标且在... 在电脑生产时,制造商常为C盘分配较小的磁盘空间,以确保软件在运行过程中不会出现磁盘空间不足的问题。但在