hot100之数组
最大子数组和(053)先看代码
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int subSum = 0;
int res = nums;
for (int i = 0; i < n; i++){
subSum = Math.max(nums, subSum+nums);
res = Math.max(res, subSum);
}
return res;
}
}
[*]分析
贪心+动态规划
判断前子数组是否对 subSum 产生负影响, 产生影响则放弃前子数组, 重新开始新的子数组
动态规划体现在计算当前的子数组和时，需要考虑前面的子数组和是否对当前有贡献。贪心体现在如果前面的子数组和为负数，就直接舍弃重新开始计算。这道题的关键在于理解subSum代表以当前元素结尾的最大子数组和。
[*]感悟
因为前值会对后值产生影响 , 让人自然想到动态规划
由于后值只需要前一个状态的值 我们可以用 subSum作滚动计算,优化空间复杂度
合并区间(056)
先看代码
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (p, q)-> p - q);
List<int []> res = new ArrayList<>();
for(int[] p : intervals){
int m = res.size();
if (m > 0 && p <= res.get(m-1)){
res.get(m-1) = Math.max(res.get(m-1), p);
}else res.add(p);
}
return res.toArray(new int[]);
}
}
[*]分析
分别计算数组的前缀积与后缀积
用 i之前的前缀积 *i之和的后缀积
res = preSum * sufSum
preSum = 1 sufSum = 1
可知 preSum 为 num * …. * num
同理 sufSum 为 num * …. * num
可知preSum * sufSum 不包含 num
[*]感悟
分解数据的前后缀再求解
缺失的第一个正数(041)
先看代码
class Solution { public int firstMissingPositive(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++){ while(0 < nums && nums
页:
[1]