LLY的博客

Appearance

补充算法类型解题思路与代码分析 ​

1. 字符串 ​

经典例题：5. 最长回文子串 ​

题目：给你一个字符串 s，找到 s 中最长的回文子串。

解题思路：中心扩展法。遍历每个字符以及每两个字符之间的空隙作为回文中心，向两边扩展直到不能形成回文。记录最长回文的起始和结束位置。

javascript
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (s.length < 2) return s;
    let start = 0, end = 0;
    
    // 从中心向两边扩展
    function expandAroundCenter(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        // 返回以当前中心扩展得到的回文长度
        return right - left - 1;
    }
    
    for (let i = 0; i < s.length; i++) {
        // 奇数长度回文中心
        const len1 = expandAroundCenter(i, i);
        // 偶数长度回文中心
        const len2 = expandAroundCenter(i, i + 1);
        const maxLen = Math.max(len1, len2);
        if (maxLen > end - start) {
            start = i - Math.floor((maxLen - 1) / 2);
            end = i + Math.floor(maxLen / 2);
        }
    }
    return s.substring(start, end + 1);
};

关键点：

  • 回文中心可以是单个字符（奇数长度）或两个字符之间（偶数长度）。
  • 扩展时左右指针向两边移动，直到不相等。
  • 记录最长回文的起始和结束下标，最后截取返回。

2. 回溯 ​

经典例题：46. 全排列 ​

题目：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。

解题思路：回溯。使用一个 used 数组标记已使用的元素，每次从剩余元素中选一个加入当前路径，递归到下一层，最后撤销选择。

javascript
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const result = [];
    const path = [];
    const used = new Array(nums.length).fill(false);
    
    function backtrack() {
        if (path.length === nums.length) {
            result.push([...path]); // 拷贝路径
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue; // 已使用跳过
            path.push(nums[i]);
            used[i] = true;
            backtrack();
            used[i] = false; // 回溯
            path.pop();
        }
    }
    
    backtrack();
    return result;
};

关键点：

  • 使用 used 数组避免重复选取同一元素。
  • 到达叶子时（路径长度等于数组长度），将当前路径拷贝加入结果。
  • 回溯的经典模板：做选择 -> 递归 -> 撤销选择。

3. 动态规划专题 ​

经典例题：1143. 最长公共子序列 ​

题目：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

解题思路：二维动态规划。dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列长度。状态转移：如果当前字符相等，则 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

javascript
/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
};

关键点：

  • 下标从 1 开始，避免处理 i-1 和 j-1 时的边界问题。
  • 字符相等时长度加一，否则取左边或上边的最大值。
  • 时间复杂度 O(mn)，空间复杂度 O(mn)（可优化为一维）。

4. 位运算 ​

经典例题：136. 只出现一次的数字 ​

题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

解题思路：利用异或运算的性质：a ^ a = 0，a ^ 0 = a，且异或满足交换律和结合律。将所有元素异或起来，成对的元素会抵消为 0，最后剩下的就是只出现一次的元素。

javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let result = 0;
    for (const num of nums) {
        result ^= num;
    }
    return result;
};

关键点：

  • 异或运算的简洁高效，一次遍历即可。
  • 不需要额外空间，时间复杂度 O(n)。

5. 数学 ​

经典例题：50. Pow(x, n) ​

题目：实现 pow(x, n)，即计算 x 的 n 次幂函数。

解题思路：快速幂（二分递归）。将 n 视为二进制，通过分治将幂运算降为 O(log n)。注意处理负数指数。

javascript
/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if (n === 0) return 1;
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    
    function fastPow(x, n) {
        if (n === 0) return 1;
        const half = fastPow(x, Math.floor(n / 2));
        return n % 2 === 0 ? half * half : half * half * x;
    }
    
    return fastPow(x, n);
};

关键点：

  • 负指数转化为正指数再取倒数。
  • 递归分治：x^n = (x^(n/2))^2，若 n 为奇数再乘一次 x。
  • 时间复杂度 O(log n)，空间复杂度 O(log n)（递归栈）。

6. 排序 ​

经典例题：148. 排序链表 ​

题目：给你链表的头结点 head，请将其按升序排列并返回排序后的链表。

解题思路：归并排序在链表上的实现。使用快慢指针找到链表中点，递归排序左右两部分，然后合并两个有序链表。

javascript
/**
 * 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 sortList = function(head) {
    if (!head || !head.next) return head;
    
    // 找中点
    let slow = head, fast = head.next;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    const mid = slow.next;
    slow.next = null; // 切断链表
    
    // 递归排序
    const left = sortList(head);
    const right = sortList(mid);
    
    // 合并两个有序链表
    const dummy = new ListNode(0);
    let cur = dummy;
    let l = left, r = right;
    while (l && r) {
        if (l.val < r.val) {
            cur.next = l;
            l = l.next;
        } else {
            cur.next = r;
            r = r.next;
        }
        cur = cur.next;
    }
    cur.next = l ? l : r;
    return dummy.next;
};

关键点：

  • 快慢指针找中点，注意 fast 从 head.next 开始，以便 slow 落在中点前一个。
  • 归并排序递归分解，然后合并。
  • 时间复杂度 O(n log n)，空间复杂度 O(log n)（递归栈）。

7. 分治 ​

经典例题：53. 最大子数组和（分治解法） ​

题目：给你一个整数数组 nums，请你找出一个具有最大和的连续子数组，返回其最大和。

解题思路：分治法。将数组分成左右两半，最大子数组可能完全在左半、完全在右半、或跨越中点。递归计算左右半的最大子数组，再计算跨越中点的最大子数组，取三者最大值。

javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    function crossSum(left, right, mid) {
        let leftSum = -Infinity, rightSum = -Infinity;
        let sum = 0;
        // 从中点向左累加
        for (let i = mid; i >= left; i--) {
            sum += nums[i];
            leftSum = Math.max(leftSum, sum);
        }
        sum = 0;
        // 从中点+1向右累加
        for (let i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightSum = Math.max(rightSum, sum);
        }
        return leftSum + rightSum;
    }
    
    function divide(left, right) {
        if (left === right) return nums[left];
        const mid = Math.floor((left + right) / 2);
        const leftMax = divide(left, mid);
        const rightMax = divide(mid + 1, right);
        const crossMax = crossSum(left, right, mid);
        return Math.max(leftMax, rightMax, crossMax);
    }
    
    return divide(0, nums.length - 1);
};

关键点：

  • 递归终止条件：只有一个元素时返回本身。
  • 跨越中点的最大子数组必须包含中点元素，从中点向两边扩展计算最大和。
  • 时间复杂度 O(n log n)，空间复杂度 O(log n)（递归栈）。

8. 设计 ​

经典例题：146. LRU 缓存 ​

题目：设计一个 LRU（最近最少使用）缓存数据结构，支持 get 和 put 操作，要求 get 和 put 的时间复杂度为 O(1)。

解题思路：使用哈希表 + 双向链表。哈希表存储键对应的链表节点，双向链表维护节点访问顺序（最近访问的放在头部，最久未使用的在尾部）。每次 get 或 put 后，将节点移动到头部；若缓存超限，删除尾部节点。

javascript
class ListNode {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = new ListNode(0, 0); // 虚拟头
    this.tail = new ListNode(0, 0); // 虚拟尾
    this.head.next = this.tail;
    this.tail.prev = this.head;
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this.removeNode(node);
    this.addToHead(node);
    return node.value;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if (this.map.has(key)) {
        const node = this.map.get(key);
        node.value = value;
        this.removeNode(node);
        this.addToHead(node);
    } else {
        if (this.map.size >= this.capacity) {
            const tailNode = this.tail.prev;
            this.removeNode(tailNode);
            this.map.delete(tailNode.key);
        }
        const newNode = new ListNode(key, value);
        this.map.set(key, newNode);
        this.addToHead(newNode);
    }
};

LRUCache.prototype.removeNode = function(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
};

LRUCache.prototype.addToHead = function(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
};

关键点：

  • 使用虚拟头尾节点简化边界处理。
  • removeNode 和 addToHead 组合实现移动到头部。
  • 哈希表提供 O(1) 的节点查找。

9. 多线程 ​

经典例题：1114. 按序打印 ​

题目：三个线程分别调用 first()、second()、third()，要求按顺序输出 "first"、"second"、"third"。

解题思路：使用控制机制保证线程执行顺序。在 JavaScript 中，虽然没有真正的多线程，但可以用 Promise 或信号量模拟。这里给出一种使用 Promise 和锁变量的思路（适合单线程异步环境，实际多线程需用真正的同步原语）。

javascript
/**
 * 这是一个模拟的多线程环境，实际 JavaScript 是单线程的，
 * 但我们可以用 Promise 和异步操作来演示顺序控制。
 * 实际力扣中该题使用 Java/C++ 的并发机制，JavaScript 版本不常见。
 * 以下为一种基于 Promise 的顺序控制实现：
 */
class Foo {
    constructor() {
        this.promise1 = null;
        this.promise2 = null;
        this.resolve1 = null;
        this.resolve2 = null;
        this.promise1 = new Promise(resolve => this.resolve1 = resolve);
        this.promise2 = new Promise(resolve => this.resolve2 = resolve);
    }

    first(printFirst) {
        // printFirst() outputs "first". Do not change or remove this line.
        printFirst();
        this.resolve1(); // 释放第一个锁
    }

    second(printSecond) {
        this.promise1.then(() => {
            printSecond();
            this.resolve2(); // 释放第二个锁
        });
    }

    third(printThird) {
        this.promise2.then(() => {
            printThird();
        });
    }
}

关键点：

  • 使用 Promise 作为同步工具，确保 second 在 first 之后执行，third 在 second 之后执行。
  • 实际多线程环境常用信号量或条件变量。

10. 高级数据结构（树状数组） ​

经典例题：307. 区域和检索 - 数组可修改 ​

题目：实现一个类 NumArray，支持更新数组元素和计算区间和。

解题思路：使用树状数组（Fenwick Tree）。树状数组支持 O(log n) 的单点更新和前缀和查询，从而区间和可通过两个前缀和相减得到。

javascript
/**
 * @param {number[]} nums
 */
var NumArray = function(nums) {
    this.nums = nums;
    this.n = nums.length;
    this.tree = new Array(this.n + 1).fill(0);
    // 初始化树状数组
    for (let i = 0; i < this.n; i++) {
        this._add(i + 1, nums[i]); // 树状数组下标从1开始
    }
};

// 将下标 idx 处的值增加 delta（idx 从1开始）
NumArray.prototype._add = function(idx, delta) {
    while (idx <= this.n) {
        this.tree[idx] += delta;
        idx += idx & -idx; // lowbit
    }
};

// 查询前缀和 [1..idx]
NumArray.prototype._prefixSum = function(idx) {
    let sum = 0;
    while (idx > 0) {
        sum += this.tree[idx];
        idx -= idx & -idx;
    }
    return sum;
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
NumArray.prototype.update = function(index, val) {
    const delta = val - this.nums[index];
    this.nums[index] = val;
    this._add(index + 1, delta); // 转换为树状数组下标
};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function(left, right) {
    return this._prefixSum(right + 1) - this._prefixSum(left);
};

关键点：

  • 树状数组下标从 1 开始，因此原始下标需加一。
  • lowbit = i & -i 用于定位父节点。
  • 更新时只需更新所有包含该元素的父节点。
  • 查询前缀和时累加所有前缀覆盖的节点值。