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/
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Solution { public: vector<vector<int>> mem; int dfs(const string& s, const string& p, int i, int j) { if (i == s.size()) return j == p.size() ? 1 : -1; if (j == p.size()) return i == s.size() ? 1 : -1; if (mem[i][j] != 0) return mem[i][j]; if (j == p.size() - 1 || p[j + 1] != '*') { if (p[j] == '.' || p[j] == s[i]) { mem[i][j] = dfs(s, p, i + 1, j + 1); return mem[i][j]; } } else { if (dfs(s, p, i, j + 2) > 0) { mem[i][j] = 1; return mem[i][j]; } if (p[j] == '.' || p[j] == s[i]) { bool t = dfs(s, p, i + 1, j + 2) > 0 || dfs(s, p, i + 1, j) > 0; mem[i][j] = t ? 1 : -1; return mem[i][j]; } } mem[i][j] = -1; return mem[i][j]; } bool isMatch(string s, string p) { s += '#'; p += '#'; mem = vector<vector<int> >(s.size(), vector<int>(p.size(), 0)); return dfs(s, p, 0, 0) > 0; } }; |
耗时&内存占用
Leetcode 21：合并两个有序链表
题目描述
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
解题思路
不需要多说，直接看代码就看得懂，这是迭代法。递归法曾经在博客发过，具体可以在博客里面搜索一下。
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* head = new ListNode(-1); ListNode* p = head; while (l1!=nullptr && l2!=nullptr) { if (l1->val <= l2->val) { head->next = l1; l1 = l1->next; } else { head->next = l2; l2 = l2->next; } head = head->next; } head->next = l1 ? l1 : l2; return p->next; } |
耗时和内存消耗
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来做中间变量。
下面是这种方法的实现。
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
ListNode* mergetwoLists(ListNode* l1, ListNode* l2) { ListNode* head = new ListNode(-1); ListNode* p = head; while (l1 && l2) { if (l1->val < l2->val) { head->next = l1; l1 = l1->next; } else { head->next = l2; l2 = l2->next; } head = head->next; } head->next = l1 ? l1 : l2; return p->next; } ListNode* mergeKLists(vector<ListNode*>& lists) { int numoflist = lists.size(); if (numoflist == 0) return nullptr; if (numoflist == 1) return lists[0]; queue<ListNode*> temp(deque<ListNode*>(lists.begin(), lists.end())); //将vector转化为队列 //如果队列元素大于1，则拿两个合并，合并后的链表继续添加到链表尾部 while (temp.size() > 1) { ListNode* temp1 = temp.front(); temp.pop(); ListNode* temp2 = temp.front(); temp.pop(); temp.push(mergetwoLists(temp1, temp2)); } return temp.front(); } |
复杂度
Leetcode 31：下一个排列
题目描述
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
解题思路
详见：
https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-by-leetcode/
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
void reve(vector<int>& nums, int start) { int i = start, j = nums.size() - 1; while (i < j) { swap(nums[i], nums[j]); i++; j--; } } void nextPermutation(vector<int>& nums) { int i = nums.size() - 2; while (i >= 0 && nums[i + 1] <= nums[i]) { i--; } if (i >= 0) { int j = nums.size() - 1; while (j >= 0 && nums[j] <= nums[i]) { j--; } swap(nums[i], nums[j]); } reve(nums,i+1); } |
复杂度
时间复杂度：O(n)
空间复杂度：O(1)
![[Leetcode]copy list with random pointer](http://www.yushuai.xyz/wp-content/themes/MyDream/timthumb.php?src=https://dqhplhzz2008-1251830035.cos.ap-guangzhou.myqcloud.com/wp-content/uploads/2019/04/1.png&h=180&w=300&zc=1)
