小奥的学习笔记

  • 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题目解析(191203):11&15&17&46&49

2019年12月3日 1265点热度 0人点赞 0条评论

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]));

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

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

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

代码实现

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

复杂度

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

复杂度分析

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

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:一种基于深度滤波的全频带音频低复杂度语音增强框架
我在为V4版作准备 班级记忆百宝箱第一版网站架设完毕 备战CET-SET&CET-6 复习方案 美军进攻莱芜,大败而归 吴恩达深度学习课程 DeepLearning.ai 编程作业(2-1)Part.2 莱芜一中高三(51级)毕业生学习成果汇报
标签聚合
linux 高中 算法 Java leetcode Python 生活 鸟哥的linux私房菜 python学习 学习
最近评论
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号