Batina's Blog

[动态规划笔记] 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

[c++/STL] sort, stable_sort, partial_sort, nth_element

这次我们来讲讲 C++/STL 里的排序算法。最后混进来的 nth_element 是选择算法，以$O(n)$的平均时间复杂度返回第 n 小的元素（若有重复元素则是排序后 n-th 位置上的元素...

Posted by Dongbo on January 1, 2022

[年终总结] 再见，2021

年终报告快轮到我了，到底还是没法静下心看代码，趁这个时间把2021的年度总结起个头吧。 以前我从来没想过要做年度总结的，看到别人的博客、朋友圈和空间里年末或者年初时发的总结总感觉无聊和浪费时间...

Posted by Dongbo on December 30, 2021