算法笔记第 02 周

本系列致力于将高频的算法题进行回顾与分析，感兴趣的小伙伴请继续阅读吧。

88. 合并两个有序数组

力扣题目链接 (opens new window)

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

思路：

需要注意的是，题目要求不要返回任何数据，要在原地修改nums1来达到最终目的。

按照题目要求，可以从数组1的末尾开始添加元素，找到数组1最后一位元素和数组2的最后一位元素，哪个元素更大，就将哪个元素放到数组1的末尾。这样合并后的数组就是非递减顺序。

通过指针len、len1、len2的递减，达到了指针左移的效果。如果数组1是空数组，则直接将数组2的元素依次放入数组1即可。

合并

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    let len1 = m - 1;
    let len2 = n - 1;
    let len = m + n - 1;
    while(len2 >= 0) {
        if (len1 < 0) {
            nums1[len--] = nums2[len2--];
        }
        nums1[len--] = nums1[len1] >= nums2[len2] ? nums1[len1--] : nums2[len2--];
    }
};

总结

本题考查有序数组的合并，跟有序链表是非类似，但是链表必须从头开始遍历，数组则不需要。核心思路是从后往前追加元素，较大者放入数组的末尾。难度系数简单。

相比之下，合并两个有序链表一般是创建一个哨兵节点，然后对比并找到两个链表中较小元素，依次追加到哨兵节点后，最后返回哨兵节点的next指针便是一个合并后的有序链表。

15. 三数之和

力扣题目链接 (opens new window)

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

提示：

• 0 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

思路：

本题是两数之和的升级版，但是思路和两数之和不尽相同。

本题采用排序+双指针的方式题解。首先确保数组是有序数组，然后固定一个元素，使用双指针分别指向固定元素的下一个元素和数组末尾元素，将三者元素相加进行判断。因为数组是有序的，所以和大于0时，左移右指针；和小于0时，右移左指针。等于0时，将结果放入结果数组。

由于题目要求不能包含重复的集合，因此需要去重处理。当遇到前后相同元素时，要直接跳过。

双指针

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let length = nums.length; // 缓存数组长度
    if (!nums || length < 3) return []; // 提前返回
    let result = []; // 初始化结果数组
    let left = null; // 初始化左指针
    let right = null; // 初始化右指针
    nums.sort((a, b) => a - b); // 对数组进行排序
    for (let i = 0; i < length; i++) {
        if (nums[i] > 0) break; // 如果第一个数就大于0，那么后续相加肯定大于0，提前返回
        if (i > 0 && nums[i] === nums[i - 1]) continue; // 去重
        left = i + 1; // 左指针指向当前索引的下一个索引
        right = length - 1; // 右指针指向数组最后一个元素
        while(left < right) { // 循环终止条件是左指针大于等于右指针
            let num = nums[i] + nums[left] + nums[right]; // 三数之和
            if (!num) { // 和等于0
                result.push([nums[i], nums[left], nums[right]]); // 放入结果数组
                while(left < right && nums[left] === nums[left + 1]) left++; // 去重
                while(left < right && nums[right] === nums[right - 1]) right--; // 去重
                left++; // 结果中不包含重复的集合，因此移动左右指针
                right--;
            }
            else if (num < 0) left++; // 和大于0，右移左指针
            else if (num > 0) right--; // 和小于0，左移右指针
        }
    }
    return result;
};

349. 两个数组的交集

力扣题目链接 (opens new window)

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

思路：

核心思路是用空间换时间。这里使用哈希表存储第一个数组的值，然后遍历第二个数组，当存在于哈希表中，则将元素添加至结果数组中，同时将该元素从哈希表中删除，否则无法确保结果值唯一。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    let map = new Map();
    let result = [];
    for (const num1 of nums1) {
        map.set(num1, num1);
    }
    for (const num2 of nums2) {
        if (map.has(num2)) {
            result.push(num2);
            map.delete(num2);
        }
    }
    return result;
};

146. LRU 缓存

力扣题目链接 (opens new window)

请你设计并实现一个满足  LRU (最近最少使用) 缓存 (opens new window) 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 10^5
• 最多调用 2 * 10^5 次 get 和 put

思路：

本题借助Map的特性来实现LRU。根据MDN的描述，Map对象保存键值对，并且能够记住键的原始插入顺序。因此插入的顺序就是最近使用的顺序。

当获取值时，直接get获取，然后删除掉当前值，再重新插入到map中，这样就实现了最近原则。

当设置值时，如果当前值已存在，则先删除再插入；如果当前缓存已满员，则删除掉最先插入的一条数据，再插入当前值。需要注意的是，可以通过以下方式来获取map中的第一条值。

const map = new Map();
const first_value = map.keys().next().value;

MDN中说到，keys() 返回一个引用的 Iterator 对象。它包含按照 顺序 插入 Map 对象中每个元素的key值。获取迭代器的第一个键的值就是上述写法。同理，values()也有类似的作用。

最终的代码如下：

Map

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (this.cache.has(key)) {
        let temp = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, temp);
        return temp;
    }
    return -1;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if (this.cache.has(key)) {
        this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
        this.cache.delete(this.cache.keys().next().value);
    }
    this.cache.set(key, value);
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

总结

LRU算法思想在vue的keep-alive组件中有被使用。本题也是面试中常被问到的高频面试题。因此需要完全掌握。

更进一步的，也需要我们了解vue的keep-alive组件的源码是如何写的，学习优秀的源码，我们才可以走的更远。

21. 合并两个有序链表

力扣题目链接 (opens new window)

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例一：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

提示：

• 两个链表的节点数目范围是 [0, 50]
• 100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

思路：

有序链表的合并问题，是最经典的链表题目，考查链表的遍历与末尾的判断。

这里我们声明一个哨兵节点作为新链表的起始位置。然后开始比较两个链表的值，将具有较小值的链表节点赋值给新链表当前节点的next指针。然后新链表和待排序链表的当前指针都向后移动一位继续下个节点的比较。

当list1或者list2为空时，跳出循环。此时可能还有另一个链表的指针还没有走到末尾，因此直接将尚未走完的链表赋值给新链表当前节点的next指针。

最后返回哨兵节点的下一个节点引用即可。因为哨兵节点是用于串联起一个链表，最终结果中不能包含该节点。

完整代码如下：

哨兵节点

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    let head = new ListNode(0); // 初始化哨兵节点
    let cur = head; // 指向cur指针
    while(list1 && list2) { // 找到两个链表的较小者，追加到新链表中
        if (list1.val < list2.val) {
            cur.next = list1; // cur的next指向较小节点
            list1 = list1.next; // 头部指向下个节点
        } else {
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next; // 指向下一个节点
    }
    cur.next = list1 || list2; // 继续拼接尚未遍历完的链表
    return head.next; // 返回哨兵节点的下一个节点
};

总结

本题考查有序链表的合并。在链表的排序中，也会使用到有序链表的合并，同时还用到了二分法以及归并排序。是一道值得掌握的算法题。

141. 环形链表

力扣题目链接 (opens new window)

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

示例1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

提示：

• 链表中节点的数目范围是 [0, 104]
• 105 <= Node.val <= 105
• pos 为 1 或者链表中的一个 有效索引 。

进阶： 你能用 O(1)（即，常量）内存解决此问题吗？

思路：

判断链表有环的问题，可以采用快慢指针的方法来解决。我们规定快指针每次移动两步，慢指针每次移动一步，如果链表有环，那么两个指针终将相遇，此时返回true。如果链表没环，当快指针走到链表末尾时，直接返回false 。

因为只需要维护两个指针变量，因此空间复杂度是O(1) 。

下面是完整代码：

快慢指针

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if (!head || !head.next) return false;
    let fast = head.next.next;
    let slow = head.next;
    while(fast !== slow) {
        if (!fast || !fast.next) return false;
        fast = fast.next.next;
        slow = slow.next;
    }
    return true;
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

投机取巧

本题还可以采用JSON的一个特性求解，就是如果对象中存在循环引用，那么执行JSON.stringify() 会报错。我们可以通过是否可以捕获到错误来判断是否有环。代码如下：

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let flag = false;
    try {
        JSON.stringify(head);
    } catch {
        flag = true;
    }
    return flag;
};

当然在平常的面试或者工作中，不要使用此方法来求解。

总结

本题考查快慢指针的应用，难度系数简单。需要注意的是，要处理边界情况，防止获取undefined的next属性，从而导致报错。

206. 反转链表

力扣题目链接 (opens new window)

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

提示：

• 链表中节点的数目范围是 [0, 5000]
• 5000 <= Node.val <= 5000

思路：

翻转链表也是很经典的链表相关题目，属于必须掌握的。需要声明两个指针，分别指向前驱节点和当前节点，而翻转链表的核心就是当前节点的next指向的变化。

首先缓存cur.next ，将cur.next 指向前驱节点pre，然后将前驱节点和当前节点分别右移一位。从而继续处理下个节点。如果下个节点为空，则停止处理。最终pre的指向就是翻转前链表的尾部节点，也是翻转后链表的头部，返回pre即可。

链表

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if (!head || !head.next) return head;
    let pre = null;
    let cur = head;
    while(cur) {
        let temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
};

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)