[day8] [LeetCode] [title435,5]

435. 无重叠区间

给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。

区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。

示例 1:

输入:         [ [1,2], [2,3], [3,4], [1,3] ]            输出:        1

解释:        移除 [1,3] 后,剩下的区间没有重叠。

示例 2:

输入:         [ [1,2], [1,2], [1,2] ]                     输出:         2

解释:         你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入:          [ [1,2], [2,3] ]                              输出:         0

解释:          你不需要移除任何区间,因为它们已经是无重叠的了。

超时程序(程序正确)


超时程序 Paet1
超时程序 Paet2


超时程序Part 3


超时(好气,总剩下最后一个超时)

于是,把程序优化了一下:

正确的程序(贪心算法):


正确的程序Part 1


正确的程序 Part2


哈哈~~~


时间复杂度(拖了后腿了~~~)


5. 最长回文子串

给定一个字符串s,找到s中最长的回文子串。你可以假设s 的最大长度为1000。

示例 1:

输入:          "babad"

输出:          "bab"

注意:          "aba"也是一个有效答案。

示例 2:

输入:           "cbbd"

输出:           "bb"

正确的程序(动态规划)


Part 1
Part 2

时间复杂度


时间复杂度
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容