小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

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

2019年12月7日 1293点热度 0人点赞 0条评论

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<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 && 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 && 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<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)

复杂度分析

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode
最后更新:2019年12月7日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
2009 S.V Beijing Travel Finally:Bye-bye,Beijing! 吴恩达深度学习课程 DeepLearning.ai 编程作业(1-2)Part.2 小花豆生活第1天:4号口安保初体验 新建济南至莱芜高速铁路工程(不含先期开工段)站前工程施工招标中标候选人公示 C++ Primer Plus(第五版)第11章编程题答案 2022年的第一篇碎碎念
标签聚合
leetcode 生活 学习 Python 鸟哥的linux私房菜 算法 linux 高中 python学习 Java
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号