力扣笔记

链表

双指针技巧

合并或分解链表：用双指针分别遍历原链表，第三个指针配合虚拟头节点简化边界处理。21合并两个有序链表

快慢指针：寻找中点、环形链表问题。快慢指针追击，相遇说明成环，其中一指针回到头节点。以相同速度前进，再次相遇的位置就是环的起点。141环形链表，142环形链表II

ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head,*fast = head;
        while(fast != nullptr && fast->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){
                slow = head;
                while(slow != fast){
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return nullptr;
}

链表相交：分别用两个指针遍历链表，遍历完一个接着遍历另外一个，如果相遇说明相交。160相交链表

回文链表：判断回文串就用双指针，单链表无法从后遍历，所以可以利用栈存放一个倒序链表。也可以用系统堆栈，利用递归模拟一个栈。在限制空间复杂度的情况下，可以从中间往两边找。首先通过快慢指针找到链表中点，然后用左右指针判断是否回文。234回文链表

2两数相加，287寻找重复数

链表翻转

迭代解法：维护三个指针，遍历翻转每个节点的指向。注意结束迭代的条件及返回值。

递归解法：分解问题，反转整个链表转换成反转后n-1个节点，然后指向头节点。

翻转前N个节点：记录第n+1个节点，翻转后head接上successor。

K个一组翻转：分解问题，首先翻转前K个节点，然后接上后续链表。后续链表又可以递归分解。24两两交换链表中节点，25K个一组翻转链表

ListNode* reverseKGroup(ListNode* head, int k) {
    if(head == nullptr){
        return nullptr;
    }
    ListNode *last = head;
    for(int i = 0;i<k;++i){
        if(last == nullptr){
            return head;//如果剩余节点不足k个，直接返回
        }
        last = last->next;
    }
    ListNode *newhead = reverseN(head,k);
    head->next = reverseKGroup(last,k);//从last开始翻转k个节点
    return newhead;
}
//翻转前N个节点
ListNode *reverseN(ListNode *head,int n){
    if(head == nullptr || head->next == nullptr){
        return head;
    }
    ListNode *pre,*cur,*next;
    pre = nullptr;
    cur = head;
    next = cur->next;
    while(cur != nullptr && n > 0){
        cur->next = pre;
        pre = cur;
        cur = next;
        if(next != nullptr){
            next = next->next;
        }
        --n;
    }
    head->next = cur;//翻转后要指向剩余节点
    return pre;
}

206翻转链表

数组

双指针技巧

快慢指针

slow指针在后面维护结果，fast指针在前面探路，找到符合条件的元素就赋值给 slow。283移动零

滑动窗口

子串子数组题目，考虑滑动窗口，回答三个问题：
1.什么时候扩大窗口？窗口加入元素时更新什么数据？
2.什么时候缩小窗口？窗口删除元素时更新什么数据？
3.什么时候更新结果？

如果能回答则可以用滑动窗口。

代码框架：

auto window; //根据实际选择数据结构
int left = right = 0; //左闭右开区间
while(right < s.size()){
    char c = s[right];
    window.add(c);
    right++;
    ...
    //更新数据
    ...
    while(window满足要求){
        char d = s[left];
        window.remove(d);
        left--;
        ...
        //更新数据
        ...
    }
}

76最小覆盖子串、438找到字符串中所有字母异位词、3无重复字符的最长子串

左右指针

两个指针相向而行，从两端向中间移动。

回文串判断：从中往左右或左右往中间两个指针，判断是否回文子串。5最长回文子串

二分查找

对于有序数组，考虑使用二分法。使用左闭右闭区间适合记忆。

代码框架：

int binary_search(vector<int>& nums, int target) {
    int left = 0, right = nums.size()-1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

int left_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size()-1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 判断 target 是否存在于 nums 中
    if (left < 0 || left >= nums.size()) {
        return -1;
    }
    // 判断一下 nums[left] 是不是 target
    return nums[left] == target ? left : -1;
}

int right_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size()-1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 由于 while 的结束条件是 right == left - 1，且现在在求右边界
    // 所以用 right 替代 left - 1 更好记
    if (right < 0 || right >= nums.size()) {
        return -1;
    }
    return nums[right] == target ? right : -1;
}

34在排序数组中查找元素的第一个和最后一个位置，35搜索插入位置，33搜索旋转排序数组，153寻找旋转排序数组中的最小值

前缀和

前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和、之积等。但前缀和要求数组元素不能改变，且运算存在逆运算。

代码框架：

class NumArray {
    // 前缀和数组
    vector<int> preSum;

    // 输入一个数组，构造前缀和
    public:
    NumArray(vector<int>& nums) {
        // preSum[0] = 0，便于计算累加和
        preSum.resize(nums.size() + 1);
        // 计算 nums 的累加和
        for (int i = 1; i < preSum.size(); i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }

    // 查询闭区间 [left, right] 的累加和
    int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
};

238除了自身以外数组的乘积

前缀和+哈希表

要寻找符合某条件的子数组，用前缀和+哈希表。哈希表记录前缀和到索引的映射。

560和为K的子数组

二维数组遍历技巧

旋转：先沿对角线翻转，再左右翻转。48旋转图像

螺旋遍历：用四个指针维护遍历的边界，按顺序每遍历一条边边界就缩小。54螺旋矩阵

栈

先入后出性质

考察栈先入后出性质，常见于表达式运算、判断括号等，主要设计好出栈出栈的逻辑。20有效的括号，394字符串解码

设计栈

155最小栈

单调栈

找下一个/上一个更大/更小元素问题，用单调栈。如果是环形数组，讲数组复制一遍，然后取余遍历。

代码框架：

// 计算 nums 中每个元素的下一个更大元素的索引
vector<int> nextGreaterElementIndex(vector<int>& nums) {
    int n = nums.size();
    // 存放答案的数组
    vector<int> res(n);
    // 栈中存放索引
    stack<int> stk;
    // 因为是求 nums[i] 后面的元素，所以倒着往栈里放
    for (int i = n - 1; i >= 0; i--) {
        // 删掉 nums[i] 后面较小的元素
        while (!stk.empty() && nums[stk.top()] <= nums[i]) {//改变比较符，可实现找更大/更小（或相等）元素
            stk.pop();
        }
        // 现在栈顶就是 nums[i] 身后更大元素的索引
        res[i] = stk.empty() ? -1 : stk.top();
        stk.push(i);
    }
    return res;
}

739每日温度，84柱状图中的最大矩形

二叉树

递归问题两种思路

1. 分解问题：把较大规模的问题分解成规模较小的问题，通过子问题的解得到原问题的解。递归函数一定要有一个清晰的定义，说明这个函数参数的含义是什么，返回什么结果。
2. 遍历：递归树上的节点并没有一个明确的含义，只是记录了之前所做的一些选择。需要一个无返回值的遍历函数，单纯起到遍历递归树，收集目标结果的作用。

94二叉树的中序遍历，104二叉树的最大深度，226翻转二叉树，543二叉树的直径，114二叉树展开为链表

动规、回溯、DFS的区别

动规就是分解问题的思路，关注整个子树，每个子树的结构相同。

回溯算法关注树枝，在树枝上做选择（到达节点前），for循环中节点之间移动时进行选择与撤销选择。

DFS关注每个节点本身。for循环外做选择。

构造二叉树

分解问题的思路，先构造根节点，再构造左右子树。前序和后序遍历可以确定根节点，通过中序遍历确认左右子树的范围。105从前序和中序遍历序列构造二叉树

最近公共祖先

如果一个节点是公共祖先，那么就能在左右子树中分别找到p和q。通过find函数找子树是否存在对应的val1或val2，递归查找，找到就返回子节点，找不到就说明不存在。根据题目要求，如果没有说明一定存在p和q，就必须实现完全遍历，在后序位置再进行判断。

236二叉树的最近公共祖先

二叉搜索树

BST的三大特性

1. 对于每个节点node，左子树节点的值都小于node，右子树节点的值都大于node。
2. 对于每个节点node，左右子树都是BST。
3. BST的中序遍历有序。

230二叉搜索树中第k小的元素，98验证二叉搜索树，108将有序数组转换为二叉搜索树

数据结构设计

LRU

要实现LRU，考虑两点：根据key查询val，需要哈希表实现；要删除最久未使用的，需要链表实现。
get函数：查表返回val，并将节点移动到链表尾。由于节点移动涉及到上一个节点的next指针，必须采用双向链表。
put函数：查表，如果key存在则修改val。如果不存在，判断容量是否已满，已满则删掉链表头节点。然后添加新节点到链表尾。由于删除节点时，需要把映射也删除，所以链表节点同时存放key和value。

146LRU缓存

回溯算法

回溯算法代码框架：

void backtrack(){
    if(到达叶子节点){
        return;
    }
    for(int i = 0;i<size;++i){
        //做选择
        ...
        backtrack();
        ...
        //撤销选择
    }
}

backtrack函数一般没有返回值，如果要提前结束遍历，可以用一个全局变量。

46全排列，51N皇后