2019-11-28  90 views 评论

Leetcode题目解析(191128):2&3&72&75&76

 标签:

Leetcode 2:两数相加

题目描述

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

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

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

示例

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

代码实现

执行用时&内存消耗

复杂度分析

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

题目描述

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

示例

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

代码实现

执行用时&占用空间

复杂度分析

Leetcode 72:编辑距离

题目描述

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

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

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

示例

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

解题思路

代码实现

复杂度

时间复杂度:算法有两个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这一位就无法判断了。

代码实现

复杂度

时间复杂度:O(n)

复杂度分析

Leetcode 76:最小覆盖子串

题目描述

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

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

示例

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

解题思路

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

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

代码实现

复杂度

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

复杂度分析

给我留言

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