Lei Xia

How to build a Finite State Machine to help business workflow

May 4, 2023 · 785 words · 4 min

This is the first article written in English. In this article, I’ll share how to build a Finite State Machine(FSM) to help business workflow transition, such as auditing.

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition

Wikipedia - Finite-state machine

MySQL、Redis、Aurora读书笔记

May 3, 2023 · 134 words · One minute

本文分享一下五一期间的读书感悟，包括MySQL、Redis、Aurora。

修复M1使用gomonkey提示permission defined错误

April 20, 2023 · 20 words · One minute

问题 Go单元测试在M1上使用github.com/agiledragon/gomonkey/v2 v2.9.0包提示permission defined。 网上查阅消息得知是由于内存安全导致，不能同时对内存进行写和执行 解决方法 下面分享一种比较简单的方法，需要修改本地的go源码。 修改go/pkg/mod/github.com/agiledragon/gomonkey/[email protected]/modify_binary_darwin.go的modifyBinary方法。 将 err := mprotectCrossPage(target, len(bytes), syscall.PROT_READ|syscall.PROT_WRITE|syscall.PROT_EXEC) 修改为 err := mprotectCrossPage(target, len(bytes), syscall.PROT_READ|syscall.PROT_WRITE)

拓补排序

February 10, 2023 · 150 words · One minute

在计算机科学领域，有向图的拓扑排序或拓扑测序是对其顶点的一种线性排序，使得对于从顶点$u$到顶点$v$的每个有向边$uv$, $u$在排序中都在$v$之前。 例如，图形的顶点可以表示要执行的任务，并且边可以表示一个任务必须在另一个任务之前执行的约束；在这个应用中，拓扑排序只是一个有效的任务顺序。 当且仅当图中没有定向环时（即有向无环图），才有可能进行拓扑排序。 任何有向无环图至少有一个拓扑排序。 算法 遍历有向边，构造u->v边中v的入度表，可使用哈希存储入度 将入度为0的节点入队 队列节点不断出队，出队时减小被更新节点的入度，如果被更新节点入度为0，则该节点入队 重复以上过程，最终可以得到一个从入度为0到最终节点的序列，这就是拓补排序算法。 示例 Leetcode 210. 课程表2 class Solution { // 生成邻接表 <当前节点，后置节点> // 进行BFS拓补排序，由最低依赖的开始写入答案 public int[] findOrder(int numCourses, int[][] prerequisites) { Set<Integer>[] graph = new HashSet[numCourses]; for (int i = 0; i < numCourses; i++) { graph[i] = new HashSet<>(); } // 入度 int[] inDegree = new int[numCourses]; for (int[] p : prerequisites) { int current = p[0]; int pre = p[1]; graph[pre].

水塘抽样算法

January 19, 2023 · 100 words · One minute

下面是维基百科水塘抽样的说明。 水塘抽样是一系列的随机算法，其目的在于从包含 $n$个项目的集合 中选取$k$ 个样本，其中 $n$为一很大或未知的数量，尤其适用于不能把所有 $n$ 个项目都存放到内存的情况。 本文分享在随机数据流中等概率抽取target的水塘抽样算法。 算法 定义$count$计数变量 遍历给定的数据流，如果当前数字等于$target$, $count$+1 在$[0, count]$产生随机数，如果等于$count$，则抽样成功 示例 Leetcode 398. 随机数索引 代码 class Solution { // 哈希表保存<值,List<下标>> private final int[] nums; private final Random random; public Solution(int[] nums) { this.nums = nums; this.random = new Random(System.currentTimeMillis()); } // 水塘抽样 // 统计target count,随机数%count 为0时重置index public int pick(int target) { var count = 0; var index = 0; for (var i = 0; i < nums.

时间差计算算法

January 19, 2023 · 103 words · One minute

本文分享如何解决计算时间差类的问题。 算法 首先需要将时间转化为数字，比如23:59，可以转化为23*60+59 然后根据数字从小到大排序，此时从[0, n]处的数据有序，可以遍历该区间计算差值 需要注意的是，由于时间的特殊性，比如23:59下一分会归0，因此还需要比如0处和n处的时间差 示例 Leetcode 539. 最小时间差 代码 class Solution { // 模拟 // 时间字符串转化为数字 // 排序，线性遍历，然后再比较第一个和最后一个的差值 public int findMinDifference(List<String> timePoints) { // 24小时总共1440个可能，超过1440，直接返回0（存在重复时间点） if (timePoints.size() > 1440) { return 0; } var array = new int[timePoints.size()]; for (int i = 0; i < timePoints.size(); i++) { var str = timePoints.get(i); array[i] = Integer.parseInt(str.substring(0, 2)) * 60 + Integer.parseInt(str.substring(3)); } Arrays.sort(array); var answer = Integer.MAX_VALUE; for (int i = 1; i < array.

滑动窗口算法

January 19, 2023 · 128 words · One minute

滑动窗口算法是查找连续区间常用的算法之一。 本文分享滑动窗口算法的通用框架。 算法 定义$left$和$right$双指针，代表窗口的左边界和右边界 当$right$小于给定区间大小时，我们可以进行操作。 在扩大窗口时，需要加当前新加入的数据进行处理 当当前窗口内数据不满足条件时，右移$left$指针缩小窗口 计算$[left,right]$之间的数据，和最佳答案比较并更新最佳答案 右移$right$ 下面是滑动窗口通用框架的java语言实现。 int left = 0; int right = 0; while(right < 上界) { 将right处数据加入窗口 while(窗口数据不符合要求) { 移除left数据 left++ } 根据当前right和left计算最佳答案并更新 right++ } 示例 Leetcode 3. 无重复字符的最长子串 思路 基于算法框架的思路如下： 定义$left$和$right$双指针，代表窗口的左边界和右边界，再定义HashMap<Character, Integer>存储窗口内的字符和数量(可以使用长度为128的字符数组代替，省去操作hashmap的开销。 当$right$小于$s.length()$时，我们可以进行操作。 在扩大窗口时，将$s.charAt(right)$加入HashMap 当HashMap.get(s.charAt(right)>1)，此时$right$处字符重复，需要收缩左边界，$left$处的字符数量-1，右移$left$ 计算$[left,right]$之间的数据，和最佳答案比较并更新最佳答案 代码 class Solution { // 滑动窗口 // 定义left,right, hashmap<char,int> // 循环条件 right<s.length() // right字符入map // while刚才入的字符重复，map移除left的字符，left++ // 计算长度 // right++ public int lengthOfLongestSubstring(String s) { var left = 0; var right = 0; var answer = 0; var map = new int[128]; while (right < s.

字符串子序列检测算法

January 5, 2023 · 63 words · One minute

本文分享一种检测一个字符串是否为另一个字符串子序列的算法。 子序列的定义： 若字符串$s1$可以由字符串$s2$删除某些字符得到，则$s1$是$s2$的子序列。换句话说，若$s1$的所有字符都在$s2$中且顺序一致，则$s1$是$s2$的子序列。 例如： a是aaa的子序列，adf是abcdef的子序列，但是cba不是abc的子序列（因为字符顺序变了）。 算法 声明$s1$的下标变量$strIndex$，若$s2$有$s1$的该字符，则$strIndex+1$ 若遍历过程中$strIndex$和$s1$的长度相等，则证明$s1$所有字符都在$s2$中，返回$s1$是$s2$在子序列 遍历结束仍未返回，证明$s1$不是$s2$的子序列 代码 class Solution { public boolean isSubsequent(String str, String str1) { var strIndex = 0; // 逐字符遍历 // 如果字符想通，则strIndex++ // 如果strIndex到达末尾，则证明str是子序列 for (var i = 0; i < str1.length(); i++) { if (str.charAt(strIndex) == str1.charAt(i)) { strIndex++; } if (strIndex == str.length()) { return true; } } return false; } } 复杂度分析 时间复杂度：$O(n)$,$n$是$str1$的长度。 空间复杂度：$O(1)$。

计算数字二进制位中1的个数

January 5, 2023 · 48 words · One minute

本文分享一种计算给定数字二进制表示中有多少个1的算法。 位运算对于非硬件相关的开发者来说可能用的比较少，朴素做法是将数字转换为二进制字符串，然后遍历该字符串得到1的个数。 算法 通过右移我们可以访问到数字的指定比特 将该比特与1进行按位与&，结果为1则证明当前比特位是1，计数器+1 根据给定数字的数据类型可以确定需要位移的次数，对于int来说，4个字节，因此需要右移32次，而对于long来说，8个字节，需要右移64次。 代码 class Solution { public int getBit1Count(int num) { var count = 0; for (int i = 0; i < 32; i++) { if (((num >> i) & 1) == 1) { count++; } } return count; } } 复杂度分析 时间复杂度：$O(1)$，不管多大的数字，只需要右移32次。 空间复杂度：$O(1)$，无需额外空间。

解析字符串中的数字

January 3, 2023 · 108 words · One minute

本文分享一种如何在字符串中解析数字的算法。 思路 解析字符串中的数字需要判断当前是否是数字字符，以及如何处理连续的数字字符。 本文使用while循环来解析数字，之所以不使用for循环，是笔者认为while循环操控力比for循环要好。 while循环解析方法如下： 如果当前字符是数字，则开启内部while循环 内部while循环退出条件为当前字符不是数字 内部循环操作为读取当前数字，然后加上一个数字乘以10 内部循环退出后，我们就得到一个连续的数字 示例 Leetcode 2042. 检查句子中的数字是否递增 class Solution { // 提取字符串中的数字，判断是否严格递增 public boolean areNumbersAscending(String s) { // 定义上一个数字，初始化为最小的数字 var lastNumber = Integer.MIN_VALUE; var i = 0; while (i < s.length()) { if (Character.isDigit(s.charAt(i))) { // 当前是数字，继续处理 var number = 0; // 核心代码 while (i < s.length() && Character.isDigit(s.charAt(i))) { // 字符串没越界而且当前字符是数字字符 number = number * 10 + (s.charAt(i) - '0'); // (s.charAt(i) - '0') 就是利用ASCII码表直接得到数字值，不需要再做parseInt i++; // 坐标后移 } if (number <= lastNumber) { // 如果当前数字<=上一个数字，证明不是严格递增，return false return false; } // number > lastNumber，更新lastNumber lastNumber = number; } // i后移 i++; } return true; } } 复杂度分析