LeetCode-Hot100-普通数组

class Solution {
    public int maxSubArray(int[] nums) {
        int max_ending_here = nums[0];
        int max_so_far = nums[0];

        for(int i = 1; i < nums.length; i++){
            max_ending_here = Math.max(nums[i], max_ending_here + nums[i]);
            max_so_far = Math.max(max_ending_here, max_so_far);
        }

        return max_so_far;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        return maxSubArrayDivideAndConquer(nums, 0, nums.length - 1);
    }

    private int maxCrossingSum(int[] nums, int left, int mid, int right) {
        // 包含中间的左半部分最大和
        int leftSum = Integer.MIN_VALUE;
        int currentSum = 0;
        for (int i = mid; i >= left; i--) {
            currentSum += nums[i];
            if (currentSum > leftSum) {
                leftSum = currentSum;
            }
        }

        // 包含中间的右半部分最大和
        int rightSum = Integer.MIN_VALUE;
        currentSum = 0;
        for (int i = mid + 1; i <= right; i++) {
            currentSum += nums[i];
            if (currentSum > rightSum) {
                rightSum = currentSum;
            }
        }

        // 返回跨越中间的最大和
        return leftSum + rightSum;
    }

    private int maxSubArrayDivideAndConquer(int[] nums, int left, int right) {
        // 基本情况：当只有一个元素时
        if (left == right) {
            return nums[left];
        }

        int mid = (left + right) / 2;

        // 分别递归求解左半部分、右半部分和跨越中间的子数组最大值
        int leftMax = maxSubArrayDivideAndConquer(nums, left, mid);
        int rightMax = maxSubArrayDivideAndConquer(nums, mid + 1, right);
        int crossMax = maxCrossingSum(nums, left, mid, right);

        // 返回三个部分的最大值
        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        // 如果输入为空，直接返回空数组
        if (intervals.length == 0) {
            return new int[0][0];
        }

        // 按照区间的起始位置进行排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> merged = new LinkedList<>();

        for (int[] interval : intervals) {
            // 如果结果列表为空，或者当前区间的起始位置大于结果列表最后一个区间的结束位置
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                // 否则，合并当前区间到结果列表的最后一个区间
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }

        return merged.toArray(new int[merged.size()][]);
    }
}

public class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n; // 处理 k 大于 n 的情况
        int[] temp = new int[n];

        for (int i = 0; i < n; i++) {
            temp[(i + k) % n] = nums[i];
        }
        
        System.arraycopy(temp, 0, nums, 0, n);
    }
}

public class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n; // 处理 k 大于 n 的情况

        reverse(nums, 0, n - 1); // 反转整个数组
        reverse(nums, 0, k - 1); // 反转前 k 个元素
        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--;
        }
    }
}

public class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n; // 处理 k 大于 n 的情况
        
        int count = 0; // 记录替换次数
        for (int start = 0; count < n; start++) {
            int current = start;
            int prevValue = nums[start];
            do {
                int nextIndex = (current + k) % n;
                int temp = nums[nextIndex];
                nums[nextIndex] = prevValue;
                prevValue = temp;
                current = nextIndex;
                count++;
            } while (start != current);
        }
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;

        // 返回数组、前缀积、后缀积初始化
        int[] ans = new int[n];
        int[] pre = new int[n];
        int[] suf = new int[n];

        Arrays.fill(pre, 1); // 填充数组初值为 1
        Arrays.fill(suf, 1);
        Arrays.fill(ans, 1);

        // 前缀积计算
        for (int i = 1; i < n; i++) {
            pre[i] = nums[i - 1] * pre[i - 1];
        }

        // 后缀积计算
        for (int j = n - 2; j >= 0; j--) {
            suf[j] = nums[j + 1] * suf[j + 1];
        }

        // 答案数组计算
        for (int k = 0; k < n; k++) {
            ans[k] = pre[k] * suf[k];
        }

        return ans;
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];

        // 前缀积
        int pre = 1;
        for (int i = 0; i < n; i++) {
            ans[i] = pre;
            pre *= nums[i];
        }

        // 后缀积
        int suf = 1;
        for (int j = n - 1; j >= 0; j--) {
            ans[j] *= suf;
            suf *= nums[j];
        }

        return ans;
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 将数字放置到正确的位置
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                // 交换 nums[i] 和 nums[nums[i] - 1]
                swap(nums, i, nums[i] - 1);
            }
        }

        // 找到第一个不匹配的索引
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        // 如果所有的数字都在正确的位置上，则返回 n + 1
        return n + 1;
    }

    // 辅助函数，用于交换数组中的两个元素
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}