LeetCode总集合

题目

此为自己有博客之后刷leetcode的总集合，已经好几年没刷了，总是断断续续的，毕竟懒狗。

序号1到399

序号400到999

序号1000后

剑指Offer

剑指II

程序员面试金典

其他

需要回顾的题目

全排列46和47

后序遍历迭代版本

手撸字典树用js和go

动态规划经典 322

二维动态规划经典 1143

矩阵类型 bfs 1091

解题小技巧

刷题整体的思路可以查看

https://programmercarl.com/

大小写切换

可以不用知道字母 c 的大小写的情况，做大小写切换。

char c = '字母'
c ^= (1 << 5)

最大公约数

使用辗转相除法

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。

gcd(a,b) = gcd(b,a mod b)

const gcd = (a, b) => {
    if (b === 0) return a;
    return gcd(b, a % b);
};

另：最小公倍数 = 两数乘积 / 最大公约数乘积

滑动窗口的模板

function findSubArray(nums) {
    const n = nums.length;
    let left = 0, right = 0; //[left, right]，闭区间
    let sums = 0; //用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数
    let res = 0; // 保存最大的满足题目要求的 子数组/子串 长度
    while (right < n) {
        // 当右边的指针没有搜索到 数组/字符串 的结尾
        sums += nums[right]; // 增加当前右边指针的数字/字符的求和/计数
        while (不符合条件) { //区间[left, right]不符合题意
            // 此时需要一直移动左指针，直至找到一个符合题意的区间
            sums -= nums[left]; // 移动左指针前需要从counter中减少left位置字符的求和/计数
            left += 1; // 真正的移动左指针，注意不能跟上面一行代码写反
        }// 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
        res = max(res, right - left + 1); // 需要更新结果
        right += 1; // 移动右指针，去探索新的区间
    }
    return res;
}

回溯的模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

最小堆实现

众所周知，js没有自带的小根堆实现，所以需要自己写一个，这里贴一个抄的，自己写还不行。

class MinHeap {
    constructor(data = []) {
        this.data = data;
        this.comparator = (a, b) => a - b;
        this.heapify();
    }
    // 建堆
    heapify() {
        if (this.size() < 2) return;
        // 将每个元素插入，往上冒到合适位置
        for (let i = 1; i < this.size(); i++) {
            this.bubbleUp(i);
        }
    }
    // 获得堆顶元素
    peek() {
        if (this.size() === 0) return null;
        return this.data[0];
    }
    // 往小顶堆中插入元素
    offer(value) {
        this.data.push(value);
        // 在最后的位置插入且向上冒泡
        this.bubbleUp(this.size() - 1);
    }
    // 移除顶堆元素
    poll() {
        if (this.size() === 0) {
            return null;
        }
        const result = this.data[0];
        const last = this.data.pop();
        if (this.size() !== 0) {
            // 最末尾元素放到堆顶
            this.data[0] = last;
            // 向下调整直至放到合适位置
            this.bubbleDown(0);
        }
        return result;
    }

    bubbleUp(index) {
        while (index > 0) {
            // 获得父节点索引
            const parentIndex = (index - 1) >> 1;
            // 如果要调整的节点比父节点的值还要小，就需要一直往上冒
            if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {
                // 交换位置往上冒
                this.swap(index, parentIndex);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    bubbleDown(index) {
        const lastIndex = this.size() - 1;
        while (true) {
            // 获得要调整的节点的左子节点和右子节点的索引
            const leftIndex = index * 2 + 1;
            const rightIndex = index * 2 + 2;
            let findIndex = index;
            // 如果左/右子节点的值小于当前要调整的节点的值
            if (leftIndex <= lastIndex && this.comparator(this.data[leftIndex], this.data[findIndex]) < 0) {
                findIndex = leftIndex;
            }
            if (rightIndex <= lastIndex && this.comparator(this.data[rightIndex], this.data[findIndex]) < 0) {
                findIndex = rightIndex;
            }
            // 则要交换
            if (index !== findIndex) {
                this.swap(index, findIndex);
                index = findIndex;
            } else {
                break;
            }
        }
    }
    // 交换元素
    swap(index1, index2) {
        [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
    }
    // 获得堆大小
    size() {
        return this.data.length;
    }
}