最长上升子序列(LIS)的定义:    一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN),我们可以得到一些上升的子序列(ai1, ai2, …, aiK),这里1 <= i1 < i2 < … < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8). 三种求解方法: 1. O(n^2)的DP 2. O(nlogn)的二分+贪心法 3. O(nlogn)的树状数组优化的DP 题目:Longest Increasing Subsequence 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2, 继续阅读 >>


刘生玺 18/07/20 12:10:14
题目:不同路径 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。 问总共有多少条不同的路径? 例如,上图是一个7 x 3 的网格。有多少可能的路径? 说明:m 和 n 的值均不超过 100。 示例 1: 输入: m = 3, n = 2 输出: 3 解释: 从左上角开始,总共有 3 条路径可以到达右下角。 1. 向右 -> 向右 -> 向下 2. 向右 -> 向下 -> 向右 3. 向下 -> 向右 -> 向右 示例 2: 输入: m = 7, n = 3 输出: 28 原题链接:https://leetcode-cn.com/explore/interview/card/top-interview-questions-medium/51/dynamic-programming/105/ 继续阅读 >>


刘生玺 18/07/19 11:15:47
1. 感性认识“动态规划” 1. 基本概念    是求解决策过程(decision process)最优化的数学方法。把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,是一种解决这类过程优化问题的新方法。 2. 使用技巧:    动态规划算法通常用于求解具有某种最优性质的问题!!!特别的 ,动态规划(Dynamic Programming)对于子问题重叠的情况特别有效,因为它将子问题的解保存在表格中,当需要某个子问题的解时,直接取值即可,从而避免重复计算! 3. 基本思想与策略 我们通过一个问题来引出: 提问:动态规划与分治法有什么不同?    答:适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题 继续阅读 >>


刘生玺 18/07/18 19:02:57
全排列算法思想: 1. 全排列的定义和公式:    从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。由排列的定义,显然不同的顺序是一个不同的排列。从n个元素中取m个元素的所有排列的个数,称为排列数。从n个元素取出n个元素的一个排列,称为一个全排列。 公式:全排列数f(n) = n! (定义0!=1) 2. 时间复杂度:    n个数(字符、对象)的全排列一共有n!种,所以全排列算法至少时间O(n!)的。如果要对全排列进行输出,那么输出的时间要O(n∗n!),因为每一个排列都有n个数据。所以实际上,全排列算法对大型的数据是无法处理的,而一般情况下也不会要求我们去遍历一个大型数据的全排列。 3. 全排列的初始思想    为了解决一个算法问题,我们选择从基本的想法做起。先回顾一下我们自己是如何写一组数的全排列的:1,3,5,9 首先肯定是 : 1 ,[3, 5,9的全排列] 3 继续阅读 >>


刘生玺 18/07/17 11:08:08
结构化与非结构化网络 非结构化的P2P网络是指网络节点之间不存在组织关系,节点之间完全是对等的,比如第一代P2P网络Napster。 结构化的P2P网络与非结构化恰好相反,我们认为网络在逻辑上存在一个人为设计的结构,比如Chord假定网络是一个环,Kadelima则假定为一颗二叉树。有了这些逻辑结构,就给我们资源查找引入了更多的算法和思路。 引言 我们在 计算机网络–详解P2P对等网络(一)—BitTorrent协议 这一篇博客中讲述了BT下载的过程:在对等用户拿到种子文件的时候,首先会联系tracker服务器,然后加入用户集群,并在用户集群中寻找自己所需的内容,最后与拥有内容的对等用户进行联系。 从BT下载的过程中引出本节所要讨论的问题:如何高效的从用户集群中找出哪些对等用户拥有你正在寻求的具体内容? 在历史中有三种比较典型的模型来解决这个问题: Napster:使用一个中心服务器接收所有的查询,服务器告知去哪下载其所需要的数据。存在的问题是中心服务器单点失效导致整个网络瘫痪。 继续阅读 >>


董恒毅 18/06/28 21:24:59
注:本篇博客只是讲述了一致性哈希的思想,我们会在之后讲述分布式哈希表以及一致性哈希的一种实现(Chord算法)。 什么是一致性哈希算法? 引用自维基百科: 一致性哈希是一种特殊的哈希算法。在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对 K/n个关键字重新映射,其中K是关键字的数量,n是槽位数量。然而在传统的哈希表中,添加或删除一个槽位几乎需要对所有关键字进行重新映射。 总结:一致性哈希算法主要关注的是在分布式架构中,当节点数目发生变化的时候(增加/删除),怎样使再哈希的数据量最少。 一致性哈希的引出 在分布式系统中,节点的宕机、某个节点加入或者移出集群是常事。对于分布式存储而言,假设存储集群中有10台机器(node),如果采用传统Hash方式对数据分片(item)(即数据根据哈希函数映射到某台机器上存储),哈希函数应该是这样的:hash(item) % 10。根据上面的介绍,当node数发生变化(增加、移除)后,数据会被重新“打散”,导致大部分数据不能落到原 继续阅读 >>


董恒毅 18/06/26 21:06:58
页面置换算法 在进程运行过程中,若需要访问的物理块不在内存中,就需要通过一定的方式来将页面载入内存,而此时内存很可能已无空闲空间,因此就需要一定的算法来选择内存中要被置换的页面,这种算法就被称为页面置换算法。页面置换算法的好坏,将直接影响系统的性能。 一个好的页面置换算法,应做到减少页面置换的频率。尽量将以后不会用到的或较长时间不会使用的页面给置换出。 下面介绍几种常用的页面置换算法。 1. 最佳置换算法 该算法是一种理想化的算法,具有非常好的性能,但是由于目前无法预知未来,因此难以实现。 该算法选择淘汰的页面是:未来永远不会再使用的页面 or 未来最长时间不再被访问的页面。该算法保证了可以获得最低缺页率,但无法预知未来页面的使用情况,因此目前无法实现,但通常用来评价其他算法。 例:假定系统为某进程分配了三个物理块,并考虑有以下的页面号引用串: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 进程运行时,先将 7,0,1 三个页面装入内存。以 继续阅读 >>


王良 18/06/10 22:34:17
零:使用STL自带的函数(less与greater) vector<int> v{45,2,5,8454,34,68421,5,84,1,5}; sort(v.begin() ,v.end(),less<int>());//从小到大 sort(v.begin() ,v.end(),greater<int>());///从大到小 一:普通比较函数 假设有一个vector<<\string>>,你的任务是统计长度小于5的string的个数,如果使用count_if 函数的话,代码就是这样: bool LengthIsLessThanFive(const string& str) { return str.length() < 5; } int res=count_if(vec.begin(), vec.end(), LengthIsLessThanFive); 继续阅读 >>


刘生玺 18/05/24 18:05:04
前言 银行家算法,是我们OS课上的一个非常重要的知识点,感觉可以说是必考题了,但是考试嘛,考过了以后不用就会忘,每次都要重新复(yu)习一遍,又非常麻烦,正好前段时间有机会实现了一遍,赶紧总结下,避免以后又忘了。 正文 银行家算法简介 银行家算法(Banker’s Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死结产生的演算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。 (来自wiki) 这里的重点是避免!!! 避免!!! 避免!!! 针对死锁这种坑爹的情况有预防和避免两种大的解决思路,之前总是傻傻分不清楚。这里我们还是通过一个生动的例子来解释吧。 女朋友:康康啊,预防感冒,冲杯板x根吧。 康康:好滴。 女朋友:康康啊,出门系上我给你织的围巾吧,避免感冒。 康康:好几。 感受到预防和避免的差异了嘛,预防就是提前做好准备,而避免则是在实际操作中小心翼翼。 回到死 继续阅读 >>


康艺杰 18/05/21 16:09:33
前言 对于学通信的人来说,在学到数字信号处理时都会学到一个东东,叫做快速傅里叶变换(Fast Fourier Transform,简称FFT)。这东西真的挺有用的,但是只要有那么一点用的东西,就是特别难的。(现在也有很多不完整的地方,以后再补充~) 什么是FFT FFT,即为快速傅氏变换,是离散傅氏变换的快速算法,它是根据离散傅氏变换的奇、偶、虚、实等特性,对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现,但是对于在计算机系统或者说数字系统中应用离散傅立叶变换,可以说是进了一大步 FFT是一种用来计算DFT(离散傅里叶变换)和IDFT(离散傅里叶反变换)的一种快速算法。这种算法运用了一种高深的数学方式、把原来复杂度为O(n2)" role="presentation">O(n2)O(n2)O(n^2) 的朴素多项式乘法转化为了O(nlogn)" role="presentation">O(nlogn)O(nlogn)O(nlogn)的算法。 首先上DFT的公 继续阅读 >>


殷健翔 18/05/15 09:40:22