算法笔记

PriorityQueue 优先队列

第k大的元素

Leetcode 215. Kth Largest Element in an Array

• 题目: 给定一个数组nums和一个整数k，输出数组中第k大的元素

Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5

• 解法1: 最小堆 什么是 heap

1. 初始化一个大小为 k 的最小堆，将前 k 个元素加入堆中
2. 遍历剩余的元素，如果当前元素大于堆顶元素，则替换堆顶
3. 遍历结束后，堆顶即为第 k 大的元素

• Python
• Javascript

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        if k == 0:
            return []

        heap = nums[:k]
        heapq.heapify(heap)  # 建立最小堆

        for num in nums[k:]:
            if num > heap[0]:  # 只在当前元素大于堆顶时替换
                heapq.heapreplace(heap, num)

        return heap[0] # 如果是 heap, 那就是返回数组前 k 大的元素

class Solution {
    findKthLargest(nums, k) {
        const minPQ = new MinPriorityQueue();
        for (let i = 0; i < nums.length; i++) {
            minPQ.enqueue(nums[i]);
            if (minPQ.size() > k)
                minPQ.dequeue();
        }
        return minPQ.front().element;
    }
}

• 解法2: 快速选择 Quick Select

1. 通过「分区」方法将数组分为两部分，左边比 pivot 大，右边比 pivot 小
2. 如果 pivot 的位置刚好是 k，则 pivot 即为第 k 大的元素
3. 如果 pivot 的位置大于 k，递归左边部分
4. 如果 pivot 的位置小于 k，递归右边部分

• Python
• Javascript

class Solution:
    def partition(self, nums: List[int], low: int, high: int) -> int:
        pivot = nums[high]
        i = low - 1
        for j in range(low, high):
            if nums[j] > pivot:  # 按降序排列
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1], nums[high] = nums[high], nums[i + 1]
        return i + 1


    def quickSelect(self, nums: List[int], low: int, high: int, k: int) -> int:
        if low <= high:
            pivot_index = self.partition(nums, low, high)
            if pivot_index == k:
                return nums[k]
            elif pivot_index > k:
                return self.quickSelect(nums, low, pivot_index - 1, k)
            else:
                return self.quickSelect(nums, pivot_index + 1, high, k)


    def findKthLargest(self, nums: List[int], k: int) -> int:
        return self.quickSelect(nums, 0, len(nums) - 1, k - 1)

class Solution {
    partition(nums, left, right) {
        const pivot = nums[right]; // 选择最右边的元素作为 pivot
        let i = left - 1; // 指针 i 表示小于 pivot 的区域的最后位置

        for (let j = left; j < right; j++) {
            if (nums[j] > pivot) { // 降序排列：将较大的元素放在左边
                i++;
                [nums[i], nums[j]] = [nums[j], nums[i]]; // 交换元素
            }
        }

        // 将 pivot 放到正确位置
        [nums[i + 1], nums[right]] = [nums[right], nums[i + 1]];
        return i + 1; // 返回 pivot 的索引
    }

    quickSelect(nums, left, right, k) {
        if (left <= right) {
            const pivotIndex = this.partition(nums, left, right);

            if (pivotIndex === k)
                return nums[k];
            else if (pivotIndex > k)
                return this.quickSelect(nums, left, pivotIndex - 1, k);
            else
                return this.quickSelect(nums, pivotIndex + 1, right, k);
        }
    }

    findKthLargest(nums, k) {
        return this.quickSelect(nums, 0, nums.length - 1, k - 1);
    }
}

---

前k个元素的频率

Leetcode 347. Top K Frequent Elements

• 题目: 给定一个数组nums和一个整数k，返回数组中出现频率最高的前k个元素

Input: nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]

• 解法1: heapq.nlargest (Python)

1. 使用 `Counter` 统计元素出现频率
2. 调用 `heapq.nlargest`，在 O(n + k log n) 时间内找到前 k 大的频率

from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        if len(nums) == k:
            return nums

        count = Counter(nums)
        return heapq.nlargest(k, count.keys(), key=count.get)

• 解法2: 最小堆

1. 统计元素频率，使用堆存储前 k 个高频元素
2. 每次比较当前元素与堆顶的频率，维护堆的大小为 k
3. 最后堆中的元素即为结果

• Python
• Javascript

from collections import Counter
import heapq

class Solution:
    def topKFrequent(nums: List[int], k: int) -> List[int]:
        # 1. 统计每个元素的频率
        freq_map = Counter(nums)

        # 2. 使用最小堆找到前 k 个频率最高的元素
        heap = []
        for num, freq in freq_map.items():
            heapq.heappush(heap, (freq, num))  # 堆中存储 (频率, 元素)
            if len(heap) > k:
                heapq.heappop(heap)  # 维持堆的大小为 k

        # 3. 提取堆中的元素
        return [num for freq, num in heap]

class Solution {
    topKFrequent(nums, k) {
        // 1. 统计频率
        const freqMap = new Map();
        for (const num of nums)
            freqMap.set(num, (freqMap.get(num) || 0) + 1);

        // 2. 使用最小堆
        const minPQ = new MinPriorityQueue({ priority: x => x[0] });
        for (const [num, freq] of freqMap) {
            minPQ.enqueue([freq, num]);
            if (minPQ.size() > k)
                minPQ.dequeue();
        }

        // 3. 提取堆中的元素
        return minPQ.toArray().map(item => item.element[1]);
    }
}

• 解法3: 桶排序

1. 统计频率，并将元素按频率存储在“桶”中
2. 桶的索引表示频率，从高到低提取前 k 个元素

• Python
• Javascript

from collections import Counter
import heapq

class Solution:
    def topKFrequent(nums: List[int], k: int) -> List[int]:
        # 1. 统计频率
        freq_map = Counter(nums)

        # 2. 桶排序
        bucket = [[] for _ in range(len(nums) + 1)]
        for num, freq in freq_map.items():
            bucket[freq].append(num) # 将元素按频率存储在对应桶中

        # 3. 从高频到低频提取前 k 个元素
        result = []
        for i in range(len(bucket) - 1, 0, -1):
            for num in bucket[i]:
                result.append(num)
                if len(result) == k:
                    return result

class Solution {
    topKFrequent(nums, k) {
        // 1. 统计频率
        const freqMap = new Map();
        for (const num of nums)
            freqMap.set(num, (freqMap.get(num) || 0) + 1);

        // 2. 桶排序
        const bucket = Array(nums.length + 1).fill(null).map(() => []);
        for (const [num, freq] of freqMap)
            bucket[freq].push(num);

        // 3. 从高频到低频提取前 k 个元素
        const result = [];
        for (let i = bucket.length - 1; i >= 0 && result.length < k; i--)
            result.push(...bucket[i]);
        return result;
    }
}

最小堆: 更灵活，可以适应动态输入数据，适合k较小的情况
桶排序: 更高效，尤其是当k较大或频率分布较均匀时

---

Design

LRU 缓存

Leetcode 146. LRU Cache

• 题目: 实现一个数据结构LRU Cache (Least Recently Used Cache)，它能够在固定容量下缓存键值对，同时满足以下两种操作

  • get(key): 如果键存在，返回其值，并将该键标记为最近使用。如果不存在，返回-1
  • put(key, value): 插入新键值对。如果缓存已满，移除最久未使用的键值对

• 解法1: OrderedDict (Python)

  • Python中的OrderedDict可以非常直观地实现LRU Cache
  • OrderedDict自动维护插入顺序，最久未使用的元素总在最前面
  • 提供了move_to_end(key)方法，可以将某个键移动到末尾，表示最近使用

get 方法
    如果键存在，将其移到末尾，表示最近使用，并返回对应值
    如果键不存在，返回 -1

put 方法
    如果键存在，更新值并移到末尾
    如果键不存在，直接添加
    如果缓存超出容量，删除最前面的键（popitem(last=False)）

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict() # 创建一个有序字典
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key in self.cache:
            # 将访问的键移到末尾
            self.cache.move_to_end(key)
            return self.cache[key]
        return -1
        

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # 如果键已经存在，更新值，并移到末尾
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # 超过容量时，删除第一个键（最久未使用）
            self.cache.popitem(last=False)

• 解法2: Map (Javascript)
  • JS的Map数据结构，它按插入顺序存储键值对
  • 使用set(key, value)方法更新键时，会将该键移到末尾，表示最近使用

get 方法
    如果键存在，先删除它，再重新插入到末尾
    如果键不存在，返回 -1

put 方法
    如果键已存在，先删除它，再插入新值
    如果超过容量，删除最老的键（Map.keys().next().value 返回第一个键）

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map(); // Map 是有序的，按插入顺序维护键值对
    }

    get(key) {
        if (!this.cache.has(key)) return -1; 
        const value = this.cache.get(key);
        this.cache.delete(key); // 删除旧位置的键
        this.cache.set(key, value); // 将键移到末尾（最新使用）
        return value;
    }

    put(key, value) {
        if (this.cache.has(key))
            this.cache.delete(key); // 如果键已存在，先删除它
        this.cache.set(key, value); // 插入新键值对

        if (this.cache.size > this.capacity) {
            const oldestKey = this.cache.keys.next().value; // 获取最老的键
            this.cache.delete(oldestKey);
        }
    }
}

JS 的写法要比 Python 简单

---

实现随机集合

Leetcode 380. Insert Delete GetRandom O(1)

• 题目: 设计一个支持以下操作的集合，在平均时间复杂度为O(1)下实现插入、删除和随机获取操作
  • insert(val): 如果集合中没有该值，则插入
  • remove(val): 如果集合中存在该值
  • getRandom(): 随机返回集合中的一个元素，每个元素被返回的概率相等

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

• 解法: 数组 + 哈希表

1. 数组存储集合的元素，用于随机访问
2. 哈希表记录每个值在数组中的索引，方便 O(1) 时间查找和删除

• Python
• Javascript

import random

class RandomizedSet:

    def __init__(self):
        self.dict = {}
        self.list = []

    def insert(self, val: int) -> bool:
        if val in self.dict:
            return False
        self.dict[val] = len(self.list) # 记录值的索引
        self.list.append(val) # 将值添加到列表
        return True

    def remove(self, val: int) -> bool:
        if val not in self.dict:
            return False
        index = self.dict[val] # 获取值的索引
        last_element = self.list[-1] # 获取列表中的最后一个元素
        self.list[index] = last_element # 将最后一个元素移到被移除的位置
        self.dict[last_element] = index # 更新最后一个元素的索引
        self.list.pop() # 删除最后一个元素
        del self.dict[val] # 从字典中删除该值
        return True

    def getRandom(self) -> int:
        return random.choice(self.list) # 随机选择一个列表中的值

class Solution {
    constructor() {
        this.map = new Map();
        this.list = [];
    }

    insert(val) {
        if (this.map.has(val)) return false;
        this.map.set(val, this.list.length); // 存储值和索引
        this.list.push(val); // 将值添加到数组
        return true;
    }

    remove(val) {
        if (!this.map.has(val)) return false;
        const index = this.map.get(val); // 获取值的索引
        const lastElement = this.list[this.list.length - 1]; // 获取最后一个值
        this.list[index] = lastElement; // 将最后一个值移到被删除的位置
        this.map.set(lastElement, index); // 更新最后一个值的索引
        this.list.pop(); // 删除最后一个值
        this.map.delete(val); // 从映射中删除该值
        return true;
    }

    getRandom() {
        const randomIndex = Math.floor(Math.random() * this.list.length);
        return this.list[randomIndex];
    }
}

---

LinkedList 链表

反转链表

Leetcode 206. Reverse Linked List

• 题目: 给定一个单链表的头节点head，将其完全反转，并返回新的头节点

Input: head = [0,1,2,3]
Output: [3,2,1,0]

• 解法: Two Pointers 双指针

1. 初始化两个指针：prev 表示前一个节点，curr 表示当前节点
2. 遍历链表，逐个调整当前节点的指向，使其指向前一个节点
3. 移动指针，直到链表尾部
4. 返回 prev 作为新的头节点

• Python
• Javascript

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head

        while curr:
            tmp = curr.next # 暂存下一个节点
            curr.next = prev # 当前节点指向前一个节点
            prev = curr # prev 向前移动到当前节点
            curr = tmp # curr 向前移动到下一个节点

        return prev   

class Solution {
    reverseList(head) {
        let prev = null;
        let curr = head;

        while (curr) {
            let tmp = curr.next; // 暂存下一个节点
            curr.next = prev; // 当前节点指向前一个节点
            prev = curr; // prev 向前移动到当前节点
            curr = tmp; // curr 向前移动到下一个节点
        }

        return prev;
    }
}

---

反转链表中间部分

Leetcode 92. Reverse Linked List II

• 题目: 给定一个单链表的头节点head，以及两个整数left和right，反转链表中从位置left到位置right的部分，并返回链表的头节点

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

• 解法: 虚拟头节点法

1. 添加虚拟头节点：用于处理从链表头部开始反转的特殊情况
2. 找到 left 的前驱节点 prev 和要反转的第一个节点 curr
3. 遍历从 left 到 right 的链表部分，逐个将当前节点插入到子链表的头部
4. 返回链表的新头节点

• Python
• Javascript

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy

        # 1. 找到 left 的前驱节点（prev）和 left 节点（curr）
        for _ in range(left - 1):
            prev = prev.next
        curr = prev.next

        # 2. 反转 [left, right] 之间的节点
        for _ in range(right - left):
            tmp = curr.next # 暂存当前节点的 next
            curr.next = tmp.next # 当前节点指向 next 的 next
            tmp.next = prev.next # 插入到子链表头部
            prev.next = tmp # 更新 prev 的 next

        return dummy.next

class Solution {
    reverseBetween(head, left, right) {
        const dummy = new ListNode(0);
        dummy.next = head;
        let prev = dummy;

        // 1. 找到 left 的前驱节点（prev）和 left 节点（curr）
        for (let i = 1; i < left; i++)
            prev = prev.next;
        curr = prev.next;

        // 2. 反转 [left, right] 之间的节点
        for (let i = 0; i < right - left; i++) {
            let tmp = curr.next;
            curr.next = tmp.next;
            tmp.next = prev.next;
            prev.next = tmp;
        }

        return dummy.next;
    }
}

---

合成链表

Leetcode 21. Merge Two Sorted Lists

• 题目: 给定两个单链表list1和list2，它们的元素按升序排列。将它们合并为一个新的链表，要求新链表也按照升序排列，并返回新链表的头节点

Input: list1 = [1,2,4], list2 = [1,3,5]
Output: [1,1,2,3,4,5]

• 解法: 虚拟头节点法

1. 使用一个虚拟头节点 dummy 来简化链表连接逻辑
2. 遍历 list1 和 list2，逐步比较它们的节点值，将较小的节点连接到结果链表中
3. 当一个链表遍历完成后，将另一个链表剩余的节点直接连接到结果链表

• Python
• Javascript

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        curr = dummy

        # 遍历两个链表，比较节点值
        while list1 and list2:
            if list1.val < list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            curr = curr.next

        # 连接剩余的节点
        curr.next = list1 or list2
        return dummy.next

class Solution {
    mergeTwoLists(list1, list2) {
        const dummy = new ListNode(0);
        let curr = dummt;

        // 遍历两个链表，比较节点值
        while (list1 !== null && list2 !== null) {
            if (list1.val < list2.val) {
                curr.next = list1;
                list1 = list1.next;
            } else {
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }

        // 连接剩余的节点
        curr.next = list1 !== null ? list1 : list2;
        return dummy.next;
    }
}

---

k个一组翻转链表

Leetcode 25. Reverse Nodes in k-Group

• 题目: 给定一个单链表的头节点head和一个整数k，将链表按照每k个节点为一组进行翻转。如果剩余节点不足 k个，则保持原样。要求返回翻转后的链表

Input: head = [1,2,3,4,5,6], k = 3
Output: [3,2,1,6,5,4]

• 解法: 按组翻转 + 双指针

1. 遍历链表并按 k 个节点为一组分割
2. 对每组节点执行翻转操作
3. 翻转后的部分与链表的其他部分正确连接

• Python
• Javascript

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        group_prev = dummy

        while True:
            # 找到当前组的第 k 个节点
            kth = self.getKthNode(group_prev, k)
            if not kth:
                break
            group_next = kth.next

            # 反转当前组的节点
            prev, curr = group_next, group_prev.next
            while curr != group_next:
                tmp = curr.next
                curr.next = prev
                prev = curr
                curr = tmp

            # 处理连接：将反转后的部分与链表其余部分连接起来
            tmp = group_prev.next
            group_prev.next = kth
            group_prev = tmp

        return dummy.next

    def getKthNode(self, curr, k) -> Optional[ListNode]:
        while curr and k > 0:
            curr = curr.next
            k -= 1
        return curr

class Solution {
    reverseKGroup(head, k) {
        const dummy = new ListNode(0);
        dummy.next = head;
        let groupPrev = dummy;

        while (true) {
            // 找到当前组的第 k 个节点
            const kth = this.getKthNode(groupPrev, k);
            if (!kth) break;
            const groupNext = kth.next;

            // 反转当前组的节点
            let prev = groupNext;
            let curr = groupPrev.next;
            while (curr !== groupNext) {
                const tmp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = tmp;
            }

            // 处理连接
            const tmp = groupPrev.next;
            groupPrev.next = kth;
            groupPrev = tmp;
        }

        return dummy.next;
    }

    getKthNode(curr, k) {
        while (curr && k > 0) {
            curr = curr.next;
            k--;
        }
        return curr;
    }
}

---

成对反转链表节点

Leetcode 24. Swap Nodes in Pairs

• 题目: 给定一个单链表的头节点head，将链表中的节点两两交换，并返回交换后的链表。如果链表节点数是奇数，最后一个节点保持不变

Input: head = [1,2,3,4]
Output: [2,1,4,3]

• 解法: 虚拟头节点法

1. 使用一个虚拟头节点 dummy，便于操作头节点及其后的节点
2. 每次取出两个相邻节点，将它们交换
3. 正确调整指针以保持链表的顺序

• Python
• Javascript

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy

        while head and head.next:
            # 要交换的两个节点
            first = head
            second = head.next

            # 交换节点
            prev.next = second
            first.next = second.next
            second.next = first

            # 移动指针准备下一组交换
            prev = first
            head = first.next

        return dummy.next

class Solution {
    swapPairs(head) {
        const dummy = ListNode(0);
        dummy.next = head;
        let prev = dummy;

        while (head && head.next) {
            // 要交换的两个节点
            const first = head;
            const second = head.next;

            // 交换节点
            prev.next = second;
            first.next = second.next;
            second.next = first;

            // 移动指针准备下一组交换
            prev = first;
            head = first.next;
        }

        return dummy.next;
    }
}

---

对折链表

Leetcode 143. Reorder List

• 题目: 给定一个单链表head，要求在原地修改链表，不使用额外的空间, 将其重新排序为
  • 原链表的第一个节点 -> 最后一个节点 -> 第二个节点 -> 倒数第二个节点 ->

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

• 解法: 快慢指针 + 反转链表 + 合并链表

1. 找到链表中点
   - 使用快慢指针，快指针每次移动两步，慢指针每次移动一步，当快指针到达末尾时，慢指针指向中点
2. 反转链表后半部分
   - 将链表从中点分成两部分，反转后半部分链表
3. 合并链表
   - 按顺序交替连接前半部分和反转后的后半部分链表

• Python
• Javascript

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # 1. 使用快慢指针找到链表中点
        slow = head
        fast = head.next

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. 反转链表的后半部分
        second = slow.next
        prev = None
        slow.next = None # 切断前半部分和后半部分链表的连接

        while second:
            tmp = second.next
            second.next = prev
            prev = second
            second = tmp

        # 3. 合并链表
        first, second = head, prev # first 是前半部分的链表头，second 是反转后的后半部分链表头
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first, second = tmp1, tmp2

class Solution {
    reorderList(head) {
        if (!head || !head.next) return;

        // 1. 使用快慢指针找到链表中点
        let slow = head, fast = head.next;
        while (fast && fast.next) {
            slow = slow.next;
            fast = fast.next;
        }

        // 2. 反转链表的后半部分
        let second = slow.next;
        slow.next = null;
        let prev = null;
        while (second) {
            let tmp = second.next;
            second.next = prev;
            prev = second;
            second = tmp;
        }

        // 3. 合并链表
        let first = head;
        second = prev;
        while (second) {
            let tmp1 = first.next, tmp2 = second.next;
            first.next = second;
            second.next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }
}

---

删除有序链表重复元素

Leetcode 83. Remove Duplicates from Sorted List

• 题目: 从一个升序排列的链表中，删除所有重复的节点，确保每个值只出现一次

Input: head = [1,1,2,3,3]
Output: [1,2,3]

• 解法: 遍历链表

1. 从链表头开始，依次检查当前节点和下一个节点的值
2. 如果当前节点值和下一个节点值相同，则跳过下一个节点
3. 如果值不同，则移动指针到下一个节点
4. 重复上述过程，直到遍历完整个链表

• Python
• Javascript

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = head

        while curr and curr.next:
            if curr.val == curr.next.val: # 如果当前值等于下一个值
                curr.next = curr.next.next # 跳过下一个节点
            else:
                curr = curr.next
        
        return head

class Solution {
    deleteDuplicates(head) {
        let curr = head;

        while (curr && curr.next) {
            if (curr.val === curr.next.val)
                curr.next = curr.next.next; // 跳过下一个节点
            else
                curr = curr.next;
        }

        return head;
    }
}

---

删除有序链表所有重复元素

Leetcode 82. Remove Duplicates from Sorted List II

• 题目: 从一个升序排列的链表中，删除所有出现次数超过1次的节点，仅保留没有重复的节点

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

• 解法: 双指针 + 虚拟头节点

1. 创建虚拟头节点 dummy，以处理可能需要删除头节点的情况
2. 定义两个指针：
    - prev：指向最后一个不重复的节点
    - curr：用于遍历链表
3. 遍历链表：
    - 如果 curr 和 curr.next 的值相同，跳过所有重复的节点
    - 如果没有重复，移动 prev 指针到当前节点
4. 返回虚拟头节点的下一个节点

• Python
• Javascript

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy
        curr = head

        while curr:
            # 如果当前节点的值与下一个节点的值相同
            if curr.next and curr.val == curr.next.val:
                # 跳过所有值相同的节点
                while curr.next and curr.val == curr.next.val:
                    curr = curr.next
                # 将 prev 的 next 指向下一个不重复的节点
                prev.next = curr.next
            else:
                # 如果没有重复，移动 prev 指针
                prev = prev.next

            # 移动 curr 指针
            curr = curr.next

        return dummy.next

class Solution {
    deleteDuplicates(head) {
        const dummy = new ListNode(0, head);
        let prev = dummy;
        let curr = head;

        while (curr) {
            // 如果当前节点的值与下一个节点的值相同
            if (curr.next && curr.val === curr.next.val) {
                // 跳过所有值相同的节点
                while (curr.next && curr.val === curr.next.val)
                    curr = curr.next;
            }
            // 将 prev 的 next 指向下一个不重复的节点
            prev.next = curr.next;
        } else {
            // 如果没有重复，移动 prev 指针
            prev = prev.next;
        }

        // 移动 curr 指针
        curr = curr.next;
    }

    return dummy.next;
}

---

链表转树

Leetcode 109. Convert Sorted List to Binary Search Tree

• 题目: 将一个有序链表转换为高度平衡的二叉搜索树（BST）。高度平衡指的是树中每个节点的两个子树的高度差不超过1

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]

• 解法: 分治法 + 快慢指针

1. 使用快慢指针找到链表的中间节点，将其作为当前树的根节点
2. 对中间节点之前的链表递归构建左子树
3. 对中间节点之后的链表递归构建右子树
4. 当链表为空时，返回 None

• Python
• Javascript

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        # 辅助函数：找到链表的中间节点
        def find_middle(start, end):
            slow = fast = start
            while fast != end and fast.next != end:
                slow = slow.next
                fast = fast.next.next
            return slow
        
        # 主函数：递归构建二叉搜索树
        def build_bst(start, end):
            if start == end:
                return None
            
            mid = find_middle(start, end)
            root = TreeNode(mid.val)

            # 构建左右子树
            root.left = build_bst(start, mid)
            root.right = build_bst(mid.next, end)

            return root
        
        return build_bst(head, None)

class Solution {
    sortedListToBST(head) {
        // 辅助函数：找到链表的中间节点
        function findMiddle(start, end) {
            let slow = start;
            let fast = start;
            while (fast !== end && fast.next !== end) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }

        // 主函数：递归构建二叉搜索树
        function buildBST(start, end) {
            if (start === end) return null;

            const mid = findMiddle(start, end);
            const root = new TreeNode(mid.val);

            // 构建左右子树
            root.left = buildBST(start, mid);
            root.right = buildBST(mid.next, end);

            return root;
        }

        return buildBST(head, null);
    }
}

---

合并k个有序链表

Leetcode 23. Merge k Sorted Lists

• 题目: 给定k个有序链表，将它们合并成一个有序链表并返

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

• 解法: 最小堆（优先队列）

1. 将每个链表的头节点加入最小堆
2. 每次从堆中取出最小值节点，将其加入结果链表
3. 如果该节点有下一个节点，将下一个节点加入堆中
4. 重复以上过程直到堆为空

• Python
• Javascript

import heapq

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        min_heap = []

        # 将每个链表的头节点放入堆中
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(min_heap, (lists[i].val, i, lists[i]))

        dummy = ListNode(0)
        curr = dummy

        # 不断从堆中取出最小节点，并将其后续节点继续放入堆中
        while min_heap:
            val, idx, node = heapq.heappop(min_heap)
            curr.next = node
            curr = curr.next
            if node.next:
                heapq.heappush(min_heap, (node.next.val, idx, node.next))

        return dummy.next

class Solution {
    mergeKLists(lists) {
        const minHeap = new MinPriorityQueue({ priority: (node) => node.val });

        // 将每个链表的头节点加入堆中
        for (let i = 0; i < lists.length; i++) {
            if (lists[i])
                minHeap.enqueue(lists[i]);
        }

        const dummy = new ListNode(0);
        let curr = dummy;

        // 从堆中取出最小节点，构建合并链表
        while (!minHeap.isEmpty()) {
            const smallestNode = minHeap.dequeue().element; // 取出最小值节点
            curr.next = smallestNode;
            curr = curr.next;

            if (smallestNode.next)
                minHeap.enqueue(smallestNode.next); // 将下一个节点加入堆
        }

        return dummy.next;
    }
}

---

BFS & DFS

海岛问题

Leetcode 200. Number of Islands

• 题目: 给定一个由'1'和'0'组成的网格，'1'表示陆地，'0'表示水域，计算网格中岛屿的数量。岛屿被水域包围，由相邻的陆地（水平或垂直方向）连接而成

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

• 解法1: 广度优先搜索 (BFS)

1. 遍历网格中的每个位置，找到未访问的陆地节点作为起点
2. 从起点开始，使用 BFS 遍历整个岛屿，将所有相连的陆地标记为已访问
3. 每发现一个新岛屿时，岛屿计数器加一
4. 返回最终的岛屿数量

• Python
• Javascript

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        island = 0
        visited = set() # 记录已访问节点
        rows, cols = len(grid), len(grid[0])

        def bfs(r, c):
            q = deque()
            q.append((r, c))
            visited.add((r, c))

            while q:
                row, col = q.popleft()
                for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                    nr, nc = dr + row, dc + col
                    if (
                        0 <= nr < rows and
                        0 <= nc < cols and
                        grid[nr][nc] == "1" and
                        (nr, nc) not in visited
                    ):
                        q.append((nr, nc))
                        visited.add((nr, nc))

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r, c) not in visited:
                    island += 1
                    bfs(r, c)
        
        return island

class Solution {
    numIslands(grid) {
        const rows = grid.length;
        const cols = grid[0].length;
        const visited = new Set();
        let island = 0;

        const bfs = (r, c) => {
            const queue = [];
            queue.push([r, c]);
            visited.add(`${r},${c}`);

            while (queue.length > 0) {
                const [row, col] = queue.shift();
                
                for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
                    const nr = dr + row;
                    const nc = dc + col;

                    if (nr >= 0 &&
                        nc >= 0 &&
                        nr < rows &&
                        nc < cols &&
                        grid[nr][nc] === "1" &&
                        !visited.has(`${nr},${nc}`)
                    ) {
                        queue.push([nr, nc]);
                        visited.add(`${nr},${nc}`);
                    }
                }
            }
        }

        for (let r = 0; r < rows; r++) {
            for (let c = 0; c < cols; c++) {
                if (grid[r][c] === "1" && !visited.has(`${r},${c}`)) {
                    island += 1;
                    bfs(r, c);
                }
            }
        }

        return island;
    }
}

• 解法2: 深度优先搜索 (DFS)

1. 使用递归替代 BFS 的队列逻辑
2. 遍历网格，遇到未访问的陆地时，启动 DFS 遍历整个岛屿
3. 每发现一个新岛屿时，岛屿计数器加一
4. 返回岛屿数量

• Python
• Javascript

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        island = 0
        rows, cols = len(grid), len(grid[0])

        def dfs(r, c):
            if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == "0":
                return
            grid[r][c] = "0" # 标记为已访问
            # 遍历四个方向
            for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                dfs(r + dr, c + dc)


        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1":
                    island += 1
                    dfs(r, c)

        return island

class Solution {
    numIslands(grid) {
        const rows = grid.length;
        const cols = grid[0].length;
        let island = 0;

        const dfs = (r, c) => {
            // 如果超出边界或遇到水域，则停止递归
            if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === "0")
                return;

            grid[r][c] = 0; // 标记为已访问
            for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]])
                dfs(r + dr, c + dc);
        }

        for (let r = 0; r < rows; r++) {
            for (let c = 0; c < cols; c++) {
                if (grid[r][c] === "1") {
                    island += 1;
                    dfs(r, c);
                }
            }
        }

        return island;
    }
}

---

Two Pointers 双指针

雨水问题

Leetcode 42. Trapping Rain Water

• 题目: 给定一个非负整数数组height，表示每个柱子的高度。假设下雨后水只会停留在柱子之间，请计算可以接住的总雨水量

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

• 解法: 双指针

1. 使用两个指针分别从数组的左右两端向中间靠拢
2. 在遍历过程中，记录左右两侧的最大高度
3. 计算当前柱子上方的雨水量：
    - 雨水量 = 较低一侧的最大高度 - 当前柱子高度
4. 移动较低一侧的指针，同时更新对应的最大高度
5. 遍历结束时，累加所有雨水量并返回结果

• Python
• Javascript

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        
        left, right = 0, len(height) - 1
        # 初始化左右两边的最大高度
        left_max, right_max = height[left], height[right]
        result = 0

        while left < right:
            # 如果左边的最大高度小于右边的最大高度
            if left_max < right_max:
                left += 1
                # 更新左边的最大高度
                left_max = max(left_max, height[left])
                # 计算当前左指针位置的接水量（左边的最大高度 - 当前柱子的高度）
                result += left_max - height[left]
            else:
                right -= 1
                # 更新右边的最大高度
                right_max = max(right_max, height[right])
                # 计算当前右指针位置的接水量（右边的最大高度 - 当前柱子的高度）
                result += right_max - height[right]
        return result

class Solution {
    trap(height) {
        let left = 0, right = height.length - 1;
        let leftMax = height[left], rightMax = height[right];
        let result = 0;

        while (left < right) {
            if (leftMax < rightMax) {
                left++;
                leftMax = Math.max(leftMax, height[left]); // 更新左边最大高度
                result += leftMax - height[left]; // 计算左侧接水量
            } else {
                right--;
                rightMax = Math.max(rightMax, height[right]); // 更新右边最大高度
                result += rightMax - height[right]; // 计算右侧接水量
            }
        }

        return result;
    }
}

---

盛水问题

Leetcode 11. Container With Most Water

• 题目: 给定一个数组height，其中每个元素表示一个竖线的高度，竖线在横轴上的间隔为1。找到两根竖线之间形成的容器能够盛水的最大面积

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

• 解法: 双指针

1. 初始化左右指针，分别指向数组的两端
2. 每次计算由左右指针对应的竖线形成的容器面积，更新最大面积
3. 移动较短竖线的一侧指针，尝试找到更大的容器
4. 重复上述步骤，直到左右指针相遇

• Python
• Javascript

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        result = 0

        while left < right:
            # 计算当前容器的面积
            width = right - left
            area = min(height[left], height[right]) * width
            # 更新最大面积
            result = max(result, area)

            # 移动较短边对应的指针，尝试找到更大的容器
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return result

class Solution {
    maxArea(height) {
        let left = 0, right = height.length - 1;
        let maxArea = 0;

        while (left < right) {
            // 计算当前容器的面积
            const width = right - left;
            const area = Math.min(height[left], height[right]) * width;

            // 更新最大面积
            maxArea = Math.max(maxArea, area);

            // 移动较短边对应的指针
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        
        return maxArea;
    }
}

---

一维数组去重

Leetcode 26. Remove Duplicates from Sorted Array

• 题目: 有序数组nums，需要原地移除重复项，使每个元素最多出现一次

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

• 解法: 双指针

1. 定义 i 指针跟踪去重后数组的最后一个位置
2. 使用 j 指针遍历数组，寻找不重复的元素
3. 遇到新元素时，将其放在 i+1 位置，并更新 i
4. 返回去重后数组的长度 i+1

• Python
• Javascript

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0

        i = 0 # 跟踪去重后数组的最后一个位置
        for j in range(1, len(nums)):
            if nums[j] != nums[i]: # 如果发现新的元素
                i += 1
                nums[i] = nums[j] # 将 nums[j] 移动到去重后的数组中

        return i + 1

class Solution {
    removeDuplicates(nums) {
        if (nums.length === 0) return 0;

        let i = 0;
        for (let j = 1; j < nums.length; j++) {
            if (nums[j] !== nums[i]) { // 遇到新元素
                i++;
                nums[i] = nums[j]; // 更新数组
            }
        }

        return i + 1;
    }
}

---

最接近的三数之和

Leetcode 16. 3Sum Closest

• 题目: 给定一个长度为n的整数数组nums和一个目标值target，找到数组中三个数的和，使其最接近目标值。返回这个和

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2)

• 解法: 排序 + 双指针

1. 首先对数组进行排序
2. 遍历数组，固定一个数 nums[i]，用双指针从 i+1 和数组末尾出发寻找最接近的三数之和
3. 如果当前三数之和比记录的更接近目标值，更新结果
4. 根据当前和与目标值的大小关系移动左右指针
5. 返回最接近的三数之和

• Python
• Javascript

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort() # 排序
        result = float("inf") # 初始化最接近的结果

        for i in range(len(nums) - 2):
            left, right = i + 1, len(nums) - 1

            while left < right:
                curr_sum = nums[i] + nums[left] + nums[right]

                # 更新最接近的结果
                if abs(curr_sum - target) < abs(result - target):
                    result = curr_sum

                # 根据当前和与目标值的关系调整指针
                if curr_sum < target:
                    left += 1
                elif curr_sum > target:
                    right -= 1
                else:
                    return curr_sum # 当前和等于目标值时直接返回

        return result

class Solution {
    threeSumClosest(nums, target) {
        nums.sort((a, b) => a - b); // 排序
        let result = Infinity; // 初始化最接近的结果

        for (let i = 0; i < nums.length - 2; i++) {
            let left = i + 1, right = nums.length - 1;

            while (left < right) {
                let currSum = nums[i] + nums[left] + nums[right];

                // 更新最接近的结果
                if (Math.abs(currSum - target) < Math.abs(result - target))
                    result = currSum;

                // 根据当前和与目标值的关系调整指针
                if (currSum < target)
                    left++;
                else if (currSum > target)
                    right--;
                else
                    return currSum; // 当前和等于目标值时直接返回
            }
        }

        return result;
    }
}

---

三数之和

Leetcode 15. 3Sum

• 题目: 给定一个包含整数的数组nums，返回所有不重复的三元组[nums[i], nums[j], nums[k]]，使得nums[i] + nums[j] + nums[k] == 0。答案中不能包含重复的三元组

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation: 
nums[0] + nums[1] + nums[3] = -1 + -1 + 2 = 0
nums[0] + nums[2] + nums[4] = -1 + 0 + 1 = 0

• 解法: 排序 + 双指针

1. 对数组进行排序，便于去重和使用双指针
2. 遍历数组，固定一个数 nums[i]，然后用双指针从 i+1 和数组末尾出发，寻找和为 -nums[i] 的另外两个数
3. 如果找到和为 0 的三元组，将其加入结果集中，同时移动指针跳过重复值
4. 如果当前和小于 0，左指针右移；如果当前和大于 0，右指针左移
5. 遍历结束返回结果

• Python
• Javascript

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort() # 对数组进行排序，方便后续去重和双指针处理
        result = []

        for i in range(len(nums) - 2):
            # 如果当前数和前一个数相同，跳过，避免重复三元组
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, len(nums) - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right] # 计算当前三数之和

                if total == 0:
                    result.append([nums[i], nums[left], nums[right]])

                    # 跳过重复的左指针和右指针值
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1

                    # 移动指针
                    left += 1
                    right -= 1
                elif total < 0: # 如果当前和小于 0，增加左指针
                    left += 1
                else: # 如果当前和大于 0，减少右指针
                    right -= 1 
        
        return result

class Solution {
    threeSum(nums) {
        nums.sort((a, b) => a - b); // 对数组进行排序
        const result = [];

        for (let i = 0; i < nums.length - 2; i++) {
            // 如果当前数和前一个数相同，跳过，避免重复三元组
            if (i > 0 && nums[i] === nums[i - 1]) continue;

            let left = i + 1, right = nums.length - 1;

            while (left < right) {
                const total = nums[i] + nums[left] + nums[right];

                if (total === 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 (total < 0) {
                    left++; // 如果当前和小于 0，增加左指针
                } else {
                    right--;  如果当前和大于 0，减少右指针
                }
            }
        }

        return result;
    }
}

---

四数之和

Leetcode 18. 4Sum

• 题目: 给定一个由整数数组nums和一个目标值target，找出所有不重复的四元组[nums[a], nums[b], nums[c], nums[d]]，使得nums[a] + nums[b] + nums[c] + nums[d] == target

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Explanation: The solution sets are unique and order does not matter

• 解法: 排序 + 双指针 + 多层遍历

1. 对数组进行排序，以便后续去重和使用双指针
2. 先固定两个数 nums[i] 和 nums[j]，然后使用双指针寻找剩下两个数，使得四数之和等于 target
3. 遍历过程中跳过重复的数值，避免结果中出现重复的四元组
4. 返回所有符合条件的四元组

• Python
• Javascript

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort() # 排序
        result = []
        
        for i in range(len(nums) - 3):
            # 跳过重复的第一个数
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, len(nums) - 2):
                # 跳过重复的第二个数
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                
                left, right = j + 1, len(nums) - 1
                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]

                    if total == target:
                        result.append([nums[i], nums[j], nums[left], nums[right]])

                        # 跳过重复的左指针和右指针值
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1
                        
                        # 移动指针
                        left += 1
                        right -= 1
                    elif total < target:
                        left += 1
                    else:
                        right -= 1

        return result

class Solution {
    fourSum(nums, target) {
        nums.sort((a, b) => a - b); // 排序
        const result = [];

        for (let i = 0; i < nums.length - 3; i++) {
            // 跳过重复的第一个数
            if (i > 0 && nums[i] === nums[i - 1]) continue;

            for (let j = i + 1; j < nums.length - 2; j++) {
                // 跳过重复的第二个数
                if (j > i + 1 && nums[j] === nums[j - 1]) continue;

                let left = j + 1, right = nums.length - 1;
                while (left < right) {
                    const total = nums[i] + nums[j] + nums[left] + nums[right];

                    if (total === target) {
                        result.push([nums[i], nums[j], 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 (total < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }

        return result;
    }
}

---

找出数组中的重复数字

Leetcode 287. Find the Duplicate Number

• 题目: 给定一个包含n + 1个整数的数组 nums，其中每个整数都在范围 [1, n] 内，且只有一个重复的数字。找出该重复的数字。注意：不能修改数组内容，并且仅使用常数级别的额外空间

Input: nums = [3,1,3,4,2]
Output: 3

• 解法: 快慢指针（Floyd判圈算法）

1. 将数组看作链表，nums[i] 指向下一个节点
2. 使用快慢指针找到环的位置：慢指针一次走一步，快指针一次走两步
3. 在环中找到入口，也就是重复的数字

• Python
• Javascript

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # 使用快慢指针
        slow, fast = nums[0], nums[nums[0]]

        # 阶段 1：找到快慢指针相遇点
        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]

        # 阶段 2：找到环的入口，即重复的数字
        slow = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]

        return slow

class Solution {
    findDuplicate(nums) {
        let slow = nums[0], fast = nums[nums[0]];

        // 阶段 1：找到快慢指针相遇点
        while (slow !== fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        // 阶段 2：找到环的入口，即重复的数字
        slow = 0;
        while (slow !== fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
}

---

Binary Search

最长递增子序列

Leetcode 300. Longest Increasing Subsequence

• 题目: 给定一个整数数组nums，找到其中最长严格递增子序列的长度

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4

• 解法: 动态规划 + 二分法优化

1. 动态规划：
   定义 dp[i] 表示以 nums[i] 为结尾的最长递增子序列的长度
   状态转移方程：dp[i] = max(dp[i], dp[j] + 1) for all j < i and nums[j] < nums[i]
   时间复杂度为 O(n^2)

2. 二分法优化：
   维护一个数组 tails，其中 tails[i] 表示长度为 i+1 的递增子序列的末尾最小值
   对每个 nums 中的元素使用二分法更新 tails
   时间复杂度为 O(n log n)

• Python
• Javascript

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 用于存储不同长度递增子序列的最小末尾值
        tails = []

        for num in nums:
            # 二分查找，寻找第一个大于等于 num 的位置
            left, right = 0, len(tails)
            while left < right:
                mid = (left + right) // 2
                if tails[mid] < num:
                    left = mid + 1
                else:
                    right = mid

            # 如果 left 等于 tails 长度，说明 num 是一个新的最大值
            if left == len(tails):
                tails.append(num)
            else:
                tails[left] = num
        
        return len(tails)

class Solution {
    lengthOfLIS(nums) {
        const tails = [];

        for (let num of nums) {
            // 找到第一个大于等于 num 的位置
            let left = 0, right = tails.length;
            while (left < right) {
                const mid = Math.floor((left + right) / 2);
                if (tails[mid] < num)
                    left = mid + 1;
                else
                    right = mid;
            }

            if (left === tails.length)
                // 如果 num 比 tails 中的所有值都大，直接添加到末尾
                tails.push(num);
            else
                // 否则替换位置 left 的值，保持更小的末尾
                tails[left] = num;
        }

        return tails.length;
    }
}

---

Tree 树与二叉树

二叉树层序遍历

• 实现二叉树的层序遍历（广度优先遍历，BFS）
• 从二叉树的根节点开始，按层级顺序逐层访问节点，每层从左到右

    3  
   / \
  9   20
     /  \
    15   7

输出: 
[
    [3],
    [9, 20],
    [15, 7]
]

• 解法: 队列实现BFS

1. 使用 deque 实现队列，初始包含根节点
2. 遍历每一层：
    - 记录当前层的节点数量（level_size）
    - 弹出队首节点，存储值到当前层结果
    - 将左右子节点加入队列
3. 每层遍历结束后，将当前层结果加入最终结果
4. 队列为空时，遍历完成

• Python
• Javascript

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def levelOrder(self, root: TreeNode) -> list[list[int]]:
        result = []
        if not root:
            return result

        queue = deque([root]) # 初始化队列，包含根节点

        while queue:
            level_size = len(queue) # 当前层的节点数
            current_level = [] # 用于存储当前层的节点值

            for _ in range(level_size):
                node = queue.popleft() # 弹出队首节点
                current_level.append(node.val) # 添加节点值到当前层

                # 将左右子节点加入队列
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            result.append(current_level) # 将当前层加入结果

        return result       

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    levelOrder(root) {
        const result = [];
        if (!root) return result;

        const queue = [root]; // 初始化队列，包含根节点

        while (queue.length > 0) {
            const levelSize = queue.length; // 当前层的节点数
            const currentLevel = []; // 用于存储当前层的节点值
            
            for (let i = 0; i < levelSize; i++) {
                const node = queue.shift(); // 弹出队首节点
                currentLevel.push(node.val); // 添加节点值到当前层

                // 将左右子节点加入队列
                if (node.left) queue.push(node.left);
                if (node.right) queue.push(node.right);
            }

            result.push(currentLevel);
        }

        return result;
    }
}

---

树每层的最大值

Leetcode 515. Find Largest Value in Each Tree Row

• 题目: 给定一个二叉树，按层遍历树，返回每一行中的最大值

      1
     / \
    3   2
   / \    \
  5   3    9

Output: [1,3,9]

• 解法: 广度优先搜索BFS

1. 使用队列（deque）进行层序遍历（BFS）
2. 遍历每一层时，找出该层节点值的最大值
3. 将每层的最大值添加到结果列表中

• Python
• Javascript

from collections import deque

class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        result = []
        queue = deque([root])

        while queue:
            level_size = len(queue)
            max_val = float("-inf") # 初始化每层最大值

            for _ in range(level_size):
                node = queue.popleft() # 弹出当前层的节点
                max_val = max(max_val, node.val) # 更新最大值
                if node.left:
                    queue.append(node.left) # 加入左子节点
                if node.right:
                    queue.append(node.right) # 加入右子节点
            
            result.append(max_val) # 保存每层最大值

        return result

class Solution {
    largestValues(root) {
        if (!root) return [];

        const result = [];
        const queue = [root];

        while (queue.length > 0) {
            const levelSize = queue.length;
            let maxVal = -Infinity; // 初始化每层最大值

            for (let i = 0; i < levelSize; i++) {
                const node = queue.shift(); // 弹出当前层的节点
                maxVal = Math.max(maxVal, node.val); // 更新最大值
                if (node.left) queue.push(node.left); // 加入左子节点
                if (node.right) queue.push(node.right); // 加入右子节点
            }

            result.push(maxVal); // 保存每层最大值
        }

        return result;
    }
}

---

验证二叉搜索树

Leetcode 98. Validate Binary Search Tree

• 题目: 验证一棵二叉树是否为二叉搜索树（BST）

二叉搜索树的性质:
1. 节点的左子树只包含比当前节点值小的节点
2. 节点的右子树只包含比当前节点值大的节点
3. 左右子树也必须是二叉搜索树

Input: root = [2,1,3]
Output: true

• 解法: 递归验证上下界

1. 使用递归检查每个节点的值是否满足二叉搜索树的性质:
   节点的值应在一个范围内 `(low, high)`
2. 初始范围是 `(-inf, inf)`
3. 左子树的值范围: `(low, node.val)`
   右子树的值范围: `(node.val, high)`
4. 递归检查子树是否满足条件

• Python
• Javascript

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # 递归函数，检查节点是否在 (low, high) 范围内
        def validate(node, low, high):
            if not node: # 空节点是合法的
                return True
            # 当前节点值必须在范围内
            if not (low < node.val < high):
                return False
            return validate(node.left, low, node.val) and validate(node.right, node.val, high)
        
        # 初始范围为 (-inf, inf)
        return validate(root, float("-inf"), float("inf"))

class Solution {
    isValidBST(root) {
        function validate(node, low, high) {
            if (!node) return true; // 空节点合法
            if (node.val <= low || node.val >= high) return false; // 不在范围内
            // 检查左右子树
            return validate(node.left, low, node.val) && validate(node.right, node.val, high);
        }

        // 初始范围 (-Infinity, Infinity)
        return validate(root, -Infinity, Infinity);
    }
}

---

二叉树最大差值

Leetcode 1026. Maximum Difference Between Node and Ancestor

• 题目: 找到二叉树中任意节点与其祖先节点值之间的最大差值
  • 祖先节点: 从根节点到当前节点路径上的任意节点

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7

差值最大的一对节点是: 8 和 1，差值为 7

• 解法: 深度优先搜索（DFS）

1. 使用递归（DFS）遍历二叉树
2. 在递归过程中维护当前路径上的最小值和最大值
3. 每到一个节点
    - 更新路径的最小值和最大值
    - 计算当前节点值与路径最小值或最大值的差值
4. 遍历整棵树，返回最大差值

• Python
• Javascript

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        def maxDiff(node, curr_min, curr_max):
            if not node: # 如果节点为空，返回当前差值
                return curr_max - curr_min

            # 更新当前路径的最小值和最大值
            curr_min = min(curr_min, node.val)
            curr_max = max(curr_max, node.val)

            # 递归左子树和右子树，计算最大差值
            left_diff = maxDiff(node.left, curr_min, curr_max)
            right_diff = maxDiff(node.right, curr_min, curr_max)

            # 返回左右子树中差值的最大值
            return max(left_diff, right_diff)

        # 从根节点开始，初始最小值和最大值为根节点的值
        return maxDiff(root, root.val, root.val)

class Solution {
    maxAncestorDiff(root) {
        function maxDiff(node, currMin, currMax) {
            if (!node) return currMax - currMin; // 返回当前差值

            // 更新路径中的最小值和最大值
            currMin = Math.min(currMin, node.val);
            currMax = Math.max(currMax, node.val);

            // 递归左右子树，计算最大差值
            const leftDiff = maxDiff(node.left, currMin, currMax);
            const rightDiff = maxDiff(node.right, currMin, currMax);

            // 返回左右子树中差值的最大值
            return Math.max(leftDiff, rightDiff);
        }

        // 初始最小值和最大值为根节点的值
        return maxDiff(root, root.val, root.val);
    }
}

---

不同二叉搜索树的数量

Leetcode 96. Unique Binary Search Trees

• 题目: 给定一个整数n，表示从1到n的节点，计算可以形成的不同二叉搜索树（BST）的数量

Input: n = 3
Output: 5

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

• 解法: 动态规划 (卡特兰数公式)

1. 定义 G[i] 表示由 i 个节点可以构成的不同二叉搜索树的数量
2. 初始条件
    - G[0] = 1（空树有 1 种情况）
    - G[1] = 1（只有一个节点也只有 1 种情况）
3. 递推公式
    - G[i] = Σ G[j-1] * G[i-j]
    - 即选择第 j 个节点为根时
        - 左子树有 j-1 个节点，数量为 G[j-1]
        - 右子树有 i-j 个节点，数量为 G[i-j]
    - 对所有可能的根节点 j 求和

• Python
• Javascript

class Solution:
    def numTrees(self, n: int) -> int:
        # G[i] 表示 i 个节点的不同二叉搜索树数量
        G = [0] * (n + 1)

        # 初始条件
        G[0] = 1
        G[1] = 1

        # 动态规划计算 G[2] 到 G[n]
        for i in range(2, n + 1):
            for j in range(1, i + 1):
                G[i] += G[j - 1] * G[i - j]

        return G[n]

class Solution {
    numTrees(n) {
        const G = new Array(n + 1).fill(0);

        // 初始条件
        G[0] = 1;
        G[1] = 1;

        // 动态规划计算 G[2] 到 G[n]
        for (let i = 2; i <= n; i++) {
            for (let j = 1; j <= i; j++) {
                G[i] += G[j - 1] * G[i - j];
            }
        }

        return G[n];
    }
}

---

检查二叉树是否平衡

Leetcode 110. Balanced Binary Tree

• 题目: 给定一个二叉树，判断它是否是高度平衡的
  • 平衡二叉树的定义是: 二叉树的任意节点的左右子树高度差不超过1

Input: root = [3,9,20,null,null,15,7]
Output: true

• 解法: 深度优先搜索 (DFS)

1. 使用递归函数 dfs(node)
   - 如果节点为空，返回平衡状态 True 和高度 0
   - 递归检查左右子树，计算它们的平衡状态和高度
2. 当前节点是否平衡
   - 左右子树都平衡
   - 左右子树高度差不超过 1
3. 返回当前节点的平衡状态和高度
4. 检查根节点的平衡状态

• Python
• Javascript

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(node):
            if not node:
                return True, 0 # [是否平衡, 高度]
            
            left_balanced, left_height = dfs(node.left)
            right_balanced, right_height = dfs(node.right)

            balanced = left_balanced and right_balanced and abs(left_height - right_height) <= 1

            height = max(left_height, right_height) + 1

            return balanced, height

        return dfs(root)[0]

class Solution {
    isBalanced(root) {
        function dfs(node) {
            if (!node) return [true, 0]; // [是否平衡, 高度]
            
            const [leftBalanced, leftHeight] = dfs(node.left);
            const [rightBalanced, rightHeight] = dfs(node.right);

            const balanced = leftBalanced && rightBalanced && Math.abs(leftHeight - rightHeight) <= 1;

            const height = Math.max(leftHeight, rightHeight) + 1;

            return [balanced, height];
        }

        return dfs(root)[0];
    }
}

---

二叉搜索树第k小的节点

Leetcode 230. Kth Smallest Element in a BST

• 题目: 给定一棵二叉搜索树的根节点root，以及一个整数k，请返回该二叉搜索树中第k小的节点值

Input: root = [3,1,4,null,2], k = 1
Output: 1

• 解法: 中序遍历 (In-order Traversal)

1. 中序遍历二叉搜索树，按升序访问节点值
2. 计数每访问一个节点，当计数等于 k 时，返回该节点值
3. 使用递归实现中序遍历

• Python
• Javascript

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        count = 0 # 计数器
        result = None # 结果存储

        def inorder(node):
            nonlocal count, result
            if not node:
                return

            # 遍历左子树
            inorder(node.left)

            # 处理当前节点
            count += 1
            if count == k:
                result = node.val
                return 
            
            # 遍历右子树
            inorder(node.right)

        inorder(root)
        return result

class Solution {
    kthSmallest(root, k) {
        let count = 0; // 计数器
        let result = null; // 结果存储

        function inorder(node) {
            if (!node) return;

            // 遍历左子树
            inorder(node.left);

            // 处理当前节点
            count += 1;
            if (count === k) {
                result = node.val;
                return;
            }

            // 遍历右子树
            inorder(node.right);
        }

        inorder(root);
        return result;
    }
}

---

二叉树展开为链表

Leetcode 114. Flatten Binary Tree to Linked List

• 题目: 将二叉树展开为链表，要求“就地”修改树的结构，使其变为一个单链表形式，顺序与前序遍历一致

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

• 解法: 递归

1. 递归处理左子树和右子树，将它们分别扁平化
2. 保存右子树，并将左子树移到右子树的位置，将左子树置为 None
3. 找到左子树的最右节点，将保存的右子树接到这个节点上

• Python
• Javascript

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        if not root:
            return

        # 递归处理左子树和右子树
        self.flatten(root.left)
        self.flatten(root.right)

        # 保存右子树
        right_subtree = root.right

        # 将左子树移动到右子树的位置
        root.right = root.left
        root.left = None

        # 找到左子树的最右节点
        curr = root
        while curr.right:
            curr = curr.right

        # 将保存的右子树接到最右节点
        curr.right = right_subtree

class Solution {
    flatten(root) {
        if (!root) return;

        // 递归处理左子树和右子树
        this.flatten(root.left);
        this.flatten(root.right);

        // 保存右子树
        const rightSubtree = root.right;

        // 将左子树移动到右子树的位置
        root.right = root.left;
        root.left = null;
        
        // 找到左子树的最右节点
        let curr = root;
        while (curr.right)
            curr = curr.right;
        
        // 将保存的右子树接到最右节点
        curr.right = rightSubtree;
    }
}

---

二叉搜索树的最近公共祖先

Leetcode 235. Lowest Common Ancestor of a Binary Search Tree

• 题目: 在一个二叉搜索树（BST）中，给定两个节点p和q，找到它们的最近公共祖先（LCA）

Input: root = [5,3,8,1,4,7,9,null,2], p = 3, q = 8
Output: 5
Explanation: 节点 5 是节点 3 和 8 的最近公共祖先

• 解法: 利用二叉搜索树的性质

1. 从根节点开始遍历
2. 如果 p 和 q 的值都小于当前节点值，则往左子树继续查找
3. 如果 p 和 q 的值都大于当前节点值，则往右子树继续查找
4. 如果 p 和 q 的值分别位于当前节点的两侧，或者当前节点值等于其中一个节点值，则当前节点为最近公共祖先

• Python
• Javascript

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            if root.val > p.val and root.val > q.val:
                root = root.left # p 和 q 都在左子树
            elif root.val < p.val and root.val < q.val:
                root = root.right # p 和 q 都在右子树
            else:
                return root # 当前节点是最近公共祖先

class Solution {
    lowestCommonAncestor(root, p, q) {
        while (root) {
            if (root.val > p.val && root.val > q.val)
                root = root.left; // p 和 q 都在左子树
            else if (root.val < p.val && root.val < q.val)
                root = root.right; // p 和 q 都在右子树
            else
                return root; // 当前节点是最近公共祖先
        }
    }
}

---

对称二叉树

Leetcode 101. Symmetric Tree

• 题目: 判断给定的二叉树是否是对称的。如果一棵树的左子树和右子树是镜像对称的，则这棵树是对称

Input: root = [1,2,2,3,4,4,3]
Output: true

• 解法: 递归

1. 如果树为空，返回 True
2. 定义一个辅助函数 isMirror，判断两个节点是否对称
   - 如果两个节点都为空，返回 True
   - 如果只有一个节点为空，返回 False
   - 判断两个节点的值是否相等，并递归判断它们的左右子节点是否对称
3. 调用 isMirror(root.left, root.right)

• Python
• Javascript

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def isMirror(t1, t2):
            if not t1 and not t2:
                return True
            if not t1 or not t2:
                return False
            return t1.val == t2.val and isMirror(t1.right, t2.left) and isMirror(t1.left, t2.right)

        return isMirror(root, root)

class Solution {
    isSymmetric(root) {
        function isMirror(t1, t2) {
            if (!t1 && !t2) return true;
            if (!t1 || !t2) return false;

            return t1.val === t2.val && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right);
        }

        return isMirror(root, root);
    }
}

---

存在路径总和

Leetcode 112. Path Sum

• 题目: 给定一个二叉树和一个目标和，判断树中是否存在从根节点到叶子节点的路径，使得路径上的所有节点值相加等于目标和

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The path 5 → 4 → 11 → 2 has a sum of 22

• 解法: 深度优先搜索

1. 从根节点出发，递归地检查左右子树
2. 在每次递归中，将目标值减去当前节点的值
3. 当到达叶子节点时，检查剩余目标值是否为 0
4. 如果找到一条路径符合条件，则返回 True；否则继续搜索

• Python
• Javascript

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        
        # 减去当前节点值
        targetSum -= root.val

        # 检查是否是叶子节点并且目标值为
        if not root.left and not root.right:
            return targetSum == 0
        
        # 递归检查左右子树
        return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)

class Solution {
    hasPathSum(root, targetSum) {
        if (!root) return false;

        // 减去当前节点值
        targetSum -= root.val;

        // 检查是否是叶子节点并且目标值为0
        if (!root.left && !root.right)
            return targetSum === 0;

        // 递归检查左右子树
        return this.hasPathSum(root.left, targetSum) || this.hasPathSum(root.right, targetSum);
    }
}

---

所有路径总和

Leetcode 113. Path Sum II

• 题目: 给定一个二叉树和一个目标和，返回所有从根节点到叶子节点的路径，使得路径上的节点值之和等于目标和

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: The paths are:
5 → 4 → 11 → 2
5 → 8 → 4 → 5

• 解法: 深度优先搜索 + 回溯

1. 使用递归深度优先搜索（DFS）遍历二叉树
2. 在路径上记录当前节点值，减去当前节点值更新目标和
3. 当到达叶子节点且目标和为 0 时，将当前路径加入结果
4. 回溯时移除当前节点值，返回上一层递归继续搜索

• Python
• Javascript

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        result = []

        def dfs(node, current_path, remaining_sum):
            if not node:
                return
            
            # 添加当前节点值到路径
            current_path.append(node.val)
            remaining_sum -= node.val

            # 如果是叶子节点且目标和为0，保存路径
            if not node.left and not node.right and remaining_sum == 0:
                result.append(list(current_path))
            
            # 递归遍历左右子树
            dfs(node.left, current_path, remaining_sum)
            dfs(node.right, current_path, remaining_sum)

            # 回溯
            current_path.pop()
        
        dfs(root, [], targetSum)
        return result

class Solution {
    pathSum(root, targetSum) {
        const result = [];

        function dfs(node, currentPath, remainingSum) {
            if (!node) return;

            // 添加当前节点值到路径
            currentPath.push(node.val);
            remainingSum -= node.val;

            // 如果是叶子节点且目标和为0，保存路径
            if (!node.left && !node.right && remainingSum === 0)
                result.push([...currentPath]);
            
            // 递归遍历左右子树
            dfs(node.left, currentPath, remainingSum);
            dfs(node.right, currentPath, remainingSum);

            // 回溯
            currentPath.pop();
        }

        dfs(root, [], targetSum);
        return result;
    }
}

---

Matrix 矩阵

螺旋矩阵

Leetcode 54. Spiral Matrix

• 题目: 按照螺旋顺序输出矩阵中的所有元素

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

• 解法: 逐层遍历

1. 初始化矩阵的边界
    - 上边界 top，初始为 0
    - 下边界 bottom，初始为矩阵的行数 - 1
    - 左边界 left，初始为 0
    - 右边界 right，初始为矩阵的列数 - 1
2. 按照螺旋顺序
    - 从左到右遍历最上面一行
    - 从上到下遍历最右边一列
    - 从右到左遍历最下面一行（如果还有剩余行）
    - 从下到上遍历最左边一列（如果还有剩余列）
3. 每遍历一层后缩小边界，直到遍历完整个矩阵

• Python
• Javascript

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1
        result = []

        while top <= bottom and left <= right:
            # 从左到右遍历最上面一行
            for i in range(left, right + 1):
                result.append(matrix[top][i])
            top += 1  # 上边界向下移动

            # 从上到下遍历最右边一列
            for i in range(top, bottom + 1):
                result.append(matrix[i][right])
            right -= 1  # 右边界向左移动

            if top <= bottom:
                # 从右到左遍历最下面一行
                for i in range(right, left - 1, -1):
                    result.append(matrix[bottom][i])
                bottom -= 1  # 下边界向上移动

            if left <= right:
                # 从下到上遍历最左边一列
                for i in range(bottom, top - 1, -1):
                    result.append(matrix[i][left])
                left += 1  # 左边界向右移动

        return result

class Solution {
    spiralOrder(matrix) {
        let top = 0, bottom = matrix.length - 1;
        let left = 0, right = matrix[0].length - 1;
        let result = [];

        while ((top <= bottom) && (left <= right)) {
            // 从左到右遍历最上面一行
            for (let i = left; i < right + 1; i++)
                result.push(matrix[top][i]);
            top += 1; // 上边界向下移动

            // 从上到下遍历最右边一列
            for (let j = top; j < bottom + 1; j++)
                result.push(matrix[j][right]);
            right -= 1; // 右边界向左移动

            if (top <= bottom) {
                // 从右到左遍历最下面一行
                for (let i = right; i > left - 1; i--)
                    result.push(matrix[bottom][i]);
                bottom -= 1; // 下边界向上移动
            }

            if (left <= right) {
                // 从下到上遍历最左边一列
                for (let j = bottom; j > top - 1; j--)
                    result.push(matrix[j][left]);
                left += 1; // 左边界向右移动
            }
        }

        return result;
    }
}

---

有效数独

Leetcode 36. Valid Sudoku

• 题目: 给定一个9x9的数独棋盘，验证该棋盘是否有效
  • 每行数字不能重复
  • 每列数字不能重复
  • 每个3x3方块中的数字不能重复

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

• 解法: 哈希表

1. 使用三个哈希表分别记录
    - 每行中已出现的数字
    - 每列中已出现的数字
    - 每个 3x3 方块中已出现的数字
2. 遍历整个棋盘
    - 如果遇到 .，跳过
    - 检查数字是否已存在于当前行、列或对应的 3x3 方块中
    - 如果存在，返回 False
    - 如果不存在，添加到相应的哈希表中
3. 遍历结束后，若未发现冲突，返回 True

• Python
• Javascript

class Solution:
    def isValidSudoku(board: List[List[str]]) -> bool:
        # 哈希表记录每行、每列和每个 3x3 方块的数字
        rows = collections.defaultdict(set)
        cols = collections.defaultdict(set)
        squares = collections.defaultdict(set) # 键为 (r//3, c//3)

        for r in range(9):
            for c in range(9):
                num = board[r][c]
                if num == ".":
                    continue

                # 检查当前数字是否已存在
                if num in rows[r] or num in cols[c] or num in squares[(r // 3, c // 3)]:
                    return False

                # 添加数字到对应哈希表
                rows[r].add(num)
                cols[c].add(num)
                squares[((r // 3, c // 3))].add(num)

        return True

class Solution {
    isValidSudoku(board) {
        const rows = new Array(9).fill(0).map(() => new Set());
        const cols = new Array(9).fill(0).map(() => new Set());
        const squares = new Array(9).fill(0).map(() => new Set());

        for (let r = 0; r < 9; r++) {
            for (let c = 0; c < 9; c++) {
                const num = board[r][c];
                if (num === ".") continue;

                const squareIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3);

                if (rows[r].has(num) || cols[c].has(num) || squares[squareIndex].has(num))
                    return false;

                rows[r].add(num);
                cols[c].add(num);
                squares[squareIndex].add(num);
            }
        }

        return true;
    }
}

---

最大岛屿面积

Leetcode 695. Max Area of Island

• 题目: 给定一个二维网格grid，其中0表示水域，1表示陆地，计算网格中最大的岛屿面积。岛屿由上下左右四个方向相连的陆地组成

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],
               [0,0,0,0,0,0,0,1,1,1,0,0,0],
               [0,1,1,0,1,0,0,0,0,0,0,0,0],
               [0,1,0,0,1,1,0,0,1,0,1,0,0],
               [0,1,0,0,1,1,0,0,1,1,1,0,0],
               [0,0,0,0,0,0,0,0,0,0,1,0,0],
               [0,0,0,0,0,0,0,1,1,1,0,0,0],
               [0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6

• 解法: 深度优先搜索（DFS）

1. 遍历整个网格
2. 遇到 1 时，启动 DFS 计算连通岛屿的面积
3. 将访问过的格子标记为 0，防止重复访问
4. 更新最大岛屿面积

• Python
• Javascript

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # 定义 DFS 函数，遍历岛屿
        def dfs(i, j):
            # 如果超出边界或当前位置不是岛屿，返回 0
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:
                return 0

            grid[i][j] = 0 # 标记为已访问
            # 递归地访问上下左右
            return 1 + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i, j - 1)

        max_area = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    max_area = max(max_area, dfs(i, j)) # 如果找到岛屿，启动 DFS

        return max_area

class Solution {
    maxAreaOfIsland(grid) {
        function dfs(i, j) {
            // 如果超出边界或当前位置不是岛屿，返回 0
            if (i < 0 || i >= grid.lenght || j < 0 || j >= grid[0].length || grid[i][j] === 0) 
                return 0;
            grid[i][j] = 0; // 标记为已访问
            // 递归地访问上下左右
            return 1 + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i, j - 1);
        }

        let maxArea = 0;
        for (let i = 0; i < grid.length; i++) {
            for (let j = 0; j < grid[0].length; j++) {
                if (grid[i][j] === 1)
                    maxArea = Math.max(maxArea, dfs(i, j));
            }
        }
        return maxArea;
    }
}

---

Array 数组

轮转数组

Leetcode 189. Rotate Array

• 题目: 给定一个数组，将其元素向右轮转k位，其中k是非负数

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]

• 解法: 翻转法

1. 翻转整个数组
2. 翻转前 k 个元素
3. 翻转剩余的元素

• Python
• Javascript

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n # 处理 k 大于数组长度的情况

        # 翻转数组的辅助函数
        def reverse(start, end):
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1

        # 1. 翻转整个数组
        reverse(0, n - 1)
        # 2. 翻转前 k 个元素
        reverse(0, k - 1)
        # 3. 翻转剩下的元素
        reverse(k, n - 1)

class Solution {
    rotate(nums, k) {
        const n = nums.length;
        k %= n; // 处理 k 大于数组长度的情况

        function reverse(start, end) {
            while (start < end) {
                [nums[start], nums[end]] = [nums[end], nums[start]];
                start++;
                end--;
            }
        }

        // 1. 翻转整个数组
        reverse(0, n - 1);
        // 2. 翻转前 k 个元素
        reverse(0, k - 1);
        // 3. 翻转剩下的元素
        reverse(k, n - 1);
    }
}

---

数组转树

Leetcode 108. Convert Sorted Array to Binary Search Tree

• 题目: 将一个有序数组转换为一棵高度平衡的二叉搜索树（BST）。高度平衡指的是树中每个节点的两个子树的高度差不超过1

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]

• 解法: 递归构建

1. 选择数组的中间元素作为当前子树的根节点。
2. 左侧子数组递归构建左子树。
3. 右侧子数组递归构建右子树。
4. 当数组为空时，返回 None。

• Python
• Javascript

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        # 如果数组为空，返回 None
        if not nums:
            return None

        # 找到中间元素并创建当前根节点
        mid = len(nums) // 2
        root = TreeNode(nums[mid])

        # 构建左子树和右子树
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid + 1:])

        return root

class Solution {
    sortedArrayToBST(nums) {
        // 如果数组为空，返回 null
        if (nums.length === 0) return null;

        // 找到中间元素并创建当前根节点
        const mid = Math.floor(nums.length / 2);
        const root = new TreeNode(nums[mid]);

        // 构建左子树和右子树
        root.left = this.sortedArrayToBST(nums.slice(0, mid));
        root.right = this.sortedArrayToBST(nums.slice(mid + 1));

        return root;
    }
}

---

合并两个有序数组

Leetcode 88. Merge Sorted Array

• 题目: 将两个有序数组nums1和nums2合并为一个有序数组，其中nums1有足够的空间存放nums2的元素

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

• 解法: 双指针从后往前合并

1. 设置三个指针
   - i 指向 nums1 的有效元素部分的末尾
   - j 指向 nums2 的末尾
   - k 指向 nums1 的末尾
2. 比较 nums1 和 nums2 中的元素，将较大的元素填入 nums1 的末尾，指针向前移动
3. 如果 nums2 还有剩余的元素，直接填入 nums1

• Python
• Javascript

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # 指针 i 指向 nums1 的有效部分末尾，j 指向 nums2 末尾，k 指向 nums1 的总末尾
        i, j, k = m - 1, n - 1, m + n - 1

        # 从后往前合并
        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1
        
        # 如果 nums2 还有剩余元素，填入 nums1
        while j >= 0:
            nums1[k] = nums2[j]
            j -= 1
            k -= 1

class Solution {
    merge(nums1, m, nums2, n) {
        // 指针 i 指向 nums1 的有效部分末尾，j 指向 nums2 末尾，k 指向 nums1 的总末尾
        let i = m - 1, j = n - 1, k = m + n - 1;

        // 从后往前合并
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }

        // 如果 nums2 还有剩余元素，填入 nums1
        while (j >= 0) {
            nums1[k] = nums2[j];
            j--;
            k--;
        }
    }
}

---

每日温度

Leetcode 739. Daily Temperatures

• 题目: 给定一个整数数组temperatures，表示每天的温度，返回一个数组answer，其中answer[i]是需要等待的天数，直到temperatures[i]之后出现更高的温度。如果没有更高的温度，answer[i] = 0

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

• 解法: 单调栈

1. 使用栈存储温度的索引
2. 遍历 temperatures：
   - 如果当前温度高于栈顶索引对应的温度，弹出栈顶索引并计算等待天数
   - 否则，将当前索引压入栈
3. 最后栈中未处理的索引对应的等待天数为 0
4. 时间复杂度 O(n)

• Python
• Javascript

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # 初始化结果数组和栈
        result = [0] * len(temperatures)
        stack = []

        # 遍历温度数组
        for i, temp in enumerate(temperatures):
            # 如果当前温度比栈顶的温度高
            while stack and temp > temperatures[stack[-1]]:
                prev_index = stack.pop()
                result[prev_index] = i - prev_index
            # 将当前索引压入栈
            stack.append(i)

        return result

class Solution {
    dailyTemperatures(temperatures) {
        const result = new Array(temperatures.length).fill(0);
        const stack = [];

        // 遍历温度数组
        for (let i = 0; i < temperatures.length; i++) {
            // 如果当前温度比栈顶的温度高
            while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
                const prevIndex = stack.pop();
                result[prevIndex] = i - prevIndex;
            }
            // 将当前索引压入栈
            stack.push(i);
        }

        return result;
    }
}

---

String 字符串

字符串解码

Leetcode 394. Decode String

• 题目: 给定一个编码过的字符串s，其中包含嵌套的数字和括号结构，例如3[a2[c]]，其解码规则为
  • 数字表示括号内字符串的重复次数
  • 解码后输出完整的字符串

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

• 解法: 栈

1. 使用栈保存当前的字符串和重复次数
2. 遇到 [ 将当前字符串和次数入栈，清空当前的数字和字符串
3. 遇到 ] 将栈中的字符串与当前字符串组合，并重复指定次数
4. 遇到数字时，累积数字值
5. 遇到普通字符时，将其追加到当前字符串
6. 最后，栈中保存的即为解码后的结果

• Python
• Javascript

class Solution:
    def decodeString(self, s: str) -> str:
        stack = [] # 栈，用于保存 (当前字符串, 当前数字)
        curr_num = 0 # 当前的重复次数
        curr_str = "" # 当前正在构建的字符串

        for c in s:
            if c.isdigit():
                # 构建数字
                curr_num = curr_num * 10 + int(c)
            elif c == "[":
                # 遇到左括号，将当前字符串和数字入栈
                stack.append((curr_str, curr_num))
                curr_str = ""
                curr_num = 0
            elif c == "]":
                # 遇到右括号，出栈并构造新字符串
                prev_str, num = stack.pop()
                curr_str = prev_str + num * curr_str
            else:
                # 字母追加到当前字符串
                curr_str += c

        return curr_str

class Solution {
    decodeString(s) {
        const stack = [];
        let currNum = 0;
        let currStr = "";

        for (const c of s) {
            if (!isNaN(c)) {
                // 构建数字
                currNum = currNum * 10 + parseInt(c);
            } else if (c === "[") {
                // 遇到左括号，将当前字符串和数字入栈
                stack.push([currStr, currNum]);
                currStr = "";
                currNum = 0;
            } else if (c === "]") {
                // 遇到右括号，出栈并构造新字符串
                const [prevStr, num] = stack.pop();
                currStr = prevStr + currStr.repeat(num);
            } else {
                // 字母追加到当前字符串
                currStr += c;
            }
        }

        return currStr;
    }
}

---

最长无重复子串

Leetcode 3. Longest Substring Without Repeating Characters

• 题目: 给定一个字符串s，找出其中不含重复字符的最长子串的长度

Input: s = "abcabcbb"
Output: 3

• 解法: 滑动窗口

1. 使用两个指针 `left` 和 `right` 维护一个滑动窗口，窗口内的字符不重复
2. 用一个 `set` 存储当前窗口内的字符
3. 每次移动右指针，将字符尝试加入窗口：
   - 如果字符已存在，移动左指针，直到窗口中无重复字符
4. 更新当前窗口的最大长度

• Python
• Javascript

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = 0
        left = 0
        char_set = set()

        for right in range(len(s)):
            # 如果字符重复，移动左指针直到窗口无重复字符
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1

            # 将当前字符加入窗口
            char_set.add(s[right])
            # 更新最大长度
            result = max(result, right - left + 1)

        return result

class Solution {
    lengthOfLongestSubstring(s) {
        let result = 0;
        let left = 0;
        let charSet = new Set();

        for (let right = 0; right < s.length; right++) {
            // 如果字符重复，移动左指针直到窗口无重复字符
            while (charSet.has(s[right])) {
                charSet.delete(s[left]);
                left++;
            }

            // 将当前字符加入窗口
            charSet.add(s[right]);
            // 更新最大长度
            result = Math.max(result, right - left + 1);
        }

        return result;
    }
}

---

括号匹配

Leetcode 20. Valid Parentheses

• 题目: 验证一个只包含括号的字符串是否有效
  • 所有的左括号必须有对应的右括号
  • 左括号必须以正确的顺序闭合

Input: s = "()[]{}"
Output: true

• 解法: 栈

1. 用一个栈来保存左括号
2. 遍历字符串
    - 遇到左括号，就压入栈
    - 遇到右括号，检查栈顶是否是对应的左括号
        - 如果匹配，弹出栈顶
        - 如果不匹配或栈为空，返回 False
3. 遍历结束后，如果栈为空，说明括号有效

• Python
• Javascript

class Solution:
    def isValid(self, s: str) -> bool:
        # 定义右括号到左括号的映射
        char_map = {")": "(", "]": "[", "}": "{"}
        stack = []

        for c in s:
            # 如果是左括号，压入栈中
            if c not in char_map:
                stack.append(c)
                continue

            # 如果栈为空或者栈顶元素不匹配，返回 False
            if not stack or stack[-1] != char_map[c]:
                return False
            
            # 匹配成功，弹出栈顶
            stack.pop()
        
        return not stack

class Solution {
    isValid(s) {
        const charMap = { ")": "(", "]": "[", "}": "{" };
        const stack = [];

        for (const c of s) {
            // 如果是左括号，压入栈中
            if (!(c in charMap)) {
                stack.push(c);
                continue;
            }

            // 如果栈为空或者栈顶元素不匹配，返回 false
            if (!stack.length || stack[stack.length - 1] !== charMap[c])
                return false;

            // 匹配成功，弹出栈顶
            stack.pop();
        }

        return stack.length === 0;
    }
}

---

生成括号

Leetcode 22. Generate Parentheses

• 题目: 给定一个数字n，生成所有可能的有效括号组合
  • 左括号数量等于右括号数量，并且任意位置右括号的数量不超过左括号

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

• 解法: 回溯法

1. 使用递归来生成括号组合
2. 每次递归时，维护当前括号字符串 s 和左右括号的数量
    - 如果左括号的数量小于 n，可以添加左括号
    - 如果右括号的数量小于左括号，添加右括号
3. 当字符串长度等于 2 * n 时，添加到结果中

• Python
• Javascript

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []

        def backtrack(s, left, right):
            # 如果长度达到 2 * n，记录结果
            if len(s) == 2 * n:
                result.append(s)
                return

            # 添加左括号
            if left < n:
                backtrack(s + "(", left + 1, right)
            
            # 添加右括号
            if right < left:
                backtrack(s + ")", left, right + 1)
        
        backtrack("", 0, 0)
        return result

class Solution {
    generateParenthesis(n) {
        const result = [];

        function backtrack(s, left, right) {
            // 如果长度达到 2 * n，记录结果
            if (s.length === 2 * n) {
                result.push(s);
                return;
            }

            // 添加左括号
            if (left < n) backtrack(s + "(", left + 1, right);
            
            // 添加右括号
            if (right < left) backtrack(s + ")", left, right + 1);
        }

        backtrack("", 0, 0);
        return result;
    }
}

---

比较版本号

Leetcode 165. Compare Version Numbers

• 题目: 给定两个版本号version1和version2，比较它们的大小
  • 如果version1 > version2返回1
  • 如果version1 < version2返回-1
  • 如果它们相等，返回0

Input: version1 = "1.2", version2 = "1.10"
Output: -1

• 解法: 分割和补齐

1. 使用点号分割版本号，将其转换为整数列表
2. 找到两个版本号的最大长度，将较短的版本号用 0 补齐
3. 从左到右逐个比较对应的版本号部分，返回结果
4. 如果遍历结束后仍然没有结果，则两个版本号相等

• Python
• Javascript

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        # 将版本号分割为整数列表
        v1_parts = list(map(int, version1.split(".")))
        v2_parts = list(map(int, version2.split(".")))

        # 用 0 补齐较短的版本号部分
        max_len = max(len(v1_parts), len(v2_parts))
        v1_parts += [0] * (max_len - len(v1_parts))
        v2_parts += [0] * (max_len - len(v2_parts))

        # 比较每一部分
        for i in range(max_len):
            if v1_parts[i] > v2_parts[i]:
                return 1
            elif v1_parts[i] < v2_parts[1]:
                return -1

        # 如果遍历结束仍未分出大小，则版本号相等
        return 0

class Solution {
    compareVersion(version1, version2) {
        // 将版本号分割为整数数组
        const v1Parts = version1.split(".").map(Number);
        const v2Parts = version2.split(".").map(Number);

        // 用 0 补齐较短的版本号部分
        const maxLen = Math.max(v1Parts.length, v2Parts.length);
        while (v1Parts.length < maxLen) v1Parts.push(0);
        while (v2Parts.length < maxLen) v2Parts.push(0);

        // 比较每一部分
        for (let i = 0; i < maxLen; i++) {
            if (v1Parts[i] > v2Parts[i]) return 1;
            if (v1Parts[i] < v2Parts[i]) return -1;
        }

        // 如果遍历结束仍未分出大小，则版本号相等
        return 0;
    }
}

---

经典计算器 (无乘除)

Leetcode 224. Basic Calculator

• 题目: 实现一个基本的计算器来计算由正整数、+、-和括号组成的数学表达式的值。表达式中可能包含空格，确保输入合法且结果不会溢出

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

• 解法: 栈 + 模拟

1. 定义一个栈，用于存储运算结果和符号
2. 遍历字符串:
   - 如果是数字，累加当前数字
   - 如果是 `+` 或 `-`，更新当前的符号，并将累加的数字加到结果中
   - 如果是 `(`，将当前结果和符号压栈，并重置结果和符号
   - 如果是 `)`，将栈顶的结果和符号弹出，并与当前结果相加
3. 返回最终计算结果

• Python
• Javascript

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        result = 0
        sign = 1 # 初始符号为正号

        for char in s:
            if char.isdigit():
                # 如果是数字，更新当前数字
                num = num * 10 + int(char)
            elif char in "+-":
                # 如果是加号或减号，先更新当前结果
                result += sign * num
                num = 0
                sign = 1 if char == "+" else -1
            elif char == "(":
                # 如果是左括号，保存当前结果和符号到栈中
                stack.append(result)
                stack.append(sign)
                result = 0
                sign = 1
            elif char == ")":
                # 如果是右括号，计算括号内的结果
                result += sign * num
                num = 0
                result *= stack.pop() # 弹出符号并应用
                result += stack.pop() # 加上之前的结果
            
        return result + sign * num

class Solution {
    calculate(s) {
        const stack = [];
        let num = 0, result = 0, sign = 1;

        for (const char of s) {
            if (!isNaN(char) && char !== " ") {
                // 如果是数字，更新当前数字
                num = num * 10 + parseInt(char);
            } else if (char === "+" || char === "-") {
                // 如果是加号或减号，先更新当前结果
                result += sign * num;
                num = 0;
                sign = char === "+" ? 1 : -1;
            } else if (char === "(") {
                // 如果是左括号，保存当前结果和符号到栈中
                stack.push(result);
                stack.push(sign);
                result = 0;
                sign = 1;
            } else if (char === ")") {
                // 如果是右括号，计算括号内的结果
                result += sign * num;
                num = 0;
                result *= stack.pop(); // 弹出符号并应用
                result += stack.pop(); // 加上之前的结果
            }
        }

        return result + sign * num;
    }
}

---

经典计算器 (有乘除)

Leetcode 227. Basic Calculator II

• 题目: 实现一个基本的计算器来计算一个字符串表达式的值。表达式仅包含非负整数、+、-、*、/运算符以及空格

Input: s = "3+2*2"
Output: 7
Explanation: 3 + (2 * 2) = 7

• 解法: 栈 + 模拟

1. 使用栈来保存当前的计算结果
2. 遍历字符串，处理数字、操作符和空格
   - 如果是数字，累加构成完整数字
   - 如果是操作符或到达字符串末尾，根据前一个操作符执行计算
     - `+`：将当前数字压入栈
     - `-`：将当前数字取反后压入栈
     - `*`：弹出栈顶数字，与当前数字相乘后压入栈
     - `/`：弹出栈顶数字，执行整数除法后压入栈
3. 遍历结束后，栈中的所有元素求和即为最终结果

• Python
• Javascript

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        op = '+' # 初始操作符为 '+'

        for i, c in enumerate(s):
            if c.isdigit():
                num = num * 10 + int(c) # 累加数字
            if c in "+-*/" or i == len(s) - 1: # 遇到操作符或字符串末尾
                if op == '+':
                    stack.append(num)
                elif op == '-':
                    stack.append(-num)
                elif op == '*':
                    stack.append(stack.pop() * num)
                elif op == '/':
                    stack.append(int(stack.pop() / num))
                op = c # 更新操作符
                num = 0 # 重置当前数字

        return sum(stack)

class Solution {
    calculate(s) {
        const stack = [];
        let num = 0;
        let op = '+'; // 初始操作符为 '+'

        for (let i = 0; i < s.length; i++) {
            const c = s[i];
            if (!isNaN(c) && c !== ' ') num = num * 10 + parseInt(c); // 累加数字

            if ("+-*/".includes(c) || i === s.length - 1) {
                if (op === '+') stack.push(num);
                else if (op === '-') stack.push(-num);
                else if (op === '*') stack.push(stack.pop() * num);
                else if (op === '/') stack.push(Math.trunc(stack.pop() / num));

                op = c; // 更新操作符
                num = 0;
            }
        }

        return stack.reduce((acc, num) => acc + num, 0);
    }
}

---

回文子串个数

Leetcode 647. Palindromic Substrings

• 题目: 给定一个字符串s，计算其中包含多少个回文子串

Input: s = "abc"
Output: 3
Explanation: Three palindromic substrings are "a", "b", and "c"

Input: s = "aaa"
Output: 6
Explanation: Six palindromic substrings are "a", "a", "a", "aa", "aa", and "aaa"

• 解法: 中心扩展法

1. 中心扩展法
   - 每个字符可以作为奇数长度回文的中心
   - 每对相邻字符可以作为偶数长度回文的中心
   - 从中心向两边扩展，判断两边字符是否相等，同时统计回文子串的数量

• Python
• Javascript

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0

        def expand_around_center(left, right):
            nonlocal count
            while left >= 0 and right < n and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1

        for i in range(n):
            # 奇数长度的回文
            expand_around_center(i, i)
            # 偶数长度的回文
            expand_around_center(i, i + 1)

        return count

class Solution {
    countSubstrings(s) {
        const n = s.length;
        let count = 0;

        function expandAroundCenter(left, right) {
            while (left >= 0 && right < n && s[left] === s[right]) {
                count++;
                left--;
                right++;
            }
        }

        for (let i = 0; i < n; i++) {
            // 奇数长度的回文
            expandAroundCenter(i, i);
            // 偶数长度的回文
            expandAroundCenter(i, i + 1);
        }

        return count;
    }
}

---

最长回文子串

Leetcode 5. Longest Palindromic Substring

• 题目: 给定一个字符串s，找到其中最长的回文子串

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer

• 解法: 中心扩展法

1. 回文的中心可以是一个字符，也可以是两个字符之间的间隔
2. 遍历字符串，每个字符和每两个字符之间都作为回文中心进行扩展
3. 在扩展过程中，更新最长的回文子串的起始位置和长度
4. 时间复杂度 O(n^2)

• Python
• Javascript

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand_around_center(left, right):
            # 从中心扩展，寻找最长回文
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left + 1:right]

        longest = ""
        for i in range(len(s)):
            # 奇数长度回文
            odd_palindrome = expand_around_center(i, i)
            # 偶数长度回文
            even_palindrome = expand_around_center(i, i + 1)
            # 更新最长回文子串
            longest = max(longest, odd_palindrome, even_palindrome, key=len)

        return longest

class Solution {
    longestPalindrome(s) {
        function expandAroundCenter(left, right) {
            // 从中心扩展，寻找最长回文
            while (left >= 0 && right < s.length && s[left] === s[right]) {
                left--;
                right++;
            }
            return s.substring(left + 1, right);
        }

        let longest = "";
        for (let i = 0; i < s.length; i++) {
            // 奇数长度回文
            const oddPalindrome = expandAroundCenter(i, i);
            // 偶数长度回文
            const evenPalindrome = expandAroundCenter(i, i + 1);
            // 更新最长回文子串
            if (oddPalindrome.length > longest.length) longest = oddPalindrome;
            if (evenPalindrome.length > longest.length) longest = evenPalindrome;
        }

        return longest;
    }
}

---

大数相加

Leetcode 415. Add Strings

• 题目: 给定两个非负整数num1和num2，以字符串的形式表示，返回它们的和，结果也用字符串表示。不能直接使用大整数库或将输入直接转换为整数

Input: num1 = "11", num2 = "123"
Output: "134"

• 解法: 模拟逐位相加

1. 从字符串末尾开始，逐位相加，记录进位
2. 如果一个字符串较短，用零补齐
3. 将每位的计算结果插入到最终结果的前面
4. 如果最终还有进位，追加到结果
5. 返回拼接的结果字符串

• Python
• Javascript

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        # 初始化指针和变量
        i, j = len(num1) - 1, len(num2) - 1
        carry = 0
        result = []

        # 从右向左逐位相加
        while i >= 0 or j >= 0 or carry:
            n1 = int(num1[i]) if i >= 0 else 0
            n2 = int(num2[j]) if j >= 0 else 0
            total = n1 + n2 + carry

            carry  = total // 10 # 计算进位
            result.append(str(total % 10))

            i -= 1
            j -= 1
        
        return ''.join(result[::-1]) # 翻转并拼接结果

class Solution {
    addStrings(num1, num2) {
        let i = num1.length - 1;
        let j = num2.length - 1;
        let carry = 0;
        let result = [];

        // 从右向左逐位相加
        while (i >= 0 || j >= 0 || carry) {
            const n1 = i >= 0 ? parseInt(num1[i]) : 0;
            const n2 = j >= 0 ? parseInt(num2[j]) : 0;
            const total = n1 + n2 + carry;

            carry = Math.floor(total / 10); // 计算进位
            result.push(total % 10);

            i--;
            j--;
        }

        return result.reverse().join(''); // 翻转并拼接结果
    }
}

---

Backtrack 回溯

全排列（无重复元素）

Leetcode 46. Permutations

• 题目: 给定一个不包含重复的数组nums，返回数组的所有可能的排列，不包含重复

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

• 解法: 回溯算法

1. 初始化一个空路径 path 和一个 used 数组用于标记是否使用过某元素
2. 遍历数组，对未使用的元素进行选择，加入路径
3. 如果路径长度等于数组长度，将当前路径加入结果
4. 撤销选择，尝试其他未使用的元素

• Python
• Javascript

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []

        def backtrack(path, used):
            # 如果路径长度等于数组长度，加入结果
            if len(path) == len(nums):
                result.append(path[:]) # 深拷贝当前路径
                return

            for i in range(len(nums)):
                if used[i]:
                    continue

                # 做选择
                path.append(nums[i])
                used[i] = True

                # 递归
                backtrack(path, used)

                # 撤销选择
                path.pop()
                used[i] = False

        backtrack([], [False] * len(nums))
        return result

class Solution {
    permute(nums) {
        const result = [];

        function backtrack(path, used) {
            // 如果路径长度等于数组长度，加入结果
            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(path, used);

                // 撤销选择
                path.pop();
                used[i] = false;
            }
        }

        backtrack([], Array(nums.length).fill(false));
        return result;
    }
}

---

全排列（有重复元素）

Leetcode 47. Permutations II

• 题目: 给定一个可能包含重复数字的数组nums，返回数组的所有不重复的排列

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

• 解法: 回溯算法 + 去重

1. 对 nums 排序，使得相同的数字相邻，方便去重
2. 在回溯过程中，跳过当前数字与前一个数字相同且前一个数字未被使用的情况
3. 构建排列路径，记录已使用数字
4. 撤销选择，尝试其他未使用的数字

• Python
• Javascript

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort() # 排序以便去重

        def backtrack(path, used):
            # 如果路径长度等于数组长度，加入结果
            if len(path) == len(nums):
                result.append(path[:])
                return

            for i in range(len(nums)):
                # 如果数字已使用，跳过
                if used[i]:
                    continue

                # 去重：当前数字与前一个数字相同，且前一个数字未被使用
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue

                # 做选择
                path.append(nums[i])
                used[i] = True

                # 递归
                backtrack(path, used)

                # 撤销选择
                path.pop()
                used[i] = False

        backtrack([], [False] * len(nums))
        return result

class Solution {
    permuteUnique(nums) {
        const result = [];
        nums.sort((a, b) => a - b); // 排序以便去重

        function backtrack(path, used) {
            // 如果路径长度等于数组长度，加入结果
            if (path.length === nums.length) {
                result.push([...path]); // 深拷贝路径
                return;
            }

            for (let i = 0; i < nums.length; i++) {
                // 如果数字已使用，跳过
                if (used[i]) continue;

                // 去重：当前数字与前一个数字相同，且前一个数字未被使用
                if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])
                    continue;

                // 做选择
                path.push(nums[i]);
                used[i] = true;

                // 递归
                backtrack(path, used);

                // 撤销选择
                path.pop();
                used[i] = false;
            }
        }

        backtrack([], Array(nums.length).fill(false));
        return result;
    }
}

---

Dynamic Programming

分割等和子集

Leetcode 416. Partition Equal Subset Sum

• 题目: 给定一个非空正整数数组nums，判断是否可以将这个数组分割为两个子集，使得两个子集的元素和相等

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11]

• 解法: 动态规划（背包问题）

1. 目标是找到一个子集，使其和等于总和的一半
2. 如果数组总和为奇数，直接返回 False
3. 定义 dp[i] 表示是否存在一个子集，使得这个子集的和为 i
4. 初始化 dp[0] = True（空集的和为 0 总是成立）
5. 遍历数组中的每个数，从 target（总和的一半）开始向下更新 dp 数组
6. 对于每个数 num 和当前的和 i，如果 dp[i - num] 为 True，则 dp[i] 也为 True
7. 最终检查 dp[target] 是否为 True

• Python
• Javascript

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0: # 如果总和是奇数，无法平分
            return False

        target = total_sum // 2
        dp = [False] * (target + 1)
        dp[0] = True # 和为 0 的子集总是存在

        for num in nums:
            for i in range(target, num - 1, -1):
                dp[i] = dp[i] or dp[i - num]

        return dp[target]

class Solution {
    canPartition(nums) {
        const totalSum = nums.reduce((acc, num) => acc + num, 0);
        if (totalSum % 2 !== 0) return false; // 如果总和是奇数，无法平分

        const target = totalSum / 2;
        const dp = Array(target + 1).fill(false);
        dp[0] = true; // 和为 0 的子集总是存在

        for (const num of nums) {
            for (let i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }

        return dp[target];
    }
}

---

组成目标和

Leetcode 494. Target Sum

• 题目: 给定一个数组nums，可以为每个元素加上+或-符号，问有多少种不同的方式使得总和等于目标值target

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

• 解法: 动态规划

1. 将问题转换为子集问题，设 P 是正号部分，N 是负号部分
2. 方程联立：P - N = target 和 P + N = sum(nums) 得到 P = (target + sum(nums)) / 2
3. 如果 (target + sum(nums)) 不是偶数或 target 超过 sum(nums)，返回 0
4. 定义 dp[i] 表示和为 i 的子集数，初始化 dp[0] = 1
5. 遍历数组中的每个数，倒序更新 dp 数组
6. dp[subset_sum] 即为结果

• Python
• Javascript

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)
        # 如果目标值无法分割为两部分，返回 
        if (target + total_sum) % 2 != 0 or total_sum < abs(target):
            return 0

        # 转换为子集和问题
        subset_sum = (target + total_sum) // 2
        # dp[i] 表示和为 i 的子集数
        dp = [0] * (subset_sum + 1)
        dp[0] = 1 # 和为 0 的子集数为 1（空集）

        for num in nums:
            # 从后向前更新 dp 数组
            for i in range(subset_sum, num - 1, -1):
                dp[i] += dp[i - num]

        return dp[subset_sum]

class Solution {
    findTargetSumWays(nums, target) {
        const totalSum = nums.reduce((acc, num) => acc + num, 0);
        // 如果目标值无法分割为两部分，返回 0
        if ((target + totalSum) % 2 !== 0 || totalSum < Math.abs(target))
            return 0;

        // 转换为子集和问题
        const subsetSum = (target + totalSum) / 2;
        const dp = new Array(subsetSum + 1).fill(0);
        dp[0] = 1; // 和为 0 的子集数为 1（空集）

        for (const num of nums) {
            // 从后向前更新 dp 数组
            for (let i = subsetSum; i >= num; i--) {
                dp[i] += dp[i - num];
            }
        }
        
        return dp[subsetSum];
    }
}

---

跳跃游戏

Leetcode 55. Jump Game

• 题目: 给定一个非负整数数组nums，每个元素表示在该位置上最多可以跳跃的步数。判断是否能够从数组的第一个位置跳到最后一个位置

Input: nums = [2,3,1,1,4]
Output: true

• 解法: 贪心算法

1. 初始化变量 maxReach 记录当前能到达的最远位置
2. 遍历数组
    - 如果当前位置 i 超过 maxReach，返回 False，表示无法跳到该位置
    - 更新 maxReach 为 max(maxReach, i + nums[i])
3. 遍历结束后，如果未返回 False，说明可以到达终点

• Python
• Javascript

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_reach = 0 # 初始化能够到达的最远位置

        for i in range(len(nums)):
            # 如果当前位置超过了最远可达位置，返回 False
            if i > max_reach:
                return False
            
            # 更新最远可达位置
            max_reach = max(max_reach, i + nums[i])

        return True

class Solution {
    canJump(nums) {
        let maxReach = 0; // 初始化能够到达的最远位置

        for (let i = 0; i < nums.length; i++) {
            // 如果当前位置超过了最远可达位置，返回 false
            if (i > maxReach) return false;

            // 更新最远可达位置
            maxReach = Math.max(maxReach, i + nums[i]);
        }

        return true;
    }
}

---

最小跳跃次数

Leetcode 45. Jump Game II

• 题目: 给定一个非负整数数组nums，每个元素表示在该位置上最多可以跳跃的步数。求从数组的第一个位置跳到最后一个位置所需的最小跳跃次数

Input: nums = [2,3,1,1,4]
Output: 2

• 解法: 贪心算法

1. 初始化 jumps（跳跃次数），current_end（当前跳跃的边界），farthest（能跳到的最远位置）
2. 遍历数组，更新 farthest 为 max(farthest, i + nums[i])
3. 当到达 current_end 时，增加跳跃次数，并更新 current_end 为 farthest
4. 遍历结束返回 jumps

• Python
• Javascript

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0 # 跳跃次数
        current_end = 0 # 当前跳跃的边界
        farthest = 0 # 当前能跳到的最远位置

        for i in range(len(nums) - 1): # 最后一个元素不需要遍历
            farthest = max(farthest, i + nums[i])
            if i == current_end: # 到达当前跳跃的边界
                jumps += 1
                current_end = farthest

        return jumps

class Solution {
    jump(nums) {
        let jumps = 0; // 跳跃次数
        let currentEnd = 0; // 当前跳跃的边界
        let farthest = 0; // 当前能跳到的最远位置

        for (let i = 0; i < nums.length - 1; i++) { // 最后一个元素不需要遍历
            farthest = Math.max(farthest, i + nums[i]);
            if (i === currentEnd) {
                jumps++;
                currentEnd = farthest;
            }
        }

        return jumps;
    }
}

---

买卖股票的最佳时机

Leetcode 121. Best Time to Buy and Sell Stock

• 题目: 给定一个整数数组prices，其中prices[i]表示某天的股票价格。只允许完成一笔交易（买入和卖出），求最大利润。如果无法获得利润，返回0

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: 在价格为1时买入，价格为6时卖出，利润为6-1=5

• 解法: 贪心算法

1. 初始化最小买入价格为无穷大，最大利润为 0
2. 遍历价格数组
    - 如果当前价格小于最小买入价格，更新最小买入价格
    - 如果当前价格减去最小买入价格的利润大于最大利润，更新最大利润
3. 返回最大利润

• Python
• Javascript

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float("inf") # 最小买入价格
        max_profit = 0 # 最大利润

        for price in prices:
            # 更新最小买入价格
            if price < min_price:
                min_price = price
            # 计算当前利润，并更新最大利润
            elif price - min_price > max_profit:
                max_profit = price - min_price

        return max_profit

class Solution {
    maxProfit(prices) {
        let minPrice = Infinity; // 最小买入价格
        let maxProfit = 0; // 最大利润

        for (const price of prices) {
            // 更新最小买入价格
            if (price < minPrice) 
                minPrice = price;
            // 计算当前利润，并更新最大利润
            else if (price - minPrice > maxProfit)
                maxProfit = price - minPrice;
        }

        return maxProfit;
    }
}

---

股票买卖的最大收益

Leetcode 122. Best Time to Buy and Sell Stock II

• 题目: 给定一个数组，prices[i]表示第i天的股票价格。可以进行多次买卖操作（但必须先卖掉之前的股票后才能再次购买），求能获得的最大利润

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: 在第2天买入（价格=1），第3天卖出（价格=5），收益=5-1=4；然后在第4天买入（价格=3），第5天卖出（价格=6），收益=6-3=3，总收益为7

• 解法: 贪心算法

1. 遍历价格数组，检查是否存在连续上涨的价格差
2. 如果今天的价格高于昨天的价格，将差值累加到最大利润中
3. 遍历完成后，返回最大利润

• Python
• Javascript

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0

        for i in range(1, len(prices)):
            # 如果今天的价格比昨天高，累加差值到利润中
            if prices[i] > prices[i - 1]:
                max_profit += prices[i] - prices[i - 1]
        
        return max_profit

class Solution {
    maxProfit(prices) {
        let maxProfit = 0;

        for (let i = 1; i < prices.length; i++) {
            // 如果今天的价格比昨天高，累加差值到利润中
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        
        return maxProfit;
    }
}

---

不同路径的数目

Leetcode 62. Unique Paths

• 题目: 一个机器人位于一个m x n网格的左上角 (起点在(0, 0))。机器人每次只能向下或向右移动一步。网格的右下角在(m-1, n-1)。问有多少条不同的路径可以到达终点

Input: m = 3, n = 7
Output: 28

• 解法: 动态规划

1. 定义 dp 数组，dp[i][j] 表示到达网格 (i, j) 的路径数量
2. 初始状态: dp[0][j] 和 dp[i][0] 都为 1（第一行和第一列的路径数量都为 1）
3. 状态转移方程: dp[i][j] = dp[i-1][j] + dp[i][j-1]
4. 返回 dp[m-1][n-1]

• Python
• Javascript

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 初始化 dp 数组，所有值为 1
        dp = [[1] * n for _ in range(m)]

        # 填充 dp 表格
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        return dp[m - 1][n - 1]

class Solution {
    uniquePaths(m, n) {
        // 初始化 dp 数组，所有值为 1
        const dp = Array.from({length: m}, () => Array(n).fill(1));

        // 填充 dp 表格
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
}

---

最大连续和

Leetcode 53. Maximum Subarray

• 题目: 给定一个整数数组nums，找到具有最大和的连续子数组（至少包含一个元素），返回其最大和

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6

• 解法: 动态规划

1. 定义 dp[i] 表示以 nums[i] 结尾的最大子数组和
2. 状态转移方程:
   dp[i] = max(nums[i], dp[i-1] + nums[i])
   即当前位置的最大和，要么是当前数字本身，要么是当前数字加上前面的最大和
3. 初始化: dp[0] = nums[0]
4. 遍历数组，计算每个位置的 dp 值，并记录最大值
5. 时间复杂度 O(n)，空间复杂度 O(1)（通过优化只保留当前值）

• Python
• Javascript

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 初始化当前最大和和全局最大和
        current_sum = max_sum = nums[0]

        for num in nums[1:]:
            # 当前和为当前数字或当前数字加之前的和
            current_sum = max(num, current_sum + num)
            # 更新全局最大和
            max_sum = max(max_sum, current_sum)

        return max_sum

class Solution {
    maxSubArray(nums) {
        // 初始化当前最大和和全局最大和
        let currentSum = nums[0];
        let maxSum = nums[0];

        for (let i = 1; i < nums.length; i++) {
            // 当前和为当前数字或当前数字加之前的和
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            // 更新全局最大和
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }
}

---

最长公共子串

Leetcode 1143. Longest Common Subsequence

• 题目: 给定两个字符串text1和text2，返回它们最长公共子序列的长度。如果不存在公共子序列，则返回0

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3

• 解法: 动态规划

1. 定义 dp[i][j]:
   - dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列长度
2. 转移方程:
   - 如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
   - 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
3. 初始化:
   - dp[0][j] = 0 和 dp[i][0] = 0，因为空字符串与任何字符串的公共子序列长度为 0
4. 遍历:
   - 填充整个 dp 表，并返回 dp[m][n]，其中 m 和 n 是 text1 和 text2 的长度

• Python
• Javascript

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        # 创建 dp 数组并初始化
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # 遍历两个字符串的所有前缀组合
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        return dp[m][n]

class Solution {
    longestCommonSubsequence(text1, text2) {
        const m = text1.length, n = text2.length;
        // 创建 dp 数组并初始化
        const dp = Array.from({length: m + 1}, () => 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];
    }
}

---

Other 其他

二维数组去重

• 题目: 给定一个二维数组，可能包含重复的行，实现一个方法去重，返回去重后的二维数组

matrix = [
    [1, 2, 3],
    [1, 2, 3],
    [4, 5, 6]
]

# 输出: [(1, 2, 3), (4, 5, 6)]

• 解法1: 不保留顺序

将每一行转化为不可变类型
    在 Python 中使用 tuple
    在 JavaScript 中使用 JSON.stringify
利用 Set 的特性去重

• Python
• Javascript

class Solution:
    def remove_duplicates(matrix):
        # 将每一行转化为元组并用 set 去重
        unique_rows = set(tuple(row) for row in matrix)
        # 将去重后的结果转回列表形式
        return [list(row) for row in unique_rows]

class Solution {
    removeDuplicates(matrix) {
        // 使用 Set 去重，将每一行转换为字符串
        const uniqueRows = new Set(matrix.map(row => JSON.stringify(rows)));
        // 将字符串还原为数组
        return Array.from(uniqueRows, row => JSON.parse(row));
    }
}

• 解法2: 保留顺序

使用 Set 跟踪已经处理的行
遍历二维数组，检查每一行是否已在 Set 中
    如果未出现过，则添加到结果数组中，并将其标记为已处理

• Python
• Javascript

class Solution:
    def remove_duplicates_with_order(matrix):
        seen = set()
        unique_rows = []

        for row in matrix:
            row_tuple = tuple(row)
            if row_tuple not in seen: # 如果该行尚未处理
                seen.add(row_tuple) # 标记为已处理
                unique_rows.append(row) # 添加到结果中

        return unique_rows

class Solution {
    removeDuplicatesWithOrder(matrix) {
        const seen = new Set();
        const uniqueRows = [];

        for (const row of matrix) {
            const rowString = JSON.stringify(row); // 将行转化为字符串
            if (!seen.has(rowString)) {
                seen.add(rowString);
                uniqueRows.push(row);
            }
        }

        return uniqueRows;
    }
}

---

斐波那契数列

斐波那契数列的定义是
    F(0) = 0
    F(1) = 1
    对于 n >= 2，F(n) = F(n-1) + F(n-2)

数列前几项为
    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

• 解法1: 递归

按照定义，递归计算每个斐波那契数
优点：实现简单，代码清晰
缺点：存在大量重复计算，效率较低

• Python
• Javascript

class Solution:
    def fibonacci(n):
        if n <= 0:
            return 0
        elif n == 1:
            return 1
        else:
            return fibonacci(n - 1) + fibonacci(n - 2)

class Solution {
    fibonacci(n) {
        if (n <= 0) return 0;
        if (n === 1) return 1;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

• 解法2: 动态规划

使用两个变量存储前两个数值，避免重复计算
从 F(2) 开始循环计算，最终返回 F(n)
优点：时间复杂度 O(n)，空间复杂度 O(1)

• Python
• Javascript

class Solution:
    def fibonacci(n):
        if n <= 0:
            return 0
        elif n == 1:
            return 1
        
        prev2, prev1 = 0, 1 # 初始值
        for _ in range(2, n + 1):
            curr = prev1 + prev2 
            prev2 = prev1  # 更新前两个数
            prev1 = curr

        return prev1

class Solution {
    fibonacci(n) {
        if (n <= 0) return 0;
        if (n === 1) return 1;
        
        let prev2 = 0, prev1 = 1;
        for (let i = 2; i <= n; i++) {
            const curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }
}

方法	时间复杂度	空间复杂度	优点	缺点
递归	O(2^n)	O(n)	简单易理解，适合小问题	性能差，大量重复计算
动态规划优化空间	O(n)	O(1)	高效，占用空间少	不保存所有中间结果
通用迭代	O(n)	O(n)	清晰直观，适合扩展	占用更多空间

---

整数反转

Leetcode 7. Reverse Integer

• 题目: 给定一个32位有符号整数x，将其数字部分反转
  • 如果反转后整数溢出（不在[-2^31, 2^31 - 1]范围内），返回0

Input: x = 123
Output: 321

• 解法: 逐位反转

1. 记录整数的符号（正或负），然后将整数取绝对值，方便处理
2. 通过 取余操作 获取最后一位数字，将其添加到结果中
    - 每次更新结果为 res = res * 10 + digit
    - 再通过整除去掉最后一位数字
3. 反转后乘以原始符号恢复符号
4. 检查是否超出 32 位整数范围，如果超出返回 0

• Python
• Javascript

class Solution:
    def reverse(self, x: int) -> int:
        # 定义 32 位整数范围
        INT_MIN, INT_MAX = -(2**31), 2**31 - 1

        result = 0
        sign = -1 if x < 0 else 1 # 记录符号
        x = abs(x)

        while x != 0:
            digit = x % 10 # 取出最后一位数字
            result = result * 10 + digit # 更新结果
            x //= 10 # 去掉最后一位

        result *= sign # 恢复符号

        if result < INT_MIN or result > INT_MAX:
            return 0

        return result

class Solution {
    reverse(x) {
        const INT_MIN = -(2 ** 31);
        const INT_MAX = 2 ** 31 - 1;

        let result = 0;
        const sign = x < 0 ? -1 : 1;
        x = Math.abs(x);

        while (x !== 0) {
            const digit = x % 10; // 取出最后一位数字
            result = result * 10 + digit; // 更新结果
            x = Math.floor(x / 10); // 去掉最后一位
        }

        result *= sign;

        if (result < INT_MIN || result > INT_MAX) return 0;

        return result;
    }
}

---

位1的个数

Leetcode 191. Number of 1 Bits

• 题目: 给定一个无符号整数，返回其二进制表示中1的个数（也称为汉明权重）

Input: n = 11 (二进制表示为 00000000000000000000000000001011)
Output: 3
Explanation: 11 的二进制表示有三个 1

• 解法: 位操作

1. 使用按位与 (n & (n - 1)) 消除最低位的 1，直到 n 为 0，统计次数

• Python
• Javascript

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1 # 每次消除最低位的 1
            count += 1
        return count

class Solution {
    hammingWeight(n) {
        let count = 0;
        while (n !== 0) {
            n &= n - 1; // 每次消除最低位的 1
            count++;
        }
        return count;
    }
}

---

快速排序

• 快速排序是一种基于分治思想的高效排序算法，平均时间复杂度为O(n log n)，最坏情况下时间复杂度为 O(n^2)。它的基本思想是通过一次排序将待排序数组分割成独立的两部分，其中一部分的所有元素都比另一部分的所有元素小，然后对这两部分分别进行递归排序。

def quicksort(arr):
    # 基本条件：如果数组为空或只有一个元素，直接返回
    if len(arr) <= 1:
        return arr
    
    # 选择基准元素
    pivot = arr[len(arr) // 2]
    
    # 将数组分成三个部分：小于基准的部分、等于基准的部分、大于基准的部分
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    # 递归排序左右两部分
    return quicksort(left) + middle + quicksort(right)

---

冒泡排序

• 冒泡排序是一种简单的排序算法，它通过重复遍历列表，将相邻的元素进行比较并交换，使得每次遍历后最大（或最小）的元素逐步“冒泡”到列表的末尾。冒泡排序的时间复杂度为O(n²)，适用于小规模数据的排序。

def bubble_sort(arr):
    n = len(arr)
    
    # 外层循环控制遍历次数
    for i in range(n):
        swapped = False  # 用来标记是否发生交换
        
        # 内层循环进行相邻元素的比较和交换
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # 交换相邻元素
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # 如果没有发生交换，说明数组已经排序完毕
        if not swapped:
            break
    
    return arr

---

插入排序

• 插入排序是一种简单直观的排序算法，适合处理小规模数据。它的工作原理是构建一个有序序列，对于未排序的数据，在已排序的序列中从后向前扫描，找到相应位置并插入。插入排序的时间复杂度为O(n²)，在数组几乎有序的情况下表现很好，接近O(n)。

def insertion_sort(arr):
    # 从第二个元素开始遍历
    for i in range(1, len(arr)):
        key = arr[i]  # 当前待插入的元素
        j = i - 1
        
        # 向前遍历已排序的序列，找到适合的位置插入当前元素
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 将大于 key 的元素向后移动
            j -= 1
        
        arr[j + 1] = key  # 将当前元素插入到正确的位置
    
    return arr

---

归并排序

• 归并排序是一种经典的分治算法，通过将数组递归地分成两个子数组，分别进行排序，然后合并这两个有序子数组来实现排序。归并排序的时间复杂度为O(n log n)，它具有稳定性且适用于大规模数据的排序。

def merge_sort(arr):
    # 如果数组长度小于等于1，则直接返回
    if len(arr) <= 1:
        return arr
    
    # 分割数组
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    
    # 合并两个已排序的子数组
    return merge(left_half, right_half)

def merge(left, right):
    sorted_array = []
    i = j = 0
    
    # 逐步比较两个子数组中的元素，按顺序合并
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_array.append(left[i])
            i += 1
        else:
            sorted_array.append(right[j])
            j += 1
    
    # 将剩余的元素加入合并结果
    sorted_array.extend(left[i:])
    sorted_array.extend(right[j:])
    
    return sorted_array

---

堆排序

• 堆排序是一种基于二叉堆的数据结构的比较排序算法，时间复杂度为O(n log n)。堆排序分为最大堆和最小堆，通常使用最大堆来进行升序排序。堆排序具有原地排序的特点，不需要额外的存储空间。

def heapify(arr, n, i):
    largest = i  # 设当前节点 i 为最大
    left = 2 * i + 1  # 左子节点
    right = 2 * i + 2  # 右子节点

    # 如果左子节点存在，且大于当前最大值
    if left < n and arr[left] > arr[largest]:
        largest = left

    # 如果右子节点存在，且大于当前最大值
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大值不是当前节点，进行交换并继续调整堆
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # 构建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 交换元素，并重新调整堆结构
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 将堆顶元素移到数组末尾
        heapify(arr, i, 0)  # 调整剩下的部分为最大堆

    return arr

---

深度优先搜索 (DFS) & 广度优先搜索 (BFS)

• 深度优先搜索: DFS是一种通过深入每一个节点并尽可能深地搜索其子节点的遍历算法。可以使用递归或显式栈来实现。

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    
    # 访问当前节点
    print(node)
    visited.add(node)

    # 递归访问相邻节点
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

• 广度优先搜索: BFS是一种逐层遍历算法，先访问当前节点的所有相邻节点，再继续访问这些相邻节点的相邻节点。BFS通常用队列来实现。

def bfs(graph, start):
    visited = set()
    queue = deque([start])  # 使用双端队列作为队列

    while queue:
        node = queue.popleft()  # 从队列中取出第一个节点
        if node not in visited:
            print(node)
            visited.add(node)
            # 将相邻节点加入队列
            queue.extend(graph[node])

---

前序，中序，后序

• 前序遍历顺序为：根节点 -> 左子树 -> 右子树

def preorder(root):
    if root:
        print(root.val)  # 先访问根节点
        preorder(root.left)  # 递归访问左子树
        preorder(root.right)  # 递归访问右子树

• 中序遍历顺序为：左子树 -> 根节点 -> 右子树

def inorder(root):
    if root:
        inorder(root.left)  # 递归访问左子树
        print(root.val)  # 访问根节点
        inorder(root.right)  # 递归访问右子树

• 后序遍历顺序为：左子树 -> 右子树 -> 根节点

def postorder(root):
    if root:
        postorder(root.left)  # 递归访问左子树
        postorder(root.right)  # 递归访问右子树
        print(root.val)  # 最后访问根节点

---