网站的关键词在哪里设置,制作二维码的软件,在线制作印章生成免费,自己动手做网站教程本篇博客讲解LeetCode热题100道普通数组篇中的五道题 第一道#xff1a;最大子数组和#xff08;中等#xff09; 第二道#xff1a;合并区间#xff08;中等#xff09; 第一道#xff1a;最大子数组和#xff08;中等#xff09; 法一#xff1a;贪心算法 class So… 本篇博客讲解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_sumnums[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 Comparatorint[]() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});Listint[] merged new ArrayListint[]();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 列表转换为二维数组并返回。 通过先对区间进行排序然后逐一合并重叠区间最终返回合并后的区间数组。
