算法

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 题目 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/super-ugly-number 编写一段程序来查找第 n 个超级丑数。超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。 示例 输入: n = 12, primes = [2,7,13,19] 输出: 32 解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32]。 说明: 1 是任何给定 primes 的超级丑数。 给定 primes 中的数字以升序排列。 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。 第 n 个超级丑数确保在 32 位有符整数范围内。 解题思路1 由于这是一道中等难度的题目，萌叔第一想到的是穷举，从1开始穷举，1、2 3、… N 判断每个数是否是超级丑数。这个思路肯定是没错的，结果提交后发现超时了。超时的原因是扫描了太多无用的数据。 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 前言 xtaci/kcp-go的作者，在KCP标准协议的基础上做了扩展，增加了加密和FEC（Forward error correction，前向纠错）那么前向纠错到底是干什么用的 2. reed-solomon算法概述 在xtaci/kcp-go中，FEC的实现使用的是reed-solomon编码(实现库为klauspost/reedsolomon)，这是一种诞生于上个世纪60年代的一种纠错码。详细的解释见参考资料1 原始数据如下图所示 它由4个piece组成, “ABCD” “EFGH” “IJKL” “MNOP”, 每行当做一个piece。 reed-solomon算法构造了一个编码矩阵(别问萌叔怎么构造，反正是挺深奥的数学问题)，使得这个矩阵与原始矩阵相乘以后，得到的新矩阵。可以观察出来，新矩阵的前4个piece与旧矩阵完全相同，剩余的2个piece，被叫做parity, 权且翻译为校验块吧。 即使新矩阵丢失了2个piece 在等式2边乘以编码矩阵的逆矩阵，就可以消去编码矩阵，重新恢复出原始数据 3. reed-solomon算法结论总结 包含有n个symbol的消息可以通过reed-solomon算法，得到包含 n + k 个 symbol的新消息。任意丢失至多k个symbol，原始消息仍然能够被恢复出来。这里symbol和piece的概念类同。 因为reed-solomon算法的这个特性，它被广泛的用于 1）DVD、CD、二维码 碟片即使有部分被刮花，仍然能够播放 二维码即使部分被遮挡，仍然能够识别 2）远距离空间传输 空间探测器在向地球发送数据包时，每个包的传输可能需要耗费几个小时，传输过程中，极有可能由于其他陨石遮挡等原因，造成丢包。有了reed-solomon算法，丢失的包可以被直接恢复出来，不需要再重传。 3）存储系统，比如 minio 甚至萌叔发现它在 minio/minio 一个支持Amazon S3协议的对象存储系统中也有使用 缺点 增加了额外的存储和传输量，另外在做数据恢复时，有额外的计算开销。 4. FEC KCP协议中前向纠错相关的字段是这样设定的，它和块加密一样，都是可选的 FEC TYPE: typeData = 0xF1 原始数据块 typeParity = 0xF2 校验数据块 FEC SEQID: 递增的计数器 +-----------------+ | SESSION | +-----------------+ | KCP(ARQ) | +-----------------+ | FEC(OPTIONAL) | +-----------------+ | CRYPTO(OPTIONAL)| +-----------------+ | UDP(PACKET) | +-----------------+ | IP | +-----------------+ | LINK | +-----------------+ | PHY | +-----------------+ (LAYER MODEL OF KCP-GO) 注意 和网络分层模型一样，FEC只对自己这层负责，FEC对自己的数据包中到底存的是什么并不感兴趣。因此校验数据块中的数据应该被理解为2进制数据，它们是不能按照ARQ被解析的。 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 前言 最近打算给我的博客做个性化推荐，初步选定使用关联规则算法来实现。 常见关联规则算法又有Apriori算法、FP-树频集算法、Eclat算法 3种。 请务必阅读参考资料1，了解Support(支持度), Confidence(置信度)， Lift（提升度） Association rules are usually required to satisfy a user-specified minimum support and a user-specified minimum confidence at the same time. Association rule generation is usually split up into two separate steps: A minimum support threshold is applied to find all frequent itemsets in a database. A minimum confidence constraint is applied to these frequent itemsets in order to form rules. While the second step is straightforward, the first step needs more attention. ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 前言 在Golang中strings模块Index原型如下 func Index(s, substr string) int Golang中 substr长度大于64/32(视CPU的情况而定)的情况， 查找采用的rabin-karp算法，它是由Richard M. Karp和 Michael O. Rabin在1987年提出的。（1987年就这么牛了，还让人活不活） 该算法的实际应用是检测抄袭 2. 点评 假定s长度为n, substr长度为m 它的时间复杂度为O(n + m)，最坏情况下的时间复杂度为O(n * m)。 KMP算法的时间复杂度也是O(n + m), 可见它的速度并不慢 它的相比于KMP算法的最大优势是，实现简单，易于理解 2.1 以下是暴力算法的伪码 function NaiveSearch(string s[1..n], string pattern[1..m]) for i from 1 to n-m+1 for j from 1 to m if s[i+j-1] ≠ pattern[j] jump to next iteration of outer loop return i return not found 2.2 以下是rabin-karp算法的伪码 function RabinKarp(string s[1..n], string pattern[1..m]) hpattern := hash(pattern[1..m]); for i from 1 to n-m+1 hs := hash(s[i..i+m-1]) if hs = hpattern if s[i..i+m-1] = pattern[1..m] return i return not found 大家可以看出rabin-karp算法其实是暴力算法的改进版， 简单的说: 就是先匹配Pattern的哈希值，如果hash值相同，才实际进行字符串匹配(line 4/5/6) ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 题目 给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组。 实例1: 输入: [0,1] 输出: 2 说明: [0, 1] 是具有相同数量0和1的最长连续子数组。 实例2 输入: [0,1,0] 输出: 2 说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。 解题思路 注意 数组中只会有0、1 两种数据 相同数量的 0 和 1 的最长连续子数组中肯定包含有相同数量的0和1 这里我们要利用0和1数量相同，互相抵消的特性 如果我们把0都当做-1， 1还是1，沿着数组求和，对于以下数组 [0, 1, 1, 0, 1, 1, 1, 0] 我们可以想到如果2个位置(i, j)之间有相同数量0和1的最长连续数组, 那么这2个位置的sum(i) == sum(j) 这里要注意的是，对于数组初始的sum值是0，我们可以记为sum(-1) = 0 要找到最长连续子数组，只需找到sum值相同，且位置相距最大的情况即可 最终代码 find_max.go func findMaxLength(nums []int) int { // sum -> index // 存最小值 cache := map[int]int{} cache[0] = -1 sum := 0 res := 0 for i := 0; i < len(nums); i++ { if nums[i] == 0 { sum -= 1 } else { sum += 1 } if _, ok := cache[sum]; ok { index := cache[sum] res = max(i-index, res) } else { cache[sum] = i } } return res } func max(a int, b int) int { if a < b { return b } else { return a } } 请我喝瓶饮料

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc leecode 上第851题 1. 题目如下 在一组 N 个人（编号为 0, 1, 2, …, N-1）中，每个人都有不同数目的钱，以及不同程度的安静（quietness）。 为了方便起见，我们将编号为 x 的人简称为 “person x “。 如果能够肯定 person x 比 person y 更有钱的话，我们会说 richer[i] = [x, y] 。注意 richer 可能只是有效观察的一个子集。 另外，如果 person x 的安静程度为 q ，我们会说 quiet[x] = q 。 现在，返回答案 answer ，其中 answer[x] = y 的前提是，在所有拥有的钱不少于 person x 的人中，person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。 示例： 输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0] 输出：[5,5,2,5,4,5,6,7] 解释： answer[0] = 5， person 5 比 person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。 唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7， 但是目前还不清楚他是否比 person 0 更有钱。 answer[7] = 7， 在所有拥有的钱肯定不少于 person 7 的人中(这可能包括 person 3，4，5，6 以及 7)， 最安静(有较低安静值 quiet[x])的人是 person 7。 其他的答案也可以用类似的推理来解释。 2. 提示 2.1 思考 对于示例，我们能够根据richer信息得出如下关系 我们能够得到富有程度的关系如上图 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 问题描述 如下图所示，从矩阵(m*n)的(0， 0)出发，然后只能向下、向右，到达矩阵的对角（m-1, n-1） 求从(0,0)到(m-1, n-1) 一共有多少种走法 解题思路 解决这个问题，我们可以参考动态规划的思想 要到达(m-1, n-1), 就必须到达(m-2, n-1)或者(m-1, n-2) 从(m-2, n-1)到(m-1, n-1) 只有一种走法 从(m-1, n-2)到(m-1, n-1) 只有一种走法 那么从(0, 0)到(m-1, n-1)的走法数量 f(m-1, n-1) = f(m-2, n-1) + f(m-1, n-2) 递归算法 采用递归算法可以很容易写出代码 def try_walk(m, n): if m == 1 and n == 1: return 0 return walk(m -1, n -1) def walk(x, y): if x == 0 and y == 0: return 1 res = 0 if x - 1 >= 0: res += walk(x - 1, y) if y - 1 >= 0: res += walk(x, y - 1) return res if __name__ == '__main__': print (1,1), try_walk(1, 1) print (1,2), try_walk(1, 2) print (2,2), try_walk(2, 2) print (2,3), try_walk(2, 3) print (3,3), try_walk(3, 3) 参考动态规划的思想，可以记录cache (x,y)到(0,0) 走法的数量，加快速度 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 问题描述 蛇形遍历矩阵 按下图的方法蛇形遍历矩阵 矩阵为m行n列 解题思路 观察可以发现 结论1. 在矩阵中移动的动作 只有以下4种 4种动作，对应的向量分别为 1）(0，1) 2) (1, -1) 3) (1, 0) 4) (-1, 1) 结论2 对于动作1和动作3 最多连续走一步 对于动作2和动作4，保持动作到矩阵边界 结论3 如果要变换方向则按照上次动作的Next动作开始尝试 沿着动作1、动作2、动作3、动作4的顺序进行尝试 完整程序 # -*- coding: utf-8 -*- actions = [(0,1), (1, -1), (1,0), (-1, 1)] def snake(matrix, m, n): # start # (0, 0) # end # (m - 1, n - 1) pos = (0, 0) num = 1 matrix[pos[0]][pos[1]] = num last_action_idx = None while pos != (m-1, n-1): num += 1 print "***************" print "current pos=", pos print "prepare to num", num, last_action_idx print "last action", last_action_idx print # 尝试走出一步 if last_action_idx is None: last_action_idx = 0 # 尝试继续按原动作前进且下一个位置也是合法的 # 继续走 elif last_action_idx in set([1, 3]) and valid(matrix, pos, actions[last_action_idx], m, n): pass else: # 必须要换方向 for i in xrange(4): last_action_idx = (last_action_idx + 1) % 4 if valid(matrix, pos, actions[last_action_idx], m, n): break print "execute action", last_action_idx action = actions[last_action_idx] pos = (pos[0] + action[0], pos[1] + action[1]) print 'track', pos, num matrix[pos[0]][pos[1]] = num def valid(matrix, pos, action, m, n): pos = (pos[0] + action[0], pos[1] + action[1]) # 不能超过边界，且从来没有走过 if pos[0] >= 0 and pos[0] < m and pos[1] >= 0 and\ pos[1] < n and matrix[pos[0]][pos[1]] == 0: return True return False def print_matrix(matrix): for line in matrix: for item in line: print item, print print '-' * 10 if __name__ == '__main__': matrix = [] matrix.append([0,0,0]) matrix.append([0,0,0]) matrix.append([0,0,0]) matrix.append([0,0,0]) snake(matrix, 4, 3) print "result", '=' * 10 print_matrix(matrix) 总结 这类问题的核心是寻找规律，规律找到了，问题也就迎刃而解了。与之类似的还有螺旋遍历2维数组。 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 问题描述 在一个有序整型数组中，从其中任意挑2个数(不重复)相加等于目标值target 求所有这样的组合 比如有以下数组 case1: target=6 [1, 2, 3, 4, 5, 7, 9] 返回结果为 [(1,5), (2,4)] case2: target=6 [1, 7, 9] 返回结果为 [] case3: target=9 [1, 2, 3, 4, 5, 7, 9] 返回结果为 [(2,7)] 解题思路 对这个问题，我们可以这样思考，以case1 为例 如果对于1, 可以从右向左找，可以找到5，与1相加可以等于目标值6 这时候再看2有没有合适的值能够与之相加等于目标值的时候，我们只需要找 [3, 4]就可以了，这是因为左边的数增大了，右边已经查找过的数，显然已经太大 方案 1）设2个指针分别指向数组的最左和最右 2) 移动右边的指针直到无法找到合适的值或者已经找到合适的值 3）移动左边的指针 4）持续步骤2和3，直到左右2个指针重合 时间复杂度为O(n) 完整代码: def find(array, target): i = 0 j = len(array) - 1 res = [] while i < j: while i < j and array[j] > (target - array[i]): j -= 1 if (array[i] + array[j]) == target and i != j: res.append((i, j)) i += 1 return res def main(): a = [1,2,3,4,5,7] print find(a, 6) a = [1,7,9] print find(a, 6) a = [1, 2, 3, 5, 7, 9] print find(a, 9) if __name__ == "__main__": main() 请我喝瓶饮料

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 题目 查找二叉树的最近公共祖先 示例如下: 节点6和节点8的最近公共祖先是节点4 节点2和节点5的最近公共祖先也是节点0 节点4和节点7的最近公共祖先也是节点4 思路 1）采用中序遍历(先左子树-> 根 -> 右子树) 可以得到每个节点在树中的层级 2）扫描2个目标节点之间所有节点，层级最小的节点，即为最近公共祖先 ancestor.cpp #include <iostream> #include <stack> #include <vector> using namespace std; #define MAX_VALUE 1000000 struct node{ int data; struct node* lchild; struct node* rchild; }; typedef struct node Node; int levels[100]; int lca(Node* root,int m,int n){ Node* p = root; vector<int> v; stack<Node*> s; int level = 0; cout<<"中序遍历:"<<endl; while(p||!s.empty()){ if(p){ s.push(p); levels[p->data]=level; p = p->lchild; level++; }else{ p = s.top(); level = levels[p->data]; s.pop(); cout<<p->data<<" "; v.push_back(p->data); p = p->rchild; level++; } } cout<<endl; cout<<"节点对应层级:"<<endl; for(int i=0;i<v.size();i++){ cout<<levels[v[i]]<<" "; } cout<<endl; int minLevel = MAX_VALUE; int res = -1; bool flag = false; for(int i=0;i<v.size();i++){ if(v[i]==m||v[i]==n){ if(levels[v[i]]<minLevel){ res = v[i]; minLevel = levels[v[i]]; } flag = !flag; }else if(flag){ if(levels[v[i]]<minLevel){ res = v[i]; minLevel = levels[v[i]]; } } } return res; } int main(){ Node node0={0,NULL,NULL}; Node node1={1,NULL,NULL}; Node node4={4,NULL,NULL}; Node node2={2,NULL,NULL}; Node node3={3,NULL,NULL}; Node node5={5,NULL,NULL}; Node node6={6,NULL,NULL}; Node node7={7,NULL,NULL}; Node node8={8,NULL,NULL}; node0.lchild = &node1; node0.rchild = &node4; node1.lchild = &node2; node1.rchild = &node3; node4.lchild = &node5; node4.rchild = &node8; node5.lchild = &node6; node5.rchild = &node7; int n = 0; n = lca(&node0,6,8); cout<<"节点6和节点8的最近公共祖先是"<<n<<endl; n = lca(&node0,2,5); cout<<"节点2和节点5的最近公共祖先是"<<n<<endl; n = lca(&node0,4,7); cout<<"节点4和节点7的最近公共祖先是"<<n<<endl; } 输出 中序遍历: 2 1 3 0 6 5 7 4 8 节点对应层级: 2 1 2 0 3 2 3 1 2 节点6和节点8的最近公共祖先是4 中序遍历: 2 1 3 0 6 5 7 4 8 节点对应层级: 2 1 2 0 3 2 3 1 2 节点2和节点5的最近公共祖先是0 中序遍历: 2 1 3 0 6 5 7 4 8 节点对应层级: 2 1 2 0 3 2 3 1 2 节点4和节点7的最近公共祖先是4 PS 2012年写的练习小程序 ...