小奥的学习笔记

  • 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题目解析(191201):53&55&56

2019年12月1日 1026点热度 0人点赞 1条评论

今天终于了2019年的最后一个月了,要坚持在本周完成Leetcode的100道题第一遍,加油!

Leetcode 53:最大子序和

题目描述

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

解题思路

使用在线规划,复杂度为O(n)。在线规划的思想就是定义一个当前和(ThisSum)和一个最大和(MaxSum)。就是从第一个数开始加,赋值给ThisSum,然后如果ThisSum比MaxSum大的话,那就把ThisSum给MaxSum,否则的话不给。如果ThisSum加着加着都小于0了,那么这几个数字的和就没必要保留,直接舍弃就好了。由于题目说了长度至少是1,所以无需判断长度为0的情况,但是脑子里应该要想着这件事。

另外,有可能最大子序列和为单个元素的情况,所以在进行上述过程之前先寻找单个元素的最大值。

代码

int maxSubArray(vector<int>& nums) {
    int ThisSum = 0;
    int MaxSum = INT_MIN;
    int len = nums.size();
    for (int i = 0; i < len; i++)
    {
        if (nums[i] > MaxSum)
            MaxSum = nums[i];
    }
    for (int i = 0; i < len; i++)
    {
        ThisSum += nums[i];
        if (ThisSum > MaxSum)
            MaxSum = ThisSum;
        else if (ThisSum < 0)
            ThisSum = 0;
    }
    return MaxSum;
}

复杂度

时间复杂度:O(n)
空间复杂度:O(1),两个变量ThisSum和MaxSum。

复杂度分析

Leetcode 55:跳跃游戏

题目描述

给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

代码实现

bool canJump(vector<int>& nums) {
    int len = nums.size();
    if (len < 1)
        return false;
    int lp = len - 1;
    for (int i = len - 1; i >= 0; i--)
    {
        //倒着往回走
        if (nums[i] + i >= lp) {
            lp = i;
        }
    }
    return lp == 0;
}

复杂度

时间复杂度:O(n)

复杂度分析

Leetcode 56:合并区间

题目描述

给出一个区间的集合,请合并所有重叠的区间。

示例

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

解题思路

首先进行排序,然后把第一个区间插入到merged数组中,然后按照顺序开始考虑这之后的每一个区间。如果我们当前的区间的左端点在前一个区间的右端点之后,那么它们铁定不会重合,我们可以直接将这个区间插入到merged里面;否则,如果当前区间的右端点比前一个区间的右端点大的话,那么就更新前一区间的右端点为当前区间的右端点,这样就可以了。

代码实现

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> res;
    sort(intervals.begin(), intervals.end());
    int cur = 0;
    for (const auto& in : intervals)
    {
        if (res.empty()) {
            res.push_back(in);
        }
        if (in[0] <= res[cur][1]) {
            if (in[1] > res[cur][1])
            {
                res[cur][1] = in[1];
            }
        }
        else {
            res.push_back(in);
            ++cur;
        }
    }
    return res;
}

复杂度

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

复杂度分析

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

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:一种基于深度滤波的全频带音频低复杂度语音增强框架
Java语言程序设计【学堂在线】(第三章)整理 航空节专题地址修改 每日一感0816:Happy Birthday to My Grandmother! 生活点滴:昨晚上的杯具性事件 我在为V4版作准备 期末考试终于结束了...
标签聚合
Java 鸟哥的linux私房菜 生活 学习 leetcode 高中 linux Python 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 发布于 8 个月前(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号