算法笔记第 03 周

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

876. 链表的中间结点

力扣题目链接 (opens new window)

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

思路：

本题采用快慢指针解决。快指针每次走两步，慢指针每次走一步，当快指针走到链表尾部时，慢指针所处的位置就是链表的中间节点。

完整代码如下：

快慢指针

/**
 * 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 middleNode = function(head) {
    let fast = head;
    let slow = head;
    while(fast && fast.next) {
        fast = fast.next.next
        slow = slow.next;
    }
    return slow;
};

复杂度分析：

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

总结

快慢指针的经典应用。包括寻找链表的中间节点、检查链表是否存在环。都需要重点掌握。

19. 删除链表的倒数第 N 个结点

力扣题目链接 (opens new window)

给你一个链表，删除链表的倒数第 n **个结点，并且返回链表的头结点。

示例1：

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

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

思路：

本题适合使用快慢指针求解。首先声明一个哨兵节点，作为链表的新头部。最终返回哨兵节点的next指向，就是链表的头节点。

然后声明快慢指针，首先让快指针先走n步。然后快慢指针同步走，直到快指针走到链表尾部，此时慢指针所处位置就是倒数第n + 1个节点。因为我们声明了一个哨兵节点，所以慢指针的下一步就是倒数第n个节点，所以删除该节点的逻辑就是将该节点的下下个next指向，重新指向给当前节点的next指向，就达到了删除节点的目的。

快慢指针

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    // 哨兵节点
    let dump = new ListNode();
    dump.next = head;
    // 快慢指针
    let fast = slow = dump;

    // 快指针先走n步
    while(n--) {
        fast = fast.next;
    }
    // 快指针走到最后，当前slow为倒数第n+1个节点
    while(fast && fast.next) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dump.next;
};

160. 相交链表

力扣题目链接 (opens new window)

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 1 <= m, n <= 3 * 10^4
• 1 <= Node.val <= 10^5
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

本题与****剑指 Offer 52. 两个链表的第一个公共节点 (opens new window)** 为同一题，先前已做过题解分析，此处不做记录。

我们直接看代码：

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let A = headA;
    let B = headB;
    while(A !== B) {
        A = A !== null ? A.next : headB;
        B = B !== null ? B.next : headA;
    }
    return A;
};

611. 有效三角形的个数

力扣题目链接 (opens new window)

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [4,2,3,4]
输出: 4

提示:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

思路：

本题是三数之和的衍生版本。判断三个数是否构成三角形的判断依据是 两边之和大于第三边 。

解题的思路是使用 排序+双指针 。首先我们要对数组进行排序，确保数组有序可以省去很多不必要的判断。排序后的数组末尾元素就是较大的。我们就依次固定末尾元素，充当三角形的第三条边，然后依次向前进行判断。固定好了第三条边，此时需要在第三条边的范围内分别初始化两条边。第一条边默认是数组第一个元素，第二条边默认是当前第三条边的前一个元素。然后通过判断不断收窄范围。

具体来说，就是在i指针(第一条边)小于j指针(第二条边)的前提下，来判断是否满足构成三角形的条件。如果满足，两个指针之间所有的值(j - i)都是满足的，同时左移j指针。如果不满足，则右移i指针，继续下一迭代判断。

最终累加出来的count，就是满足的个数，返回即可。

排序+双指针

/**
 * @param {number[]} nums
 * @return {number}
 */
var triangleNumber = function(nums) {
    if (!nums || nums.length < 3) return 0; // 如果不满足条件则直接返回0
    let count = 0; // 初始化三角形个数
    nums.sort((a, b) => a - b); // 排序
    for (let k = nums.length - 1; k > 1; k--) { // 固定第三条边
        let i = 0; // 初始化第一条边
        let j = k - 1; // 初始化第二条边
        while(i < j) {
            if (nums[i] + nums[j] > nums[k]) { // 满足条件
                count += j - i; // 累加所有满足条件的可能
                j--; // 左移第二条边
            } else {
                i++; // 右移第一条边
            }
        }
    }
    return count;
};

总结

不管是两数之和还是三数之和，均考查了双指针的思想。采用双指针的前提是要让数据有序，否则无法合理的使用双指针进行求解，这是我们需要特别注意的。

42. 接雨水

力扣题目链接 (opens new window)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

提示：

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

思路：

本题可以使用动态规划、单调栈、双指针求解。这次采用双指针法。

首先明确几个变量的含义：

left_max：左边的最大值，它是从左往右遍历找到的
right_max：右边的最大值，它是从右往左遍历找到的
left：从左往右处理的当前下标
right：从右往左处理的当前下标

定理一：在某个位置i处，它能存的水，取决于它左右两边的最大值中较小的一个。

定理二：当我们从左往右处理到left下标时，左边的最大值left_max对它而言是可信的，但right_max对它而言是不可信的。

定理三：当我们从右往左处理到right下标时，右边的最大值right_max对它而言是可信的，但left_max对它而言是不可信的。

对于位置left而言，它左边最大值一定是left_max，右边最大值“大于等于”right_max，这时候，如果left_max < right_max成立，那么它就知道自己能存多少水了。无论右边将来会不会出现更大的right_max，都不影响这个结果。 所以当left_max < right_max时，我们就希望去处理left下标，反之，我们希望去处理right下标。

上述思路参考自官方题解，下面说说个人的看法。

能接多少雨水，取决于低洼左右的较低高度的柱子。可以理解为就是所谓的木桶理论。因此通过左右指针，分别找到左边的最大值和右边的最大值。然后比较哪个最大值较小，就以哪个为基准计算更低处与其的差值，然后累加到最终结果中。因为这里计算的是垂直方向的差值，因此不需要做额外的处理。

双指针

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let total = 0;
    let left = 0;
    let right = height.length - 1;
    let leftMax = 0;
    let rightMax = 0;
    while (left <= right) {
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);
        if (leftMax < rightMax) {
        total += leftMax - height[left];
        left++;
        } else {
        total += rightMax - height[right];
        right--;
    }
  }
  return total;
};

总结

本题有多种解法，这里采用双指针求解。如果采用动态规划，那么就需要找到动态规划方程然后再进行求解。双指针通过找到柱子的短板，进而求得每个柱子在垂直方向的差值，直到双指针相遇，求出的累加和就是最后的结果。

151. 翻转字符串里的单词

力扣题目链接 (opens new window)

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明：

• 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
• 翻转后单词间应当仅用一个空格分隔。
• 翻转后的字符串中不应包含额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

提示：

• 1 <= s.length <= 10^4
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

进阶：

• 请尝试使用 O(1) 额外空间复杂度的原地解法。

本题与剑指Offer58的题目相同，具体的题解看这里 (opens new window)。

下面是代码：

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    s = s.trim(); // 去除首尾空格
    let i = s.length - 1; // 初始化单词的左边界
    let j = i; // 初始化单词的右边界
    let result = []; // 初始化结果数组
    while(i >= 0) { // 单词的左边界小于0则终止循环
        while(i >= 0 && s[i] !== ' ') i--; // 寻找单词的左边界
        result.push(s.slice(i + 1, j + 1)); // 将单词放至结果数组
        while(i >= 0 && s[i] === ' ') i--; // 跳过单词之间的空隙
        j = i; // 重置单词的右边界
    }
    return result.join(' '); // 结果数组拼接为字符串后返回
};

14. 最长公共前缀

力扣题目链接 (opens new window)

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成

思路：

首先考虑逐个字符串对比，来确定最终的公共前缀。按照题目提示，数组至少会有一项，因此不需要做空置判断。

假设第一个数组元素就是最长的前缀。然后从数组的第二个元素开始遍历。然后依次对比数组的当前元素和最长前缀的每个字符，直到不一样为止。那么前面一样的字符串就是最新的最长前缀。如果对比时发现前缀已经是空字符串，便提前返回，无需再判断。

逐个比较

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let prevs = strs[0];
    for (let i = 1; i < strs.length; i++) {
        let j = 0;
        while(j < prevs.length && j < strs[i].length) {
            if (prevs[j] !== strs[i][j]) break;
            j++;
        }
        prevs = prevs.slice(0, j);
        if (!prevs) return '';
    }
    return prevs;
};

优化

上述方法是将每个字符串进行比较，来获取最长前缀。其实起决定性因素的是最大字符串和最小字符串。只需要对比两者的公共前缀，也就是整个数组的公共前缀。那么做法就是先进行一次遍历，找出最大字符串和最小字符串的索引。然后依次对比两者的每个字符，即可找出最长前缀。

本题的另外一种解法也可以采用字典树进行求解。

字典树

此方法是效率最高的一种方法。通过构建字典树，可以字典树的基础上去查找最长公共前缀。大概逻辑是：

字符串数组的最长公共序列就为从根节点开始遍历树，直到：

• 遍历节点存在超过一个子节点的节点
• 或遍历节点为一个字符串的结束字符

为止，走过的字符为字符串数组的最长公共前缀。

var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    // 初始化 Trie 树
    let trie = new Trie()
    // 构建 Trie 树
    for(let i = 0; i < strs.length; i++) {
        if(!trie.insert(strs[i])) return ""
    }
    // 返回最长公共前缀
    return trie.searchLongestPrefix()
};
// Trie 树
var Trie = function() {
    this.root = new TrieNode()
};
var TrieNode = function() {
    // next 放入当前节点的子节点
    this.next = {};
    // 当前是否是结束节点
    this.isEnd = false;
};
Trie.prototype.insert = function(word) {
    if (!word) return false
    let node = this.root
    for (let i = 0; i < word.length; i++) {
        if (!node.next[word[i]]) {
            node.next[word[i]] = new TrieNode()
        }
        node = node.next[word[i]]
    }
    node.isEnd = true
    return true
};
Trie.prototype.searchLongestPrefix = function() {
    let node = this.root
    let prevs = ''
    while(node.next) {
        let keys = Object.keys(node.next)
        if(keys.length !== 1) break
        if(node.next[keys[0]].isEnd) {
            prevs += keys[0]
            break
        }
        prevs += keys[0]
        node = node.next[keys[0]]
    }
    return prevs
}

总结

本题考查字典树的构建与公共前缀的查找。前端领域，一般不太能遇到使用字典树这种思想的场景，但是这种思路也是要掌握的。尤其适合有大量相同前缀的数据，使用字典树的效率会非常高。

3. 无重复字符的最长子串

力扣题目链接 (opens new window)

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入:s = "abcabcbb"
输出:3
解释: 因为无重复字符的最长子串是"abc"，所以其长度为 3。

提示：

• 0 <= s.length <= 5 * 10^4
• s 由英文字母、数字、符号和空格组成

思路：

本题与剑指Offer48 (opens new window) 属于同一题，已经做过题解分析，这里不再赘述。直接看代码：

双指针+哈希表

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let i = -1;
    let result = 0;
    let map = new Map();
    for(let j = 0; j < s.length; j++) {
        const current = s.charAt(j); // 记录当前索引下的字符
        if (map.has(current)) { // 如果字符存在于哈希表中
            i = Math.max(i, map.get(current)) // 更新i为最大的索引
        }
        map.set(current, j); // 将当前字符的索引存储于哈希表中
        result = Math.max(result, j - i); // 存储较大值
    }
    return result;
};

415. 字符串相加

力扣题目链接 (opens new window)

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

示例 1：

输入：num1 = "11", num2 = "123"
输出："134"

提示：

• 1 <= num1.length, num2.length <= 10^4
• num1 和num2 都只包含数字 0-9
• num1 和num2 都不包含任何前导零

思路：

根据题目要求，不能直接转换为数字进行相加。因此我们这里需要逐位的从低位到高位相加。

具体做法是，从两个字符串的低位开始相加，得出值为数字的结果。然后将结果和10进行取余，得到的就是不考虑进位的当前位的值，然后与低位的字符串结果相拼。如果数字结果大于9，意味着需要进位，将进位的信息保存至temp，用来下次循环的相加。

当两个字符串都处理完毕后，还需要判断最终temp是否有进位，如果有，则最高位还需要拼接1。

最终返回结果字符串即可。

逐位相加

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function(num1, num2) {
    let len1 = num1.length;
    let len2 = num2.length;
    let result = '';
    let temp = 0; // 初始化当前位的计算结果
    while(len1 || len2) {
        if (len1) temp += +num1[--len1];
        if (len2) temp += +num2[--len2];
        result = temp % 10 + result; // 字符串拼接
        temp = temp > 9 ? 1 : 0; // 计算进位的值
    }
    if (temp) result = 1 + result;
    return result;
};

43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

提示：

• 1 <= num1.length, num2.length <= 200
• num1 和 num2 只能由数字组成。
• num1 和 num2 都不包含任何前导零，除了数字0本身。

思路：

两个数M和N相乘的结果可以由 M 乘上 N 的每一位数的和得到。

因此可以：

• 计算 num1 依次乘上 num2 的每一位的和
• 把得到的所有和按对应的位置累加在一起，就可以得到 num1 * num2 的结果

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
let multiply = function(num1, num2) {
    if(num1 === '0' || num2 === '0') return "0"
    let res = []
    for(let i = 0; i < num1.length; i++){
        let tmp1 = +num1[num1.length - 1 - i]
        for(let j = 0; j < num2.length; j++){
            let tmp2 = +num2[num2.length - 1 - j]
            let pos = res[i + j] ? res[i + j] + tmp1 * tmp2 : tmp1 * tmp2
            res[i + j] = pos % 10
            pos >= 10 && (res[i + j + 1] = res[i + j + 1] ? res[i + j + 1] + Math.floor(pos / 10) : Math.floor(pos / 10));
        }
    }
    return res.reverse().join("");
}

复杂度分析：

• 时间复杂度：O(m * n)
• 空间复杂度：O(m + n)

总结

上面代码的核心逻辑是：

• 使用res数组来保存指定位的数字，以防需要进位；
• 首先依次找到num1 从低位到高位的每一个数字；
• 然后依次找到num2 从低位到高位的每一个数字；
• 更新res指定位上的数字；
• 如果指定位的数字超过10，则需要更新更高位的数字；

最终将res翻转并拼接成字符串返回。因为res的保存顺序是由低位到高位，因此需要进行翻转。