算法

哈希表查找逻辑

哈希表的底层是桶数组（一个存放键值对的数组）

1. 先用 key 通过哈希函数计算出哈希值
2. 再根据哈希值和桶（bucket）数量确定索引位置
3. 若该位置的 key 与目标一致，则返回对应 value
4. 否则按冲突解决策略（如链地址法或开放寻址）继续查找，直到匹配 key 并取出 value。

• 元素的占到容量的百分比是负载因子（默认 0.75），超过了阈值则扩容
• HashMap 的扩容是扩大二倍，原来的哈希值会新增 1 个 bit，既不用重新计算又能随机分散到新的桶中

滑动窗口

left 是左边界的索引，是在窗口内的最左元素
定长窗口直接算

int left = right - k + 1;//k 是窗口长度

不定长用 while

//这个是典型，left初值是0，给0出边界后left进一
//此时left就指向新窗口的左边界了
//窗口长度就是正常的右减左加一，right-left+1
while (n0 > k) {
    if (nums[left] == 0) n0--;
    left++;
}

二分查找

• 查找 target 第一次出现的索引
• ranges::lower_bound C++20 里引入了这个函数，找下界，下面这就是他的具体实现
• 默认比较器用的 less，就是 mid 值 < target，改用 greater 后就是 mid > target

int n = nums.size();
int left = 0, right = n - 1;//指针初值设为两头
// 循环不变量：整个循环包括结束都会严格满足下面这两个条件
// 循环不变量：看最后左右指针在mid汇合的时候的条件，计算之后左右指针落点
// nums[left-1] < target
// nums[right+1] >= target
// 因为是二分查找，所以最后两指针是相邻的
while ( left <= right ) {//while循环
    int mid = (left + right ) / 2;
    //如果中间值在target左侧，就更新left，缩小左边界
    if (nums[mid] < target) {//这个地方比较的是mid,老错写成left
        //left要设为mid+1，是闭区间最左边界
        left = mid + 1;
    }
    //right要设为mid-1
    else right = mid - 1;
}
return left;//最后返回的是target第一次出现的索引，也等于right+1
//也适用于target不存在的情况，只要记住循环不变量就行
//就比如lower_bound(nums, 0);能返回第一个0的索引
//lower_bound(nums,1);若1不存在能返回第一个大于0的索引

• lower_bound(nums.begin(),nums.(end),target)，升序，找到第一个>=target 的值的元素，并返回该元素的迭代器
• lower_bound( begin , end , val , less<type>() )升序，找到第一个>=target 的元素，与上面不写的升序功能相同,官方的自定义比较函数
• lower_bound( begin , end , val , greater<type>() )降序，找到第一个<=target 的元素
• 返回的值是迭代器，若要获取索引，需要用- begin
• ranges::lower_bound(nums2.begin(),nums2.end(), nums1[i], ranges::greater{}) - nums2.begin();//减去开始获取索引
• upper_bound()也是升序，但是是找到第一个>target 的元素

4. 寻找两个正序数组的中位数

class Solution {
public:
    // 真是难题，我用灵神的双指针法先做一遍
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 约定nums1是哪个小数组，方便操作
        if (nums1.size() > nums2.size()) {
            swap(nums1, nums2);
        }
        // 交换之后获取长度
        int n1 = nums1.size();
        int n2 = nums2.size();
        // 两头插入无穷边界，用来避免越界和保证有结果
        nums1.insert(nums1.begin(), INT_MIN);
        nums2.insert(nums2.begin(), INT_MIN);
        nums1.push_back(INT_MAX);
        nums2.push_back(INT_MAX);

        // 中位数（包含中位数）的左边为第一组，右边为第二组
        // 如果nums1有i个数在第一组，那nums2应该有(n1 + n2 + 1)/2 - i = j个数在第一组
        // 偶数是（n1 + n2)/2 和奇数加一那种可以合并，因为偶数加一也会被截断，不影响
        // 二分的边界应该用1组的范围加负无穷，同时因为头部插入了负无穷所以right不用减一了
        int left = 0;
        int right = n1;
        // 既然知道了要找的边界，i和j又换算关系，那就能用二分去找这个边界
        // 用1组找对应的i和j+1，因为是刚好的，那另一组就不用看了
        while (left <= right) {
            int mid = left + (right - left) / 2;// 先减再加可以防止整型溢出
            // i和j作为临时变量，方便理解
            int i = mid;
            int j = (n1 + n2 + 1)/2 - i;// 用i换算成j就可以找组2里对应数字了
            if (nums1[i] <= nums2[j + 1]) {// 找到刚满足的那个边界
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 最后的right就应该是暴力做法里的i
        int i = right;
        int j = (n1 + n2 + 1)/2 - i;
        // 第一组的最大值
        int first = max(nums1[i], nums2[j]);
        // 第二组的最小值
        int second = min(nums1[i + 1], nums2[j + 1]);
        return (n1 + n2)%2 ? first : (first + second)/2.0;
    }
};

前缀和

s[i]就是前 i 个元素的和
适合求区间和，无论是否有序

// 建立前缀和数组
vector<int> s;
s.resize(nums.size() + 1);// 常用resize(n + 1)
for (int i = 0; i < nums.size(); i++) {
    // 第一位就是0，计算[left, right]区间的和就是s[right + 1] - s[left]
    s[i + 1] = s[i] + nums[i];
}

找所有和为 k 的子串

for (int i = 0 ; i < pre.size(); i++) {// i是正在遍历的数组，j是要查的
    // 等式变换pre[i] - pre[j] = k; pre[j] = pre[i] - k;
    auto it = map.find(pre[i] - k);// find返回迭代器
    if (it != nullptr) ans += it -> second;
    // 用元素当key，频率当value
    map[pre[i]]++;
}

链表 List

翻转链表

ListNode* reverseList(ListNode* node) {
        ListNode* pre = nullptr, *cur = node;
        while (cur != nullptr) {
            ListNode* nxt = cur -> next;// nxt每次重新赋值
            cur -> next = pre;// 一次只改一个next指向
            pre = cur;// 注意顺序，先把cur赋出去，再覆盖cur
            cur = nxt;
        }
        return pre;// 最后返回新链表的头结点
    }

快慢指针法，查看是否存在环型链表

bool hasCycle(ListNode *head) {
    // 定义快慢指针
    ListNode* fast = head, *slow = head;
    // 省略 != nullptr
    while (fast && fast -> next) {
        // 快指针每次走两步，慢指针每次走一步
        slow = slow -> next;
        fast = fast -> next -> next;
        if (fast == slow) return true;// 有环的会一直打转直到相遇
    }
    return false;
}

快慢指针法，找中间节点

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while (fast != nullptr && fast -> next != nullptr) {
        slow = slow -> next;
        fast = fast -> next -> next;
    }
    return slow;// 奇数返回中间，偶数返回中间右侧第一个
}

虚拟头结点，头插法，合并两个有序链表

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode dummy(0); // 虚拟头节点
    ListNode* tail = &dummy;
    // 直到走空一个链表为止
    while (list1 != nullptr && list2 != nullptr) {
        if (list1 -> val <= list2 -> val) {
            // 比较此时两个链表谁的val大
            tail -> next = list1;
            // 然后链表走一步继续比较
            list1 = list1 -> next;
        }
        else {
            tail -> next = list2;
            list2 = list2 -> next;
        }
        // 上面确定了tail的next，这里走一步到最新节点
        tail = tail -> next;
    }
    // 因为是有序的，所以后面的直连接第一个节点就行，谁存在就连接谁
    tail -> next = list1 ? list1 : list2;
    return dummy.next;
}

二叉树

深度优先搜索(DFS)，用递归或者栈实现

// 递归中序遍历
void Recursion(TreeNode* root, vector<int> &ans) {
    if (root == nullptr) return;// 终止条件
    Recursion(root->left, ans);// 记得把数组地址传进去
    ans.push_back(root->val);
    Recursion(root->right, ans);
}
// 栈中序遍历，一句话的核心思想：一路向左，走到头；弹出处理，转右再走左。
stack<TreeNode*> stk;
// 只要存在结点或者栈不空就进行，直到结点和栈都空
while (root != nullptr || !stk.empty()) {
    // 先把结点左子树全压进去
    while (root != nullptr) {
        stk.push(root);
        root = root->left;
    }
    // 出来之后的root是空，先把栈里最先结点赋回去
    // 每次while循环都会取出最新的结点
    root = stk.top();
    // 当前结点不存在左子树，把值放进数组，进行中序遍历
    ans.push_back(stk.top()->val);
    stk.pop();
    // 最后root再更新成右子树
    root = root->right;
}

广度优先搜索(BFS)，用队列实现

// BFS广度优先遍历，用队列来打成，先进后出
// 用队列存储指针
queue<TreeNode*> queue;
// 二维向量存储结果
vector<vector<int>> res;
queue.push(root);
while (!queue.empty()) {
    // 构建一行
    vector<int> vals;
    // 每次把上一轮存进来的子节点都遍历完
    for(int n = queue.size(); n > 0; n--) {
        // 获取当前结点
        TreeNode* node = queue.front();
        // 把当前结点的左右子树推进队列
        if (node->left) queue.push(node->left);
        if (node->right) queue.push(node->right);
        // 把结点的值放入向量
        vals.push_back(node->val);
        // 弹出尾结点
        queue.pop();
    }
    // 把构建的一行放入答案
    res.emplace_back(vals);
}
return res;

递归

把原问题化解成一个个和相似的子问题，然后确定好递归的终止条件

数组转换为平衡二叉树

// 把 nums[left] 到 nums[right-1] 转成平衡二叉搜索树
TreeNode* dfs(vector<int>& nums, int left, int right) {
    if (left == right) return nullptr;
    int m = (left + right) / 2;
    TreeNode* node = new TreeNode(nums[m]);
    node->left = dfs(nums, left, m);
    node->right = dfs(nums, m+1 , right);
    return node;
    // 也可以直接用构造函数写返回值，第一个参数是val，第二个是左子树，第二个是右子树
    // return new TreeNode(m, dfs(nums, left, m), dfs(nums, m+1, right))
}

二叉搜索树，左子树严格小于根节点，右子树严格大于根节点
中序遍历就是升序

回溯

用递归实现

全排列问题

// 全排列每个数字只能出现一次，所以下一轮应去掉当前选择的数
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;// 建立ans用来存答案
        int n = nums.size();// 获取长度用来设置递归次数
        vector<int> vec(n), select(n);// 存储每个结果，和每一轮能选的数

        // 递归，i代表当前排序结果的索引索引，所以i等于n的时候就终止了
        auto dfs = [&](this auto&& dfs, int i) -> void {
            if (i == n) {位数到n的时候停止
                ans.emplace_back(vec);// 放进全排列的结果
                return;// 终止递归
            }
            // for循环遍历每个数字
            for (int j = 0; j < n; j++) {
                if (select[j] == 0) {// 如果当前的数字为0就可选，不为0就跳过
                    vec[i] = nums[j];// 把数字数字放进数组，同位的直接覆盖就行
                    // 用select来标记能选的数，因为vector初始化值为0，所以约定0为可选，1为不能
                    select[j] = 1;// 给下次遍历做标记，当前的数字不可选
                    dfs(i + 1);// 选择下一位的数字
                    select[j] = 0;// 因为是深度遍历，所以最后恢复现场就能把所有结果遍历出
                }
            }
            // void函数会在执行完最后一条语句后自动返回，可以不用在末尾显示的写return;
            // 但if里面的是必须的，用来终止递归
            // return;
        };
        dfs(0);// 开始遍历
        return ans;
    }
};

问：什么时候需要写恢复现场，什么时候不需要写？

答：下面代码中，如果初始化 path 为空列表，就需要写恢复现场。本题由于所有括号长度都是固定的 2n，我们可以创建一个长为 2n 的 path 列表，在递归时直接写入字符（而不是插入字符），这样做无需写恢复现场。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string path;
                                        // 左右括号数量
        auto dfs = [&](this auto&& dfs, int l, int r) {
            // 括号数量是对数二倍
            if (r == n) {
                ans.emplace_back(path);
                return;
            }
            if (l < n) {
                path.push_back('(');
                dfs(l + 1, r);// 每个dfs后面都应该邻着现场恢复
                path.pop_back();
            }
            if (l > r) {
                path.push_back(')');
                dfs(l, r + 1);// 每个dfs后面都应该邻着现场恢复
                path.pop_back();
            }
            return;
        };
        dfs(0, 0);
        return ans;
    }
};

string path(2 * n, 0);
// 结果不用取子集都是填满的时候，可以一开始创建初始化好空间的path
// 然后每次直接覆盖对应索引，就不用现场恢复，开销更小
path[l + r] = '(';
dfs(l + 1, r);

79.单词搜索

class Solution {
public:
    // 用深度遍历，图论
    bool exist(vector<vector<char>>& board, string word) {
        bool flag = false;
        int n = word.size();
        // 新建一个标记二维向量
        vector<vector<int>> mark(board.size(), vector<int>(board[0].size(), 0));

        // 传横纵坐标                    // 索引和横纵坐标
        auto dfs = [&](this auto&& dfs, int i, int x, int y) -> void {
            // 判断坐标是否合法
            if (x<0 || y<0 || x>=board.size() || y>=board[0].size()) return;
            // 对比字符是否是目标，以及是否走过
            if (board[x][y] != word[i] || mark[x][y] == 1) return;
            // 下面就是找到了的逻辑
            // 标记走过的结点
            mark[x][y] = 1;
            if (i == n - 1) {// i是索引，所以对比的大小要减一
                flag = true;
            }
            dfs(i + 1, x + 1, y);
            dfs(i + 1, x, y + 1);
            dfs(i + 1, x - 1, y);
            dfs(i + 1, x, y - 1);
            // 到这了就说明上面都找完了，当前坐标该回溯了
            mark[x][y] = 0;// 恢复现场
        };
        // 应该一开始用嵌套for循环找最初字符，然后开始递归
        for (int x = 0; x < board.size(); x++) {
            for (int y = 0; y < board[0].size(); y++) {
                dfs(0, x, y);
            }
        }
        return flag;
    }
};