2019-12-07  183 views 评论

Leetcode题目解析(191207):10&21&23&31

 标签:

Leetcode 10:正则表达式匹配

题目描述

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '* ' 的正则表达式匹配。

题目解析

详见:https://leetcode-cn.com/problems/regular-expression-matching/solution/c-ji-yi-hua-shen-du-you-xian-sou-suo-by-da-li-wa-2/

代码实现

耗时&内存占用

复杂度分析

Leetcode 21:合并两个有序链表

题目描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

解题思路

不需要多说,直接看代码就看得懂,这是迭代法。递归法曾经在博客发过,具体可以在博客里面搜索一下。

代码实现

耗时和内存消耗

复杂度分析

Leetcode 23:合并K个排序链表

题目描述

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

示例

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

解题思路

其实解题思路有很多,例如链表全部push到一个vector后然后排序,最后再转换成一个list,这个复杂度是O(n^2),这是我想到的方法,但是这个方法太麻烦,复杂度太高。

另外一种思想就是合并数组中第k个链表到第1个链表,合并数组中第k-1个链表到第2个链表,依次这样操作;一轮合并之后,新链表分布在数组的 第1 到 第(k+1)/2个链表中,继续1这样的合并直到新链表只在数组第一个位置。这种方法是时间复杂度为O(N* log(k)),其中k为链表个数,N为链表平均长度。

还有一种思想是首先将vector转化为queue,然后在queue中每次取出前两个链表,按照之前简单的两个链表合并的方式进行合并,将合并完之后的链表push到queue的最后。依次这样进行,其实和上面的方法思路总体上是一样的,只不过用了一个queue来做中间变量。

下面是这种方法的实现。

代码实现

复杂度

复杂度分析

Leetcode 31:下一个排列

题目描述

实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。

必须原地修改,只允许使用额外常数空间。

解题思路

详见:
https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-by-leetcode/

代码实现

复杂度

时间复杂度:O(n)
空间复杂度:O(1)

复杂度分析

给我留言

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: