力扣hot100-普通数组

题目：最大子数组和

原题链接：最大子数组和

方法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 Comparator<int[]>() {@Overridepublic 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 列表中最后一个区间的结束值。

• 排序区间: 确保区间按照起始值从小到大排列，方便后续合并操作。
• 遍历和合并: 遍历排序后的区间数组，使用一个 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];}}List<Integer> res = new ArrayList<>();for (int num : nums) {if (zero == 1) {//num==0 则当前结果数组该位置的结果为其他元素乘积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;}

---

❤觉得有用的可以留个关注~~❤