LeetCode 之算法篇（1）——排序

本篇文章做leetcode的一些内容总结

题目

合并区间

解题思路：先排序后遍历
1、首先，按照区间的起始位置对所有区间进行排序。
2、接着，遍历排序后的区间，依次合并重叠的区间。具体做法是比较当前区间的起始位置和上一个合并后区间的结束位置，如果发现有重叠，则合并；否则，将当前区间加入结果集。
3、最终得到的结果集即为合并后的不重叠区间数组。

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    if (!intervals || intervals.length === 0) {
        return [];
    }

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

    const merged = [intervals[0]];

    for (let i = 1; i < intervals.length; i++) {
        const currentInterval = intervals[i];
        const lastMerged = merged[merged.length - 1];

        // 如果有重叠，则合并区间
        if (currentInterval[0] <= lastMerged[1]) {
            lastMerged[1] = Math.max(lastMerged[1], currentInterval[1]);
        } else {
            // 否则，将当前区间加入结果集
            merged.push(currentInterval);
        }
    }

    return merged;
};

轮转数组

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
function rotate(nums, k) {
    const n = nums.length;
    k %= n;  // 处理 k 大于数组长度的情况

    // 整体反转
    reverse(nums, 0, n - 1);

    // 前 k 个元素反转
    reverse(nums, 0, k - 1);

    // 后 n-k 个元素反转
    reverse(nums, k, n - 1);
}

// 反转数组的指定区间
function reverse(nums, start, end) {
    while (start < end) {
        const temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

将数组元素向右轮转 k 个位置的思路是通过反转数组的不同部分来实现的。这种思路的来源可以追溯到翻转字符串的问题，其中我们也会使用类似的方法。

反转数组的思路：

1、整体反转： 先将整个数组进行反转，这样原来数组的末尾元素就变成了开头。
2、部分反转： 接着，对前 k 个元素进行反转，这样原来数组的开头 k 个元素就变成了末尾。
3、再次部分反转： 最后，对剩余的 n-k 个元素进行反转，将它们恢复到正确的顺序。
这样整个过程就相当于是将数组的元素向右轮转了 k 个位置。

为什么是执行三次反转呢？

在这里，执行三次反转是为了保持反转的方向，确保数组的元素正确地向右轮转 k 个位置。具体来说：

1、整体反转是为了将原数组的末尾元素移动到数组的开头。
2、第一次部分反转是为了将这些位于开头的元素移动到正确的末尾位置。
3、第二次部分反转是为了将原来的开头元素恢复到数组的正确位置。

这种思路的直观性在于，通过反转数组的不同部分，可以有效地实现循环移动的效果。这种方法在处理数组旋转等问题时非常常见。