2019-12-07 341 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/

代码实现

class Solution {
public:
    vector&lt;vector&lt;int&gt;&gt; mem;
    int dfs(const string&amp; s, const string&amp; 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) &gt; 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) &gt; 0 || dfs(s, p, i + 1, j) &gt; 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&lt;vector&lt;int&gt; &gt;(s.size(), vector&lt;int&gt;(p.size(), 0));
        return dfs(s, p, 0, 0) &gt; 0;
    }
};

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

解题思路

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

代码实现

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
    ListNode* head = new ListNode(-1);
    ListNode* p = head;
    while (l1!=nullptr &amp;&amp; l2!=nullptr) {
        if (l1-&gt;val &lt;= l2-&gt;val)
        {
            head-&gt;next = l1;
            l1 = l1-&gt;next;
        }
        else {
            head-&gt;next = l2;
            l2 = l2-&gt;next;
        }
        head = head-&gt;next;
    }
    head-&gt;next = l1 ? l1 : l2;
    return p-&gt;next;
}

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来做中间变量。

下面是这种方法的实现。

代码实现

 ListNode* mergetwoLists(ListNode* l1, ListNode* l2)
{
    ListNode* head = new ListNode(-1);
    ListNode* p = head;
    while (l1 &amp;&amp; l2) {
        if (l1-&gt;val &lt; l2-&gt;val)
        {
            head-&gt;next = l1;
            l1 = l1-&gt;next;
        }
        else {
            head-&gt;next = l2;
            l2 = l2-&gt;next;
        }
        head = head-&gt;next;
    }
    head-&gt;next = l1 ? l1 : l2;
    return p-&gt;next;
}
ListNode* mergeKLists(vector&lt;ListNode*&gt;&amp; lists) {
    int numoflist = lists.size();
    if (numoflist == 0)
        return nullptr;
    if (numoflist == 1)
        return lists[0];
    queue&lt;ListNode*&gt; temp(deque&lt;ListNode*&gt;(lists.begin(), lists.end()));
    //将vector转化为队列
    //如果队列元素大于1，则拿两个合并，合并后的链表继续添加到链表尾部
    while (temp.size() &gt; 1)
    {
        ListNode* temp1 = temp.front();
        temp.pop();
        ListNode* temp2 = temp.front();
        temp.pop();
        temp.push(mergetwoLists(temp1, temp2));
    }
    return temp.front();
}

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/

代码实现

void reve(vector&lt;int&gt;&amp; nums, int start)
{
    int i = start, j = nums.size() - 1;
    while (i &lt; j)
    {
        swap(nums[i], nums[j]);
        i++;
        j--;
    }
}
void nextPermutation(vector&lt;int&gt;&amp; nums) {
    int i = nums.size() - 2;
    while (i &gt;= 0 &amp;&amp; nums[i + 1] &lt;= nums[i])
    {
        i--;
    }
    if (i &gt;= 0)
    {
        int j = nums.size() - 1;
        while (j &gt;= 0 &amp;&amp; nums[j] &lt;= nums[i])
        {
            j--;
        }
        swap(nums[i], nums[j]);
    }
    reve(nums,i+1);
}