赞
踩
原题链接:最大子数组和
public class T53 { //动态规划 public static int maxSubArray(int[] nums) { if (nums.length == 0) return 0; int[] dp = new int[nums.length]; // dp[i] 表示以 nums[i] 结尾的最大子数组和 dp[0] = nums[0]; // 初始化状态 int res = dp[0]; // 初始化最大子数组和 // 动态规划状态转移 for (int i = 1; i < nums.length; i++) { dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]); //状态转移方程 res = Math.max(res, dp[i]); } return res; } public static void main(String[] args) { int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; System.out.println(maxSubArray(nums)); // 输出: 6 } }
方法二可能不容易想到
public class T53 { public int maxSubArray(int[] nums) { // 初始化为int类型最小值 int res = nums[0]; int tempTotal = 0; for (int i = 0; i < nums.length; i++) { tempTotal += nums[i]; // 记录最大数值 res = Math.max(tempTotal, res); if (tempTotal < 0) { // 如果和小于0,就重置为0,因为任何数加上一个负数一定小于当前数值 tempTotal = 0; //0加任何数都等于任何数 } } return res; } public static void main(String[] args) { int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; System.out.println(maxSubArray(nums)); // 输出: 6 } }
原题链接:合并区间
public static int[][] merge(int[][] intervals) { if (intervals.length == 0) { return new int[0][2]; } // 可使用Lambda表达式 Arrays.sort(intervals, new Comparator<int[]>() { @Override public int compare(int[] interval1, int[] interval2) { return interval1[0]-interval2[0]; } }); List<int[]> merged = new ArrayList<>(); for (int[] interval : intervals) { int L = interval[0], R = interval[1]; // 如果merged列表为空,或者当前区间与上一个区间不重叠,直接添加当前区间 if (merged.isEmpty() || 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); } } //List.toArray(T[] a) 方法将列表中的所有元素存储到指定类型的数组中 return merged.toArray(new int[merged.size()][]); }
核心:
如果新区间
的起始值大于 merged 列表中最后一个区间的结束值,则直接将新的区间添加到 merged 列表中;否则,更新 merged 列表中最后一个区间的结束值。
原题链接:轮转数组
方法1是自己写出来的。方法2参考的别人的,方法2太声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。