建设企业网站公,免费ftp网站,台州网站开发,wix做网站步骤LeetCode 热题 100 文章目录 LeetCode 热题 100普通数组13. 中等-最大子数组和14. 中等-合并区间15. 中等-轮转数组16. 中等-除自身以外数组的乘积17. 困难-缺失的第一个正数 矩阵18. 中等-矩阵置零19. 中等-螺旋矩阵20. 中等-旋转图像21. 中等-搜索二维矩阵II 本文存储我刷题的…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 ] [m1,r] [m1,r] m ⌊ l r 2 ⌋ m \lfloor \frac{l r}{2} \rfloor m⌊2lr⌋直到子区间长度为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 加上「左子区间」的 rSum \textit{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(??%)。
