2019-12-01 314 views 1

Leetcode题目解析（191201）：53&55&56

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

Leetcode 53：最大子序和

题目描述

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

解题思路

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

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

代码

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

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&lt;int&gt;&amp; nums) {
    int len = nums.size();
    if (len &lt; 1)
        return false;
    int lp = len - 1;
    for (int i = len - 1; i &gt;= 0; i--)
    {
        //倒着往回走
        if (nums[i] + i &gt;= lp) {
            lp = i;
        }
    }
    return lp == 0;
}

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&lt;vector&lt;int&gt;&gt; merge(vector&lt;vector&lt;int&gt;&gt;&amp; intervals) {
    vector&lt;vector&lt;int&gt;&gt; res;
    sort(intervals.begin(), intervals.end());
    int cur = 0;
    for (const auto&amp; in : intervals)
    {
        if (res.empty()) {
            res.push_back(in);
        }
        if (in[0] &lt;= res[cur][1]) {
            if (in[1] &gt; res[cur][1])
            {
                res[cur][1] = in[1];
            }
        }
        else {
            res.push_back(in);
            ++cur;
        }
    }
    return res;
}