SF
csRyan的学习专栏
csRyan的学习专栏
注册登录
关注博客
注册登录
主页
关于
RSS
算法题解:从条形图中找出最大矩形(扫描过程中维护信息树/信息栈)
csRyan
2018-01-22
阅读 3 分钟
2.8k
一开始,我尝试通过枚举所有左右边界,来依次计算夹在其中的最高矩形的面积,但是很快发现这种方式非常低效。由于左右边界没有提供关于高度的信息,每次枚举出一对左右边界以后,还要遍历两个边界之间的所有条形(O(n)),才能找出矩形可以达到的最大高度。并且,所有左右边界的组合达到n^2量级。总的时间复杂度将达到O(...
算法题解:找出给定表达式所有可能的计算次序(递归分治改进为动态规划)
csRyan
2018-01-20
阅读 3 分钟
1.9k
题目链接:[链接]从表面上看,题目问有多少种方式为表达式增加括号,实际上等价于找出表达式所有可能的计算次序,每一种画括号的方式一一对应于一种计算次序。
算法题解:Count of Smaller Numbers After Self (归并排序的妙用)
csRyan
2018-01-16
阅读 5 分钟
4.1k
在上一篇题解中,我们介绍了如何通过在扫描输入的过程中维护一个有序的数据结构来为新输入的计算提供信息。但是我们同时也发现,支持相关操作的容器(既能够进行二分查找又能够在常数时间内插入元素)似乎没有;如果自己构造一棵二叉搜索树,也会烦恼于树的平衡问题。
算法题解:Count of Smaller Numbers After Self (巧用排序、二叉树)
csRyan
2018-01-16
阅读 4 分钟
5.5k
最直接的方法,拿到一个数x以后,依次遍历x右边的所有数并与x比较,对小于x的数字进行计数,计数的结果就是在x右边、比x小的数字。容易看出,这个方案的时间复杂度是O(n^2),不是很理想。上面方法对时间的浪费体现在:完全没有利用已经计算得到的信息,把所有可以做的比较都做了一遍。如果我们在拿到x之前已经通过比较知...
算法题解:找出包含给定字符的最小窗口(枚举的一般方法)
csRyan
2018-01-10
阅读 3 分钟
1.5k
如何使我们的枚举能够不重复、不遗漏呢?要做到不重不漏地枚举,我们需要为每一种可能枚举出的元素定义一种“大小判断”,然后定义“如何从一个元素求出稍微大一些的下一个元素”(从当前的枚举迁移到下一个枚举)。最后,我们只要从最小到最大按序枚举,就能够保证不重不漏。
算法题解:最小编辑距离(动态规划算法)
csRyan
2018-01-09
阅读 2 分钟
10k
为了使用动态规划算法,要先将父问题分解成子问题(父问题和子问题是同一种问题,只不过分解得到的子问题规模更小)。那么现在就需要我们找出父问题和子问题之间的转移关系。推导父子问题之间的转移关系有2中思路:
算法题解:经典的动态规划问题——最长递增子序列(二)
csRyan
2018-01-08
阅读 6 分钟
7.7k
在上一篇博客中,我们介绍了最长递增子序列(LIS)问题的一个动态规划算法,时间复杂度为O(n^2)(如果使用二叉树能降低到O(nlogn))。在这篇文章我们再分析一个O(nlogn)的巧妙算法。思路来自:[链接]
算法题解:经典的动态规划问题——最长递增子序列(一)
csRyan
2018-01-08
阅读 2 分钟
22.7k
这也属于搜索问题。我们首先想象最长递增子序列(LIS)具有什么样的特征,然后根据这种特征来扫描输入。如果存在某个数字X比某个已有的递增子序列的最后一个元素E要大,且X在E的右边,那么X就可以添加到这个递增子序列的末尾,从而使递增子序列的长度更大。等等,某个已有的递增子序列又是哪个子序列呢?我们希望,这个...
算法题解: 42. Trapping Rain Water (扫描数据和下标移动的技巧,计算类问题)
csRyan
2018-01-08
阅读 2 分钟
2.2k
题目连接:[链接]如果只是从数组的左边扫描到右边,不可能在这种单向扫描时知道:在当前扫描到的的地板上方能够装多少水。因为能装多少水依赖于当前地板的两边的地形,而单向扫描时无法知道当前地板右边的地形。因此我们需要从两边向中间扫描。
[Angular, TypeScript, 路由算法] 模拟IP层路由协议,实现LS算法、洪泛算法、DV算法、路由毒化
csRyan
2018-01-07
阅读 5 分钟
6.4k
链路状态协议(Link-state routing protocol)和距离向量路由协议(Distance-vector routing protocol)是分组交换(Packet switching)网络中最主要的两种路由协议。本项目的模拟路由器实现了LS路由算法、LS广播洪泛、DV路由算法,以及防止DV路由环路和无穷计数问题的策略。此外还实现了完整的前后端以便研究者通过UI界...
算法题解:实现正则表达式 '.' 和 '*' 的匹配(动态规划)
csRyan
2017-11-15
阅读 3 分钟
6.6k
经过思考,难点主要在于*究竟应该匹配多少个字符。因为*并不是匹配越多字符越好(不能贪婪匹配):比如模式a*abc中的a*只能匹配aaabc的aa。如果a*匹配了aaa,那么剩余的模式abc(a*abc减去开头的a*)就无法匹配剩余的字符串'bc'。换一种说法,如果a*匹配3个a,a*a(4个a)无法匹配aaabc的任何前缀。同理,如果匹配的字符...
算法题解:对于输入数字串,给出另一种数字排列,使得字典序增加尽可能小
csRyan
2017-11-08
阅读 2 分钟
2.2k
题目分析 题目链接:31. Next Permutation 这题让我们找到比输入数字排列恰好大一点点的数字排列。对这个问题的算法不仅适用于数字串,而且适用于任何有字典序的符号串。 为了方便讨论,我们将输入数字串称为串1,输出数字串称为串2。 输出的串2需要满足以下条件: 字典序增大。字典序增大当且仅当:串2与串1从最高位的...
算法题解:查找由'('和')'组成的字符串中,所有的合法括号子串
csRyan
2017-10-30
阅读 4 分钟
4k
输入的字符串s由'('和')'组成,其中存在一些子串是合法的括号字符串。比如(()())是合法的括号字符串;()())(())就不是合法的括号字符串,但是其中的()()和(())是合法的括号字符串。
【响应式布局】理解设备像素、设备独立像素和css像素
csRyan
2017-10-27
阅读 6 分钟
6.3k
设备像素指的是显示器上的真实像素,每个像素的大小是屏幕固有的属性,屏幕出厂以后就不会改变了。设备分辨率描述的就是这个显示器的宽和高分别是多少个设备像素。设备像素和设备分辨率交给操作系统来管理,浏览器不知道、也不需要知道设备分辨率的大小,浏览器只需要知道逻辑分辨率就可以了。
算法题解:从数组中搜索和为x的三元组
csRyan
2017-10-26
阅读 2 分钟
5.6k
搜索最佳结果的一个一般思想:先想象这个最佳结果必定具有什么样的特征,然后我们通过这些特征来查找,不断找出很多“候选最佳结果”,最后从这些候选结果中选拔出最佳的结果。
Angular进阶:Angular编译机制(AOT、JIT)
csRyan
2017-10-15
阅读 16 分钟
21.7k
2018年2月17日更新:最近又做了2个小Demo用来研究Angular的编译和打包,基于Angular5,一个使用rollup,一个使用webpack,(rollup目前无法做到Angular的lazy loading)。不仅项目文件结构非常简洁,而且使用ngc(Angular compiler)的输出作为打包的输入,这意味着:你不仅可以修改ts代码然后查看ngc输出有何变化,而且可以...
算法题解:从字符串中查找最长的回文子串(搜索最佳结果的一般方法)
csRyan
2017-10-09
阅读 3 分钟
5.4k
搜索最佳结果的一个一般思想:先想象这个最佳结果必定具有什么样的特征,然后我们通过这些特征来查找,不断找出很多“候选最佳结果”,最后从这些候选结果中选拔出最佳的结果。
不要拘泥于消费者思维,成长为一名生产者
csRyan
2017-10-08
阅读 1 分钟
2k
大部分人永远都是在手机上寻找一个个APP去使用,而不会去思考为什么这个APP要这么设计,为什么登录时候要绑定微信微博,为什么产品下一次要这么更新。而一旦你思考过这些,这也就说明了你有了产品经理的思维——你形成了生产者的萌芽。很多人终其一生,都活在消费着观念里,他们按照社会大多数人规定好的、最舒服和最没风...
算法题解:用DFS(递归)寻找树中的最大权值路径
csRyan
2017-10-02
阅读 2 分钟
6.1k
不难分析出,最大的路径是“^型”的,从一个最高点向下延伸的两条路径组成一个“^型”路径。注意这个“最高点”不一定是树的根。并且,这两条路径必定分别经过左右子节点,并且是向下路径中权值最大的。由于每个节点都有可能是“最高点”,因此对于每个节点(可以用DFS/BFS遍历每个节点),我们都要计算出以该节点为“最高点”的最...
算法题解:从输入string中找出无重复字符的最长子串
csRyan
2017-09-24
阅读 2 分钟
4k
这道题目主要难点在于这样一个问题:a, b, c, d, e, f, c, g, h, ...我从第一个字符开始检查,已经检查到f了,目前为止还没有出现重复字符:[a, b, c, d, e, f,] c, g, h, ...检查到下一个c时,发现它在前面已经出现过了(至于如何判断新字符是否已经出现过,我们在下面讨论):[a, b, c, d, e, f, c,] g, h, ...这时应...
算法题解:合并k个已排序的链表
csRyan
2017-09-17
阅读 4 分钟
4.2k
不断取出值最小的那个Node(因为每个list已经排序,所以这一步只需要找出最小的head Node),添加到已排序链表的尾部,直到所有lists的所有Node都取完。
算法题解:从2个已排序数组中找到第k小的数字
csRyan
2017-09-09
阅读 3 分钟
4.8k
leetcode题目链接设给出的两个已从小到大排序的数组为nums1和nums2,size1=nums1.size(),size2=nums2.size()。分析题目可以知道,要找到中位数,最好能从2个已排序数组中找到第k小的数字,后者是更具一般性的问题。
你真的了解JavaScript的Promise吗?
csRyan
2017-09-08
阅读 11 分钟
3.3k
Promise代理了一个可能要在未来才能到达的值[[PromiseValue]]。Promise的一个最重要的特点是,你可以通过then来指定当[[PromiseValue]]到来时(或到来失败时)调用的handler。
1
2
3
(current)
上一页
3
(current)
下一页