2019-12-03  92 views 评论

Leetcode题目解析(191203):11&15&17&46&49

 标签:

Leetcode 11:盛最多水的容器

题目描述

给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

question_11.jpg

示例

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

如上图所示,图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

解题思路

其实这个题的意思就是假设我有两个点(i,ai)和(j,aj),然后这两个点向下做垂线交x轴于(i,0)和(j,0)点,然后储水量其实就是(i,0)(j,0),(j,aj),(i,ai)四个点围起来的区域的面积。那么我们假设这个面积为res,那么可以得到

然后这其实就是这个题的核心,剩下就是如何求解最大呢?可以用贪婪算法。我们可以令i=0,j=height.size()-1,这样一步一步往中间收缩。收缩方式为

可能会想我们是否会错过最大值呢?其实感性想一想,面积最大也就是i-j和坐标值中的最小值有关系,当然我们希望i-j越大越好,最小值越大越好,所以我们要一边增大最小值,一边收缩,然后不断记录当前的最大值就可以了。

代码实现

复杂度

时间复杂度:O(n)
空间复杂度:O(1)

复杂度分析

Leetcode 15:三数之和

题目描述

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

示例

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

解题思路

首先对数组进行排序,排序后固定一个数nums[i],再使用左右指针指向nums[i]后面的两端,数字分别为nums[L]和nums[R],计算三个数的和sum判断是否满足为0,满足则添加进结果如果nums[i]大于0,则三数之和必然无法等于0,结束循环;如果nums[i]==nums[i-1],则说明该数字重复,会导致结果重复,所以应该跳过;当sum==0时,nums[L]==nums[L+1]则会导致结果重复,应该跳过,L++;当sum==0时,nums[R]==nums[R−1]则会导致结果重复,应该跳过,R−−。

改编自:https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/

代码实现

复杂度

时间复杂度:O(n^2),n为数组长度。

复杂度分析

Leetcode 17:电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例

输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

解题思路

这个题可以使用深度优先遍历,也可以使用广度优先遍历。这里讲一下深度优先遍历。其过程可以用下图来表示,我们以“23”为例来进行讲解,递归调用deepfs函数,每次找到stored中存储的字符,调用下一层deepfs函数。

题解

代码实现

复杂度

时间复杂度:O(3^n+4^m)
空间复杂度:O(3^n+4^m)

n表示三个字母的数字的个数,m表示4个字母的数字的个数。

复杂度分析

Leetcode 46:全排列

题目描述

给定一个没有重复数字的序列,返回其所有可能的全排列。

示例

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

解题思路

这个题其实就是使用回溯法的思路即可解决。回溯法思路在此不再重述。

代码实现

复杂度

复杂度分析

Leetcode 49:字母异位词分组

题目描述

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

所有输入均为小写字母。不考虑答案输出的顺序。

示例

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

解题思路

如图所示,就是利用了异位词是由相同的字母组成这一特点,设置了map的key,然后将单词作为value来储存得到。

49题解

代码实现

复杂度

时间复杂度:O(n)。
空间复杂度:额外使用了一个map。

复杂度分析

给我留言

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