《LeetCode热题100》---＜5.普通数组篇六道＞

本篇博客讲解LeetCode热题100道普通数组篇中的六道题

第一道：最大子数组和（中等）

第二道：合并区间（中等）

第一道：最大子数组和（中等）

法一：贪心算法

class Solution {public int maxSubArray(int[] nums) {int len = nums.length;int cur_sum  = nums[0];int max_sum = cur_sum;for(int i = 1; i <len; i++){cur_sum = Math.max(nums[i],cur_sum+nums[i]);max_sum = Math.max(cur_sum,max_sum);}return max_sum;}
}

1.将当前和与最大和设置为数组第一个元素 

2.从第二个元素开始遍历数组元素。

• 令当前和等于 当前元素 和 当前和+当前元素 的最大值
• 令最大和等于 当前和 与 最大和 的最大值

3.返回最大和，即为答案。

法二：动态规划

class Solution {public int maxSubArray(int[] nums) {int pre = 0, maxAns = nums[0];for (int x : nums) {pre = Math.max(pre + x, x);maxAns = Math.max(maxAns, pre);}return maxAns;}
}

 这个动态规划的答案实际上和上面讲的贪心算法的答案是一样的。

第二道：合并区间（中等）

方法一：排序 

class Solution {public int[][] merge(int[][] intervals) {if (intervals.length == 0) {return new int[0][2];}Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});List<int[]> merged = new ArrayList<int[]>();for (int i = 0; i < intervals.length; ++i) {int L = intervals[i][0], R = intervals[i][1];if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {merged.add(new int[]{L, R});} else {merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);}}return merged.toArray(new int[merged.size()][]);}
}

• 检查空数组：如果输入的区间数组 intervals 为空，则返回一个空的二维数组。
• 排序区间：将所有区间按起始位置进行排序，确保按从左到右的顺序处理区间。
• 合并区间：
  • 初始化一个列表 merged，用于存储合并后的区间。
  • 遍历每个区间，获取当前区间的起始位置 L 和结束位置 R。
  • 如果 merged 为空，或者当前区间的起始位置 L 大于 merged 中最后一个区间的结束位置，则直接将当前区间加入 merged。
  • 否则，将当前区间与 merged 中最后一个区间合并，更新最后一个区间的结束位置为二者的最大值。
• 返回结果：将 merged 列表转换为二维数组并返回。

 通过先对区间进行排序，然后逐一合并重叠区间，最终返回合并后的区间数组。