升序|结尾_LeetCode刷题笔记数据结构day4

篇首语：本文由编程笔记#自由互联小编为大家整理，主要介绍了LeetCode刷题笔记-数据结构-day4相关的知识，希望对你有一定的参考价值。文章目录

篇首语：本文由编程笔记#自由互联小编为大家整理，主要介绍了LeetCode刷题笔记-数据结构-day4相关的知识，希望对你有一定的参考价值。

文章目录

• LeetCode刷题笔记-数据结构-day4
• • 240.搜索二维矩阵 II
  • • 1.题目描述
    • 2.解题思路
    • 3.代码
  • 435.无重叠区间
  • • 1.题目描述
    • 2.解题思路
    • 3.代码

LeetCode刷题笔记-数据结构-day4

240.搜索二维矩阵 II

1.题目描述

原题链接240. 搜索二维矩阵 II

2.解题思路

题目说了矩阵两个重要的性质

• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列

根据性质。我们可以发现如果从右上角出发初始化i 0,j m - 1

若matrix[i][j] target返回true

若matrix[i][j] > target向左走j--

若matrix[i][j]

如果出界返回false

最终的时间复杂度为O(nm)符合题目要求

3.代码

class Solution public: bool searchMatrix(vectorv.size(),mv[0].size(); int i0,jm-1; while(i0) if(v[i][j]t) j--; else return true; return false; ;

435.无重叠区间

1.题目描述

原题链接435. 无重叠区间

2.解题思路

算法贪心

具体思路

按照区间右端点排序

选择的区间结尾越小余留给其它区间的空间就越大就越能保留更多的区间所以这里使用右端点排序。优先保留结尾小且不相交的区间。这样保留的区间也更多从而需要移除的区间就越少

3.代码

class Solution public: int eraseOverlapIntervals(vector ); int edv[0][1]; int res0; for(int i1;i