2025-12-02小记

周二，没课，感觉和昨天过的差不多，甚至早上没课，睡懒觉。
然后出门吃午饭。

下午开始干活。

刷题：
先是刷题了树的剩下2题的递归，感觉写的有些感觉了，都能给他过了。

965. 单值二叉树

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。

bool isUnivalTree(TreeNode* root) {
        if(root==nullptr)
        {
            return true;
        }
        if(root->left!=nullptr)
        {
            if(root->left->val!=root->val)
            {
                return false;
            }
        }
        if(root->right!=nullptr)
        {
            if(root->right->val!=root->val)
            {
                return false;
            }
        }
        return isUnivalTree(root->left)&&isUnivalTree(root->right);    
    }

虽然是简单题，但是一遍过了，不错，对递归有些理解了。
对这题的总结是：无论是开头为空还是到叶结点为空，返回为真
然后如果左孩子存在，看根与左孩子是否相等，同理又孩子
要注意的是，判断这种好像就是看是否找到了不对的地方就返回false,如果是对的就不用管，直接走到叶子结点
同理看判断是否是相同的树，就是为空是真，然后找不对的地方就直接返回false了。

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

bool isduicheng(TreeNode *p,TreeNode *q)
    {
        if(p==nullptr&&q==nullptr)
        {
            return true;
        }
        else if((p==nullptr&&q!=nullptr)||(p!=nullptr&&q==nullptr))
        {
            return false;
        }
        else if(p->val!=q->val)
        {
            return false;
        }
        return isduicheng(p->left,q->right)&&isduicheng(p->right,q->left);
    }

直接写一个判断对称，和之前树的相同同理的，就是左右子树的位置换一下，就是掌握了一下递归的思考应该就好写了。

然后去看了一眼回溯，刚开始，还是不太会，上来就是一个N皇后，这个后面等算法考试再看看，看了一个中等的，但是自己没写出来，思路是有一些了。

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

bool exist(vector<vector<char>>& board, string word) {
        //这个代码是最为接近我原来写的那个方式的了
        int m = board.size();
        int n = board[0].size();
        // 遍历每个单元格作为起点
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 只有起点字符匹配，才启动回溯
                if (board[i][j] == word[0]) {
                    if (backtrack(board, word, i, j, 0)) {
                        return true; // 找到匹配路径，直接返回
                    }
                }
            }
        }
        return false; // 所有起点都匹配失败
    }
    bool backtrack(vector<vector<char>>& board, string& word, int i, int j, int k) {
        // 终止条件：已匹配完所有字符
        if (k == word.size()) {
            return true;
        }
        // 约束检查：越界/字符不匹配 → 失败
        int m = board.size();
        int n = board[0].size();
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k]) {
            return false;
        }
        // 标记当前单元格为已访问（修改为特殊字符，避免额外空间）
        char temp = board[i][j];
        board[i][j] = '/';
        // 递归探索上下左右四个方向
        bool res = backtrack(board, word, i+1, j, k+1) // 下
                || backtrack(board, word, i-1, j, k+1) // 上
                || backtrack(board, word, i, j+1, k+1) // 右
                || backtrack(board, word, i, j-1, k+1); // 左
        // 撤销标记：恢复原始字符（回溯核心）
        board[i][j] = temp;
        return res;
    }

尽量写了一份有模板样子的，但是不行
还是先学习这份代码：
首先主函数，跟原版思路一样，就是先找到第一个可行位置，然后开始调用一个判断的递归功能函数。
递归功能函数传入参数，首先判断有没有满足要求了，就直接返回true。
再这里要看的是找到字符，一方面检查越界，原本也考虑了，但是写的不好
然后递归搜索，要找上下左右的字符串，看是否匹配，然后进一步判断长度是否达标了。
同时，要看到因为不能重复用单元格，因此，每次找到后要变化当前单元格，再进行递归搜索四周。
但是递归搜索四周后，由于恢复当前单元格，方便重新从主函数的循环再次找到一个开头搜索。
可以稍微从中找到一些模板的感觉:

// 主函数：遍历起点，启动回溯
函数 主函数(网格 board, 目标 word) -> 布尔值：
    行数m = board行数，列数n = board列数
    
    遍历每个单元格(i,j)：
        若 起点匹配条件（如board[i][j]==word[0]）：
            若 回溯函数(board, word, i, j, 0) 为真：
                返回真
    返回假

// 回溯核心函数
函数 回溯函数(board, word, i, j, k) -> 布尔值：
    // 1. 终止条件：匹配完成
    若 k == word长度：返回真
    
    // 2. 约束检查：无效路径
    若 越界 或 board[i][j]≠word[k]：返回假
    
    // 3. 标记已访问
    临时保存当前值 = board[i][j]
    board[i][j] = 特殊标记
    
    // 4. 探索上下左右
    结果 = 下探(i+1,j,k+1) 或 上探(i-1,j,k+1) 或 右探(i,j+1,k+1) 或 左探(i,j-1,k+1)
    
    // 5. 回溯恢复
    board[i][j] = 临时保存值
    
    // 6. 返回结果
    返回结果

然后去写作业了，把那个最优化方法的第七章，也是最后一章的作业给他写完了，说明也快要结课了。

晚上还是照例看数据库，把那个锁给结束了，innoDB引擎的架构开了个头，后面全是理解性的东西了，指令学的差不多了。

行级锁

每次操作锁住对应的行数据。锁定粒度最小，发生锁冲突的概率最低，并发度最高。应用在InnoDB存储引擎中。

1. 行锁(Record Lock):锁定单个行记录的锁，防止其他事务对此行进行update和delete。在RC、RR隔离级别下都支持。
2. 间隙锁(GapLock):锁定索引记录间隙(不含该记录)，确保索引记录间隙不变，防止其他事务在这个间隙进行insert，产生幻读。在RR隔离级别下都支持。
3. 临键锁(Next-Key Lock):行锁和间隙锁(所有前面的间隙上锁)组合，同时锁住数据，并锁住数据前面的间隙Gap。在RR隔离级别下支持。

行锁

InnoDB实现了以下两种类型的行锁：

1. 共享锁(S)：允许一个事务去读一行，阻止其他事务获得相同数据集的排它锁。
2. 排他锁(X)：允许获取排他锁的事务更新数据，阻止其他事务获得相同数据集的共享锁和排他锁。

S(共享锁) X(排他锁)
S(共享锁) 兼容 冲突
X(排他锁) 冲突 冲突
SQL 行锁类型 说明
insert，update，delete … 排他锁 自动加锁
select 不加任何锁
select … lock in share mode 共享锁 需要手动select之后加上lock in share mode
select … for update 排他锁 需要手动在select之后for update

1. 针对唯一索引进行检索时，对已存在的记录进行等值匹配时，将会自动优化为行锁。
2. InnoDB的行锁是针对于索引加的锁，不通过索引条件检索数据，那么!nnoDB将对表中的所有记录加锁，此时 就会升级为表锁。

间隙锁：

默认情况下，InnoDB在REPEATABLE READ事务隔离级别运行，InnoDB使用next-key锁进行搜索和索引扫描，以防止幻读。
1.索引上的等值查询（唯一索引)，给不存在的记录加锁时，优化为间隙锁。
主键索引，1，3，8。
给5加索引，就会给3，8之间加入间隙锁。
插入id7 就会阻塞

2.索引上的等值查询(普通索引)，向右遍历时最后一个值不满足查询需求时，next-keylock退化为间隙锁。
非唯一索引，如果有多个数值为3的
会对3之前的加上间隙锁，对后面之后第一个不为3，如7的之间加上间隙锁

3.索引上的范围查询（唯一索引)--会访问到不满足条件的第一个值为止。
where age>19,数据种有11，19，25
会对11之后加上索引

InnoDB引擎

逻辑存储结构

一张图说明：

image.png

架构

image.png

内存架构

image.png

image.png