2019-12-03 305 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，那么可以得到

res=max(res,(j-i)*min(height[i],height[j]));

1 2	res=max(res,(j-i)*min(height[i],height[j]));

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

height[i]&lt;height[j]?i++:j--;

1 2	height[i]<height[j]?i++:j--;

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

代码实现

int maxArea(vector&lt;int&gt;&amp; height) {
    int len = height.size();
    if (len == 0)
        return 0;
    else if (len == 1)
        return height[0];
    int left = 0, right = len - 1;
    int maxvalue = 0,tmp=0;
    while (left &lt;= right)
    {
        if (height[left] &lt;= height[right])
        {
            tmp = height[left] * (right - left);
            maxvalue = (maxvalue &lt; tmp ? tmp : maxvalue);
            ++left;
        }
        else if (height[left] &gt; height[right])
        {
            tmp = height[right] * (right - left);
            maxvalue = (maxvalue &lt; tmp ? tmp : maxvalue);
            --right;
        }
    }
    return maxvalue;
}

int maxArea(vector<int>& height) {

int len = height.size();

if (len == 0)

return 0;

else if (len == 1)

return height[0];

int left = 0, right = len - 1;

int maxvalue = 0,tmp=0;

while (left <= right)

{

if (height[left] <= height[right])

{

tmp = height[left] * (right - left);

maxvalue = (maxvalue < tmp ? tmp : maxvalue);

++left;

}

else if (height[left] > height[right])

{

tmp = height[right] * (right - left);

maxvalue = (maxvalue < tmp ? tmp : maxvalue);

--right;

}

return maxvalue;

}

复杂度

时间复杂度：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/

代码实现

vector&lt;vector&lt;int&gt;&gt; threeSum(vector&lt;int&gt;&amp; nums) {
    vector&lt;vector&lt;int&gt;&gt; res;
    int len = nums.size();
    if (len &lt; 3)
        return res;
    sort(nums.begin(), nums.end());
    for (int i = 0; i &lt; len; i++)
    {
        if (nums[i] &gt; 0)
            break;//如果当前数字大于0，则三数之和一定大于0，所以结束循环
        if (i &gt; 0 &amp;&amp; nums[i] == nums[i - 1])//去重
            continue;
        int left = i + 1;
        int right = len - 1;
        while (left &lt; right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0)
            {
                vector&lt;int&gt; tmp{ nums[i],nums[left],nums[right] };
                res.push_back(tmp);
                while (left &lt; right &amp;&amp; nums[left] == nums[left + 1])
                    left++;//去重
                while (left &lt; right &amp;&amp; nums[right] == nums[right - 1])
                    right--;//去重
                left++;
                right--;
            }
            else if (sum &lt; 0)
                left++;
            else if (sum &gt; 0)
                right--;
        }
    }
    return res;
}

vector<vector<int>> threeSum(vector<int>& nums) {

vector<vector<int>> res;

int len = nums.size();

if (len < 3)

return res;

sort(nums.begin(), nums.end());

for (int i = 0; i < len; i++)

{

if (nums[i] > 0)

break;//如果当前数字大于0，则三数之和一定大于0，所以结束循环

if (i > 0 && nums[i] == nums[i - 1])//去重

continue;

int left = i + 1;

int right = len - 1;

while (left < right) {

int sum = nums[i] + nums[left] + nums[right];

if (sum == 0)

{

vector<int> tmp{ nums[i],nums[left],nums[right] };

res.push_back(tmp);

while (left < right && nums[left] == nums[left + 1])

left++;//去重

while (left < right && nums[right] == nums[right - 1])

right--;//去重

left++;

right--;

}

else if (sum < 0)

left++;

else if (sum > 0)

right--;

}

return res;

}

复杂度

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

复杂度分析

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

题目描述

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

示例

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

解题思路

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

代码实现

class Solution
{
    vector&lt;string&gt; res;
    string digits;
    unordered_map&lt;char, string&gt; stored;
public:
    vector&lt;string&gt; letterCombinations(string digits) {
        if (digits.empty())
            return res;
        this-&gt;digits = digits;
        stored = { {'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"} };
        deepfs("", 0);
        return res;
    }
    void deepfs(string rstr, int ind)
    {
        int dsize = int(this-&gt;digits.size());
        if (dsize == ind)
        {
            res.push_back(rstr);
            return;
        }
        char targetChar = this-&gt;digits[ind];
        string targetStr = stored[targetChar];
        for (auto tmpChar : targetStr)
        {
            deepfs(rstr + tmpChar, ind + 1);
        }
        return;
    }
};

class Solution

{

vector<string> res;

string digits;

unordered_map<char, string> stored;

public:

vector<string> letterCombinations(string digits) {

if (digits.empty())

return res;

this->digits = digits;

stored = { {'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"} };

deepfs("", 0);

return res;

}

void deepfs(string rstr, int ind)

{

int dsize = int(this->digits.size());

if (dsize == ind)

{

res.push_back(rstr);

return;

}

char targetChar = this->digits[ind];

string targetStr = stored[targetChar];

for (auto tmpChar : targetStr)

{

deepfs(rstr + tmpChar, ind + 1);

}

return;

}

};

复杂度

时间复杂度：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]
]

解题思路

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

代码实现

void permuted(vector&lt;int&gt;&amp; nums, vector&lt;vector&lt;int&gt;&gt;&amp; result, int i)
{
    if (i == nums.size())
    {
        result.push_back(nums);
        return;
    }
    for (int j = i; j &lt; nums.size(); j++)
    {
        if (i != j)
            swap(nums[i], nums[j]);
        permuted(nums, result, i + 1);
        if (i != j)
            swap(nums[i], nums[j]);
    }
}
vector&lt;vector&lt;int&gt;&gt; permute(vector&lt;int&gt;&amp; nums) {
    vector&lt;vector&lt;int&gt;&gt; res;
    permuted(nums, res, 0);
    return res;
}

void permuted(vector<int>& nums, vector<vector<int>>& result, int i)

{

if (i == nums.size())

{

result.push_back(nums);

return;

}

for (int j = i; j < nums.size(); j++)

{

if (i != j)

swap(nums[i], nums[j]);

permuted(nums, result, i + 1);

if (i != j)

swap(nums[i], nums[j]);

}

vector<vector<int>> permute(vector<int>& nums) {

vector<vector<int>> res;

permuted(nums, res, 0);

return res;

}

复杂度

复杂度分析

Leetcode 49：字母异位词分组

题目描述

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

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

示例

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

解题思路

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

49题解

代码实现

vector&lt;vector&lt;string&gt;&gt; groupAnagrams(vector&lt;string&gt;&amp; strs) {
    vector&lt;vector&lt;string&gt;&gt; result;
    if (strs.empty())
        return result;
    map&lt;string, vector&lt;string&gt;&gt; mymap;
    for (auto str : strs)
    {
        string tmp = str;
        sort(tmp.begin(), tmp.end());//把所有的异序字母单词都排成按字母序排列
        //则有相同字母的排序完肯定是一样的，所以作为map的key
        mymap[tmp].push_back(str);
    }
    for (const auto&amp; mmap : mymap)
    {
        result.push_back(mmap.second);
    }
    return result;
}