版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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 ≤… 继续阅读 算法题 LEECODE 313. 超级丑数

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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协议的对象存储系统中也有使用 缺点 增加了额外的存储和传输量,另外在做数据恢复时,有额外的计算开销。… 继续阅读 玩转KCP(4)-FEC(前向纠错)

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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… 继续阅读 关联规则算法-Eclat

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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… 继续阅读 Golang strings中的Index函数(字符串查找)

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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,… 继续阅读 算法题 leecode 525.连续数组

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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… 继续阅读 算法题 leecode 851. 喧闹和富有

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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 ==… 继续阅读 算法题(9)

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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)]… 继续阅读 算法题(8)

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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,… 继续阅读 算法题(7)

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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;… 继续阅读 查找二叉树的最近公共祖先