小奥的学习笔记

  • 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题目解析(191128):2&3&72&75&76

2019年11月28日 978点热度 0人点赞 0条评论

Leetcode 2:两数相加

题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

代码实现

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        ListNode *tmp=new ListNode(-1);
        ListNode *res=tmp;
        ListNode *add1=l1;
        ListNode *add2=l2;
        int ge=0;
        int jin=0;
        while(add1!=NULL || add2!=NULL||jin)
        {
            ge=(add1?add1->val:0)+(add2?add2->val:0)+jin;
            jin=ge/10;
            ge=ge%10;
            ListNode *newnode = new ListNode(ge);
            tmp->next=newnode;
            tmp=tmp->next;
            if(add1)
                add1=add1->next;
            if(add2)
                add2=add2->next;
        }

        return res->next;
    }

执行用时&内存消耗

复杂度分析

Leetcode 3:无重复字符的最长子串

题目描述

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

代码实现

int lengthOfLongestSubstring(string s) {
        int len = s.size();
        vector<int> a(256,-1);
        int maxlen = 0;
        int l = -1;
        for(int i=0; i<len; i++){
            l = max(l,a[s[i]]);
            a[s[i]] = i;
            maxlen = max(maxlen,i-l);
        }
        
       return maxlen; 
    }

执行用时&占用空间

复杂度分析

Leetcode 72:编辑距离

题目描述

给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

示例

输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

解题思路

代码实现

int min3(int a, int b, int c)
{
    return (a < b) ? (a < c ? a : c) : (b < c ? b : c);
}
int minDistance(string word1, string word2) {
    int strlen1 = word1.size();
    int strlen2 = word2.size();
    vector<vector<int>>dp(strlen1 + 1, vector<int>(strlen2 + 1, 0));
    for (int i = 1; i <= strlen1; i++)
        dp[i][0] = i;
    for (int i = 1; i <= strlen2; i++)
        dp[0][i] = i;
    for (int i = 1; i <= strlen1; i++)
    {
        for (int j = 1; j <= strlen2; j++)
        {
            int diff;
            if (word1[i - 1] == word2[j - 1])
                diff = 0;
            else
                diff = 1;
            dp[i][j] = min3(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + diff);
        }
    }
    return dp[strlen1][strlen2];
}

复杂度

时间复杂度:算法有两个for循环,一个双重for循环。如果两个字符串分别是m和n,前两个for循环时间复杂度为O(n)和O(m)。双重for循环时间复杂度为O(n * m),所以总时间复杂度是O(n * m)。

空间复杂度:O(n * m)

复杂度分析

Leetcode 75:颜色分类

题目描述

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例

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

解题思路

此题是一个荷兰国旗问题,曾经在博客和公众号中都推送过这个问题的解决方案。所谓荷兰国旗问题,或者说黑猫白猫灰猫问题,其实都是一样的,就是说有三类数据乱序排列,然后要求用O(N)的时间复杂度,O(1)的空间复杂度使其有序。因其类似于荷兰国旗,所以被称为荷兰国旗问题(德国、法国在这里表示不服~)。

具体思路如下:

排序方法:设置start/end/current三个指针,分别指向开头、开头、结尾。在current<=end的背景下,然后开始判断current的值:

  1. 若current==0,因为0要排在前面,所以则将start指向的值和current的值交换,然后start++,current++;
  2. 若current==1,因为1是排在中间,所以current++,start不变;
  3. 若current==2,则将current和end的元素交换,将end--,但是current不变,如果current后移1位,那么current这一位就无法判断了。

代码实现

void sortColorsl(vector<int> &nums)
{
    int len = nums.size();
    int start = 0, current = 0, end = len - 1;
    //在current<=end的背景下,然后开始判断current的值
    while (current <= end)
    {
        //1.若current==0,则将start指向的值和current的值交换,然后start++,current++;
        if (nums[current] == 0)
        {
            swap(nums[current], nums[start]);
            ++current;
            ++start;
        }
        //3.若current==2,则将current和end的元素交换,将end--,但是current不变。
        else if (nums[current] == 2)
        {
            swap(nums[current], nums[end]);
            --end;
        }
        //2.若current==1,则current++,start不变;
        else if (nums[current] == 1)
        {
            ++current;
        }
    }
}

复杂度

时间复杂度:O(n)

复杂度分析

Leetcode 76:最小覆盖子串

题目描述

给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字母的最小子串。

如果 S 中不存这样的子串,则返回空字符串 ""。如果 S 中存在这样的子串,我们保证它是唯一的答案。

示例

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

解题思路

其实这个题的题目的英文Minimum winow substring给了我们一个答案,就是用窗来解决,但是中文名称却掩盖了这一点。

简单来说思路就是这样:设置一个左指针left,设置一个有指针right,然后不断移动右指针right,然后可以寻找到一个覆盖面最广的子串(最长覆盖子串),当然如果right移动到最后一个字母都没有找到覆盖子串的话,就是找不到了。完成这一步之后,开始移动left,这个时候寻找最小覆盖子串。

代码实现

string minWindow(string s, string t)
{
    int count[256] = { 0 };
    for (auto c : t)++count;//统计t中每个字符出现的次数
    int len = 0, minlen = s.size();//minlen最大为s的长度
    string res;
    for (int l = 0, r = 0; r < s.size(); ++r) {
        if (--count[s[r]] >= 0)++len;
        //上面这句话的意思是:不断移动窗口的right,同时若在s中发现t中有的字符,则len++
        //直到len加到和t相同,也就是在s中找到了一个字符串
        //下面就是找最优字符串了
        while (len == t.size()) {
            if (r - l + 1 <= minlen) {
                minlen = r - l + 1;
                res = s.substr(l, minlen);
            }
            if (++count[s[l++]] > 0)--len;
        }
            
    }
    return res;
}

复杂度

时间复杂度O(m* n),m和n分别为s和t的长度。

复杂度分析

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

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:一种基于深度滤波的全频带音频低复杂度语音增强框架
我对奥数班的怨念 《实时语音处理实践指南》第五章学习笔记 Leetcode题目解析(191105) Bye, Chen Yi middle School 《鸟哥的Linux私房菜》(基础篇)笔记整理(第8章) 班级记忆百宝箱第一版网站架设完毕
标签聚合
高中 Java linux 鸟哥的linux私房菜 python学习 生活 Python 算法 leetcode 学习
最近评论
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号