最大子数组和

动态规划

public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int[] dp = new int[nums.length]; 
    dp[0] = nums[0];
    int maxSum = dp[0];
    for (int i = 1; i < nums.length; i++) {
        // 要么从头开始 要么叠加上当前的
        dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);
        maxSum = Math.max(maxSum, dp[i]);
    }
    
    return maxSum;
}

合并区间

注意排序写法

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][];
        }
        // 排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        List<int[]> result = new ArrayList<>();
        result.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] last = result.get(result.size() - 1);  // 结果列表中的最后一个区间
            int[] curr = intervals[i];                   // 当前区间
            
            // 如果当前区间与最后一个区间有重叠
            if (curr[0] <= last[1]) {
                // 合并：取两者区间的最大值
                last[1] = Math.max(last[1], curr[1]);
            } else {
                // 没有重叠，直接加入
                result.add(curr);
            }
        }
        return result.toArray(new int[result.size()][]);
    }

轮转数组

思路题，三次反转，先整体反转，再反转前k个，再反转后n-k个。

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
    
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

除了自身以外数组的乘积

计算左侧的乘积和右侧的乘积。res[i] = res[i-1] * nums[i-1];

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    
    // 计算左侧乘积
    result[0] = 1;
    for (int i = 1; i < n; i++) {
        result[i] = result[i - 1] * nums[i - 1];
    }
    
    // 计算右侧乘积并同时更新最终结果
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] = result[i] * right;
        right *= nums[i];
    }
    
    return result;
}

缺失的第一个正数

先贴个题解，有空再来琢磨。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}