Pistachio's Blog

Later equals never.

【行为型】观察者模式

一、定义定义对象间的一种一对多（变化）的依赖关系，以便当一个对象的状态发生改变时，所有依赖它的对象都得到通知并自动更新。二、结构使用面向对象的抽象，Observer模式使得我们可以独立地改变目标与观察者（通过add/remove），从而使二者之间的依赖关系达致松耦合。目标发送通知时，无需指定观察者，通知会自动传播。观察者自己决定是否需要订阅通知，目标对象对此一无所知。......

Posted by Liao on 2023-01-12

【行为型】策略模式

一、定义策略模式定义了一系列算法，把它们一个个封装起来，并且可以使它们可相互替换（变化）。该模式使得算法可独立于使用它的客户端程序（稳定）而变化。二、结构 Strategy及其子类为组件提供了一系列可重用的算法，从而可以使得类型在运行时方便地根据需求在各个算法之间进行切换。 Strategy模式提供了用条件判断语句(if/else)以外的另一种选择，消除条件判断语句，就......

Posted by Liao on 2023-01-12

最长回文子串

求最长回文子串是面试中常考的题目，这道题有三种解法：动态规划、中心扩展法和Manacher算法。给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。示例 1： 123>输入：s = "babad">输出："bab">解释："aba" 同样是符合题意的答......

Posted by Liao on 2023-01-11

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