Pistachio's Blog

Later equals never.

Brian Kernighan算法

Brian Kernighan是一种位移运算的算法，将n和n-1按位与后，n最右边的1会被清除。故用于清除二进制串中最右边的1。 1n & (n - 1) ...

Posted by Liao on 2023-01-11

字符串DP题目总结

1. LC72. 编辑距离给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符示例 1： 123456输入：word1 = "horse", word2 = "ros"输出：3解释：horse -> ror......

Posted by Liao on 2023-01-10

LIS题目总结

LIS (Longest Increasing Subsequence)最长递增子序列，通常使用动态规划求解。 1. LC647. 最长连续递增序列给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。连续递增的子序列可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i ......

Posted by Liao on 2023-01-10

MVCC

一、定义MVCC (Multiversion Concurrenct Contiol) 多版本并发控制，通过数据行的多个版本（undo log）管理来实现数据库的并发控制二、实现原理隐藏字段、Undo Log版本链、ReadView 隐藏字段 trx_id：事务id roll_pointer Undo Log版本 ReadViewReadView是事务A在使用MVCC机制进行快照读操作......

Posted by Liao on 2022-09-26

STL之list集合

一、定义list的底层是双向链表，通过指针进行数据访问。相对于vector，list能高效地在任何地方插入和删除。二、用法12345list<Type> list;list<Type>::iterator itlist.push_back()list.insert()list.erase() 三、应用根据身高重建队列 123456789101112131415......

Posted by Liao on 2022-09-09

组合数

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。计算并返回可以凑成总金额的硬币组合数。输入：amount = 5, coins = [1, 2, 5]输出：4解释：有四种方式可以凑成总金额：5=55=2+2+15=2+1+1+15=1+1+1+1+1 12345678910111213......

Posted by Liao on 2022-08-25

分布式系统

当执行锁操作时，涉及不同的线程可能不知道彼此的状态。对于另外一些线程，它们只希望获取到数据而不受到其它线程的干扰，因此线程之间也需要交流以等待对方的数据，通常叫协作。协程间的通信，称为Coordination，Go中提供了几种方法实现： channel Sync.cond() 若有些线程停在那里，你想每隔一段时间发一个信号，但你不确定线程是否在等你。若它在等，就给它发一个ticket，它......

Posted by Liao on 2022-07-26

MySQL日志

一、Redo Log1.1 定义Redo log是物理日志，记录事务提交时，数据页的物理修改（具体存放了什么数据），用于实现事务的持久性。 1.2 作用保证事务的持久性。保证内存中和磁盘中数据的一致性，当刷新脏页到磁盘，发生错误时，进行数据恢复。 1.3 操作原理Redo Log由重做日志缓冲 (Redo Log buffer) 和重做日志文件 (Redo Log file) 组成。前者......

Posted by Liao on 2022-07-04

下一个排列的实现

整数数组的下一个排列，是指下一个字典序更大的排列，如123下一个排列是132 以下算法思想是c++ next_permutation的实现以【1,2,3,8,5,7,6,4】的下一个排列为例 1234567891011121314151617181920212223242526272829class Solution {public: void nextPermutat......

Posted by Liao on 2022-07-01

go Map

一、定义1a := map[string]string{} map类型的变量本质上是一个指针，指向hmap结构体 /runtime/map.go hmaphmap是哈希表 1234567891011121314type hmap struct { count int // （记录已经存储的键值对的数量） # live cells == size of ......

Posted by Liao on 2022-06-22