Batina's Blog

[动态规划笔记] 3 - 最长递增子序列

leetcode 300 的经典动态规划问题，求一个数组中最长递增子序列的长度。 $O(n^2)$的解法： dp数组元素dp[i]表示第i个元素参与构成的最长递增序列的长度； 状态...

Posted by Dongbo on March 5, 2022

[db] 3 - 日志恢复系统

数据库日志恢复系统的笔记 概念1 事务的原子性要求事务对数据库的修改要么能够全部成功应用，要么把已经修改的部分全部撤回，恢复到该事务执行之前的状态。但是如果在一个事务在执行过程中发生...

Posted by Dongbo on March 4, 2022

[动态规划笔记] 2 - 矩阵合集

leetcode 上动态规划 tag 下碰到几道矩阵的题目，记录一下解题思路。 leetcode 221 leetcode 1277 leetcode 764 // TODO leet...

Posted by Dongbo on March 3, 2022

[动态规划笔记] 1 - 01背包

一些笔记 先以纯01背包百练 2773的问题作为示例 首先是开辟二维dp数组的写法。dp[i][j]的含义为：i代表使用了[0~i]个物品计算的结果；j表示大小为j的背包能够装下的最...

Posted by Dongbo on February 23, 2022

[缓存替换策略] LRU & LFU

引 - 缓存替换策略 首次接触缓存替换算法，是大二的操作系统课，讲内存页面替换的时候（操作系统概念第七版第9章）。因为时间太久了，所以翻教材回忆了一下当初学的替换算法都有哪些。 最优替...

Posted by Dongbo on February 21, 2022

[db] 2 - Two Phase Locking（2PL）

整理两阶段锁的笔记，来填以前的坑了 2PL 理论部分 如之前所说，2PL是一种悲观的并发控制手段，通过使用2PL我们可以保证事务的可串行化。其规则说起来很简单，我们将一个事务生命周期...

Posted by Dongbo on February 17, 2022

[db] 1 - Transaction

整理数据库事务概念的笔记 教材1上给出“事务”的定义为：访问并可能更新各种数据项的一个程序执行单元。另外这里也给出一个更好理解的事务定义：A transaction is the ex...

Posted by Dongbo on February 14, 2022

[随笔集] 猫和狗

只是一些生活感触而已 农村老家养了一条狗，到现在大概三四岁，就是普通的土狗，我妈把它捡回来养的时候它应该才几个月大，但是等我寒假回家的时候已经挺大一只了。平时就是伯伯奶奶吃完饭喂它点粥...

Posted by Dongbo on February 1, 2022

[tinyky] Debug日志 （1）

记录实现tinykv遇到的各类bug和解决方案 1（project2b）client查询时发现一部分应用成功的put请求，没有查询到对应的value 出错原因 ...

Posted by Dongbo on January 22, 2022

[共识算法] 1 - Raft Basic

0. 引 在什么应用场景下我们需要分布式共识算法，是否还有其他的解决方案 当我们的应用场景从单机数据库转向分布式数据库时，我们需要考虑如何保证分布式事务的ACID性质。在单个节点上我...

Posted by Dongbo on January 13, 2022