我太菜了

喜欢写Hello World的未来程序员.

309. Best Time to Buy and Sell Stock with Cooldown

我太难了

终是谁使弦断 花落肩头 恍惚迷离 C++，动态规划。 看评论区和题解，好像是有很多道类似的股票题，但这是我碰到的第一道，这种题一看就是dp，但最惨的是不知道怎么去推导和确定关系。 看了评论区和题解区的大佬题解，慢慢就懂了点了。 可以说是简单dp+状态机。 两种状态： 持有股票 不持有股票 一个dp数组对应一种状态，也就是用hold_dp数组记录当...

Posted by bbkgl on November 28, 2019

300. Longest Increasing Subsequence

我太难了

寒灯纸上梨花雨凉 我等风雪又一年 C++，动态规划。 动态规划 纯动态规划十分的简单，就是用数组dp记录上升序列的长度，dp[i]就表示以i为结尾的最长上升子序列，于是就能得到状态转移方程： \[dp(i) = max\{dp(i), dp(j) + 1\} ,j < i\] 用代码来表示也是非常简单，对每个元素，遍历在此之前的所有元素，然后看能不能以当前元素作...

Posted by bbkgl on November 27, 2019

287. Find the Duplicate Number

你快乐吗

掬水月在手 弄花香满衣 C++，二分法。 二分法 二分法的思路相当暴力，复杂度应该是O(NlogN)。 用[left, right]表示该重复数字表示的范围，左闭右闭区间。 然后用int mid = (left + right) / 2 ，然后计算小于等于mid的元素个数cnt，如果cnt > mid，说明处于[1, mid]之间的元素个数要大于mid，所以就说...

Posted by bbkgl on November 26, 2019

279. Perfect Squares

你快乐吗

从此无心爱良夜 任他明月下西楼 C++，dp背包，数学题。 dp（背包问题） 首先想到的就是dp，如果用数组dp来记录n由m个完全平方数组成的话，就是dp[n] = m. 对于数字n，可以进行分解，分解成某个数s和完全平方数的和，于是就有了dp[n] = dp[s] + 1 。 然后我们假设\(dp(n) \)表示数字\(n \)最少可以表示为\(dp(n) \)个完...

Posted by bbkgl on November 25, 2019

leveldb的整体设计

leveldb

船泊湘风晚 花谢烟雨迟 前面已经知道了leveldb存储数据的基本思路，然后介绍一下架构设计。 上一节说的大概就是这么个架构设计。 数据读写 写流程 知道整体思路和架构后，数据的写入流程就是： 按照WAL来，也就是先写Log再写数据 再把数据更新到Memtable，其实就是一个map 当Memtable的size超过一定限制的时候，就把Memtab...

Posted by bbkgl on November 24, 2019

leveldb的整体思路

leveldb

三十功名尘与土 八千里路云和月 关于leveldb的整体思路，已经有超级多的博客讲过了，这里我只是浏览了很多资料，然后综合一下，做一个易理解的阐述。 数据接口 leveldb的接口十分简单，对于用户来说其实就是只有几个。 static Status Open(const Options& options, const s...

Posted by bbkgl on November 24, 2019

240. Search a 2D Matrix II

你快乐吗

江头未是风波恶 别有人间行路难 C++，剑指offer原题。 对于题意提出的有规律的数组，可以有如下思路： 从二维数组的左下角开始查找； 如果当前位置大于target，则说明target不可能在当前位置所在行或所在行的下方，将范围缩小到当前所在行的上方，即将查找范围矩阵的行数缩小一行bottom–； 如果当前位置小于target，则说明target不可能在当...

Posted by bbkgl on November 24, 2019

238. Product of Array Except Self

你快乐吗

似此星辰非昨夜 为谁风露立中宵。 C++，数学题，想到了就一分钟写完哈哈哈。 其实就是一个公式，设\( ans(i) \)为除了\(i \)以外的乘积，\( f(i) \)为从\(0 \)到\(i \)的乘积, \( h(i) \)为从\(n-1 \)到\(i \)的乘积： \[ans(i) = f(i-1)h(n - i - 1) ​\] 最简单就是借助两个数组，一个...

Posted by bbkgl on November 24, 2019

leveldb的介绍和安装

leveldb

不向人间怨不平 相期浴火凤凰生 leveldb是谷歌开发的快速的KV数据库引擎，由Google传奇工程师Jeff Dean和Sanjay Ghemawat开发并开源。leveldb整体的设计比较巧妙，代码质量也有非常多的值得借鉴的地方，所以我打算阅读leveldb的源码，然后再自己撸一个KV数据库。 leveldb下载 现在的leveldb已经支持cmake了，所以可以先...

Posted by bbkgl on November 23, 2019

221. Maximal Square

我太难了

日出江花红胜火 春来江水绿如蓝。 C++，求LCA，有两种思路： 倍增法 根据“若R为P和Q的最近公共祖先，则P和Q一定位于R的不同子树上或者PQ之一等于R”这个理论（简称RPQ理论） RPQ理论 其实就是一种递归查找的策略，也不太区分是前/中/后序，按理说都可以的。 这里假设是前序，然后对于任一结点R，如果我们分别在其左子树和右子树中，则有三种可能： ...

Posted by bbkgl on November 23, 2019

FEATURED TAGS
Blog leetcode C++ 剑指offer http Raft Linux Hadoop 设计模式 CV 链表 动态规划 图 拓扑排序 快排 二叉树 leveldb 数学 数组 二分 dfs profile hash表 字符串 贪心 01背包 最小堆 单调栈 luajit 计算机网络 操作系统 共享内存 linux 原地哈希 双指针 滑动窗口 UE4 编译原理
ABOUT ME

写过Hello World, 下过矿。

✉️ zoujiakun@zju.edu.cn

FRIENDS