中国建设银行北京分行网站,甘肃省建设部网站首页,wordpress怎么访问数据库,建设厅的工程造价网站文章目录 题目#xff1a;最大子数组和方法1 动态规划方法2 题目#xff1a;合并区间题解 题目#xff1a;轮转数组方法1-使用额外的数组方法2-三次反转数组 题目#xff1a;除自身以外数组的乘积方法1-用到了除法方法2-前后缀乘积法 题目#xff1a;最大子数组和
原题链… 文章目录 题目最大子数组和方法1 动态规划方法2 题目合并区间题解 题目轮转数组方法1-使用额外的数组方法2-三次反转数组 题目除自身以外数组的乘积方法1-用到了除法方法2-前后缀乘积法 题目最大子数组和
原题链接最大子数组和
方法1 动态规划
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}
}
方法2
方法二可能不容易想到
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 Comparatorint[]() {Overridepublic int compare(int[] interval1, int[] interval2) {return interval1[0]-interval2[0];}});Listint[] 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 列表中最后一个区间的结束值。
排序区间: 确保区间按照起始值从小到大排列方便后续合并操作。遍历和合并: 遍历排序后的区间数组使用一个 merged 列表来存储合并后的区间。如果当前区间与前一个区间不重叠直接添加到 merged 列表如果重叠更新 merged 列表中最后一个区间的结束值。 题目轮转数组
原题链接轮转数组
方法1-使用额外的数组
方法1是自己写出来的。方法2参考的别人的方法2太了不易发现这个规律 public static void rotate(int[] nums, int k) {int[] temp new int[nums.length];int j 0;k k % nums.length; // 数组长度大于k时旋转次数取余---关键for (int i nums.length - k; i nums.length; i) {temp[j] nums[i];}for (int i 0; i nums.length - k; i) {temp[j] nums[i];}System.arraycopy(temp, 0, nums, 0, nums.length);}方法2-三次反转数组 private static void reverse(int[] nums, int start, int end) {while (start end) {int temp nums[start];nums[start] nums[end];nums[end] temp;start;end--;}}public static void rotate1(int[] nums, int k) {k k % nums.length; reverse(nums, 0, nums.length - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.length - 1);}题目除自身以外数组的乘积
原题链接除自身以外数组的乘积
方法1-用到了除法
当时没看题目中不让用除法当时一下就想到这个思路了哈哈哈 public static int[] productExceptSelf(int[] nums) {int temp 1;int zero 0;// 先看数组中0的个数 大于1则结果数组全为0 等于1则结果数组中0的位置为其他元素乘积for (int num : nums) {if (num ! 0) {temp * num;} else {zero;if (zero 1) return new int[nums.length];}}ListInteger res new ArrayList();for (int num : nums) {if (zero 1) {//num0 则当前结果数组该位置的结果为其他元素乘积res.add(num 0 ? temp : 0);} else {res.add(temp / num);}}return res.stream().mapToInt(Integer::intValue).toArray();}方法2-前后缀乘积法
方法2使用两次遍历分别计算数组元素左边和右边的乘积从而构建出结果数组 public static int[] productExceptSelf1(int[] nums) {int n nums.length;int[] res new int[n];// 第一次遍历计算左边所有元素的乘积res[0] 1;for (int i 1; i n; i) {res[i] res[i - 1] * nums[i - 1];}// 第二次遍历计算右边所有元素的乘积并更新结果数组int right 1;for (int i n - 1; i 0; i--) {res[i] * right; //res[i]是当前i左边元素全部乘积right * nums[i]; //用一个变量记录当前元素右边的所有元素乘积}return res;}❤觉得有用的可以留个关注~~❤
