今天终于了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)
文章评论