LeetCode 热题 100
文章目录
- LeetCode 热题 100
- 普通数组
-
- 13. 中等-最大子数组和
- 14. 中等-合并区间
- 15. 中等-轮转数组
- 16. 中等-除自身以外数组的乘积
- 17. 困难-缺失的第一个正数
- 矩阵
-
- 18. 中等-矩阵置零
- 19. 中等-螺旋矩阵
- 20. 中等-旋转图像
- 21. 中等-搜索二维矩阵II
本文存储我刷题的笔记。
普通数组
13. 中等-最大子数组和
我的思路
思路:从第一个非负数开始,不断向右扩大窗口更新最大值;若当前窗口为负,则继续从下一个正数开始滑动窗口。
时间96ms(50.51%),内存64.89MB(56.76%)。
class Solution {
public:
int maxSubArray(std::vectorint>& nums) {
int len = nums.size();
// 寻找到第一个非负数
int left{ -1 };
int max_tmp{ nums[0] };
while (left len - 1 && nums[++left] 0) {
max_tmp = std::max(max_tmp, nums[left]);
}
// 向右扩大窗口,不断记录最大值,直到和为负或遍历完成
int sum{ 0 };
for (int i = left; i len; i++) {
sum += nums[i];
max_tmp = std::max(max_tmp, sum);
// 若当前和为负则重新找下一个正数
if (sum 0) {
while (i len - 1 && nums[++i] 0) {}
if (i == len - 1) {
return std::max(max_tmp, nums[i]);
}
--i;
sum = 0;
}
}
return max_tmp;
}
};
官方思路一:动态规划
- 思路:类似于滚动数组的思想。若使用
p
r
e
(
i
)
pre(i)
pre(i) 表示以下标
i
i
i 为结尾的“连续子数组最大和”,显然我们只需要滚动遍历寻找
max
0
≤
i
≤
n
−
1
{
p
r
e
(
i
)
}
max_{0 le i le n-1}{ pre(i)}
max0≤i≤n−1{pre(i)} 即可。那每一步如何计算
p
r
e
(
i
)
pre(i)
pre(i) 呢?可以使用递推的思想,也就是:
p
r
e
(
i
)
=
max
{
p
r
e
(
i
−
1
)
+
nums
[
i
]
,
nums
[
i
]
}
且
p
r
e
(
0
)
=
nums
[
0
]
pre(i) = max { pre(i-1) + textit{nums}[i], textit{nums}[i] } ; 且 ; pre(0) = textit{nums}[0]
pre(i)=max{pre(i−1)+nums[i],nums[i]}且pre(0)=nums[0]。
- 时间复杂度:
O
(
n
)
O(n)
O(n),其中
n
n
n 为
nums
textit{nums}
nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
- 空间复杂度:
O
(
1
)
O(1)
O(1)。我们只需要常数空间存放若干变量。
- 时间80ms(92.74%),内存64.91MB(55.59%)。
class Solution {
public:
int maxSubArray(vectorint>& nums) {
int pre = 0, maxAns = nums[0];
for (const auto &x: nums) {
pre = max(pre + x, x); // 求解本步骤的pre(i)
maxAns = max(maxAns, pre); // 求解最大值
}
return maxAns;
}
};
官方思路二:分治
- 思路:我们想通过定义一个递归函数
get(nums,l,r)
表示查询nums
序列[l,r]
区间 的最大子段和,于是get(nums,0,nums.size()-1)
就可以直接完成题目。每次查询时,都将区间拆成左右两个子区间[
l
,
m
]
[l,m]
[l,m]、
[
m
+
1
,
r
]
[m+1,r]
[m+1,r](
m
=
⌊
l
+
r
2
⌋
m = lfloor frac{l + r}{2} rfloor
m=⌊2l+r⌋),直到子区间长度为1,然后再逐级根据两个子区间的信息返回当前子区间的信息。每个区间的“信息”包括四个:
lSum
textit{lSum}
lSum 表示
[
l
,
r
]
[l,r]
[l,r] 内以
l
l
l 为左端点的最大子段和
rSum
textit{rSum}
rSum 表示
[
l
,
r
]
[l,r]
[l,r] 内以
r
r
r 为右端点的最大子段和
mSum
textit{mSum}
mSum 表示
[
l
,
r
]
[l,r]
[l,r] 内的最大子段和
iSum
textit{iSum}
iSum 表示
[
l
,
r
]
[l,r]
[l,r] 的区间和
显然区间长度为1时,四个量都等于序列值。区间长度大于1时:
- 首先最好维护的是
iSum
textit{iSum}
iSum,区间
[
l
,
r
]
[l,r]
[l,r] 的
iSum
textit{iSum}
iSum 就等于「左子区间」的
iSum
textit{iSum}
iSum 加上「右子区间」的
iSum
textit{iSum}
iSum。
- 对于
[
l
,
r
]
[l,r]
[l,r] 的
lSum
textit{lSum}
lSum,存在两种可能,它要么等于「左子区间」的
lSum
textit{lSum}
lSum,要么等于「左子区间」的
iSum
textit{iSum}
iSum 加上「右子区间」的
lSum
textit{lSum}
lSum,二者取大。
- 对于
[
l
,
r
]
[l,r]
[l,r] 的
rSum
textit{rSum}
rSum,同理,它要么等于「右子区间」的
rSum
textit{rSum}
rSum,要么等于「右子区间」的
iSum
textit{iSum}
iSum 加上「左子区间」的
服务器托管网
rSumtextit{rSum}
rSum,二者取大。
- 当计算好上面的三个量之后,就很好计算
[
l
,
r
]
[l,r]
[l,r] 的
mSum
textit{mSum}
mSum 了。我们可以考虑
[
l
,
r
]
[l,r]
[l,r] 的
mSum
textit{mSum}
mSum 对应的区间是否跨越
m
m
m——它可能不跨越
m
m
m,也就是说
[
l
,
r
]
[l,r]
[l,r] 的
mSum
textit{mSum}
mSum 可能是「左子区间」的
mSum
textit{mSum}
mSum 和 「右子区间」的
mSum
textit{mSum}
mSum 中的一个;它也可能跨越
m
m
m,可能是「左子区间」的
rSum
textit{rSum}
rSum 和 「右子区间」的
lSum
textit{lSum}
lSum 求和。三者取大。
- 时间92ms(63.50%),内存64.87MB(59.37%)。
力扣官方 注:这个分治方法类似于「线段树求解最长公共上升子序列问题」的
pushUp
操作。 也许读者还没有接触过线段树,没有关系,方法二的内容假设你没有任何线段树的基础。当然,如果读者有兴趣的话,推荐阅读线段树区间合并法解决多次询问的「区间最长连续上升序列问题」和「区间最大子段和问题」,还是非常有趣的。
class Solution {
public:
// 每个区间[l,r]都定义了四种量
struct Status {
int lSum, // 区间[l,r]内,以 l 为左端点的最大子段和
rSum, // 区间[l,r]内,以 r 为右端点的最大子段和
mSum, // 区间[l,r]内的最大子段和
iSum; // 区间[l,r]的区间和
};
// 根据左右子区间的信息,计算当前区间的信息
Status pushUp(Status l, Status r) {
int iSum = l.iSum + r.iSum;
int lSum = std::max(l.lSum, l.iSum + r.lSum);
int rSum = std::max(r.rSum, r.iSum + l.rSum);
int mSum = std::max(std::max(l.mSum, r.mSum), l.rSum + r.lSum);
return Status { lSum, rSum, mSum, iSum };
};
// 分治法:采用递归思想
Status get(std::vectorint>& a, int l, int r) {
// 长度为1,直接返回
if (l == r) {
return Status { a[l], a[l], a[l], a[l] };
}
// 将区间对半分,递归寻找每个子区间的信息
int m = (l + r) >> 1; // 区间的中点
Status lSub = get(a, l, m); // 左子区间
Status rSub = get(a, m + 1, r); // 右子区间
return pushUp(lSub, rSub); // 根据左右子区间信息,计算当前区间最大字段和
}
// 主函数
int maxSubArray(std::vectorint>& nums) {
return get(nums, 0, nums.size() - 1).mSum;
}
};
14. 中等-合并区间
15. 中等-轮转数组
16. 中等-除自身以外数组的乘积
17. 困难-缺失的第一个正数
矩阵
18. 中等-矩阵置零
19. 中等-螺旋矩阵
20. 中等-旋转图像
21. 中等-搜索二维矩阵II
我的思路
思路:
时间??ms(??%),内存??MB(??%)。
官方思路:
思路:
时间??ms(??%),内存??MB(??%)。
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net