一种结合链表和优先队列的优雅解法,巧妙之处在于使用优先队列出队元素,可以直接得到下一个入队元素,算法复杂度是O(nlgn)。联想到如果不是优先队列结构,那么我们可以使用同样的解法,只是我们需要在队列中记录每个元素属于哪一行,而使用链表结构就避免了这种麻烦。
PengChao
LeetCode_126: Word Ladder II
最近总是Rank到很难的题目,这次遇到了LeetCode中通过率最低的题目。这道题目是一个图相关的问题,同时牵扯到很多坑,很多细节,即使思路正确稍不注意内存超出,时间超出都是常事儿,自己做出来还是需要废一番功夫的。博主写了BFS算法的大概就放弃了,后面翻了几份代码,找了个最简洁的 ,这里也只能讲解一下别人的代码了。
LeetCode_085: Maximal Rectangle 动态规划
这道题很难想,主要有两种解法,一种是把这道题目转化成之前那道(#084)直方图面积计算的题目,使用栈来做,但是还有更优雅的方法,使用DP。这两种方法的时间复杂度都是O(mn),空间复杂度都是O(n)。
LeetCode_084: Largest Rectangle in Histogram
经典的题目,最开始没想到这种解法,只想着用优先队列去解了,看了下答案,大概有两种解法,一种是DP,另一种是维护一个栈,这种解法应该是见过最好的了。惯例,贡献高质量解法。
LeetCode_039: DFS与Combination Sum系列问题
LeetCode的39和40两道题都是CombinationSum,它们都可以用深度优先搜索(DFS)来解决(当然也还有许多其它方法)。这篇博客就系统的来介绍DFS和CombinationSum这一类问题。
LeetCode_011: Container With Most Water
这道题的重点是对双指针过程的分析,典型的双指针类型题目,博主的代码速度为16ms,战胜90%的答题者,思路比较一般,不过还是分享一下。
MatConvNet进行FCN语义分割
FCN语义分割算法已经在很多主流深度学习平台上实现了,包括Caffe、TenserFlow、MatConvNet等。这篇博客主要介绍如何在MatConvNet上运行起FCN语义分割,包括CPU和GPU版本。博主的平台是Matlab2017a+Cuda8.0。
LeetCode_218: The Skyline Problem
Skyline是一个经典问题了,一开始博主思考先进行高度排序,从高到低来确定关键点。事实上通过优先队列来获取当前位置的最大高度,沿着x轴来遍历是最好的。这篇博客提供了一份19ms的答案,战胜了97%,当然是从讨论区淘出来的,博主没想到这么优秀的方法。
MFC动态设置CEdit、CStatic文字颜色和背景颜色(修改控件方式)
MFC的控件常常需要动态的改变文字颜色和背景底色,最好的做法是修改控件本身,增加设置颜色的接口函数直接调用,进行控件颜色的修改。CtlColor是反射式消息的响应函数,在控件内部自己实现重绘,这种方式是最好的。与反射式消息修改控件本身不同,还有另一种方式使用OnCtlColor在控件父窗口类中增加代码修改颜色,这两种方式都可以实现颜色的修改。这篇博客主要介绍反射式消息的方式。
LeetCode_313: Super Ugly Number
这道题一种普遍的解法是动态规划。但是同样是动态规划,也有优劣之分。这篇博客贡献一份36ms(80%+)的答案,推荐这份答案不仅是因为速度,还是因为这种思路十分清晰,当然也可以参考讨论区中的7行的动态规划答案,也是十分优秀的。
LeetCode_373: Find K Pairs with Smallest Sums
寻找K个最大组合,博主最开始使用BFS来做的,算法复杂度$latex O(mn)$,计算和$latex mn$,广度优先搜索$latex V+E = mn+(m-1)(n-1)$,速度13ms。此外,博主对DP的掌握一直不够熟练,顺便贴了另一种使用DP的搜索方法,也是13ms,其实两种思路是差不多的。[mathjax]
LeetCode_378: Kth Smallest Element in a Sorted Matrix
经典的数据结构问题,在算法导论堆排序的思考题中出现过这种结构的排序求解问题,该问题解法多样,很适合学习。
LeetCode_407: Trapping Rain Water II
一道很有意思的题目,题目是计算容器雨水积累量,实际上是利用广度优先搜索来不断收缩边界,计算雨水的积累。由于博主之前图一类的题目接触的比较少,这道题目看了一眼答案。这篇博客除了介绍这道题目本身,还将介绍stl中的优先队列priority queue,优先队列是广度优先搜索(BFS)必要的辅助。作为编程辅助,后面还顺便介绍了C++11的花括弧初始化。
图像跟踪(九)FCNT语义跟踪
刚有一个idea,用语义分割来做图像跟踪,搜了一下发现已经有人做过了,细细的看了下Paper,和自己相当还不一样。FCN是深度学习语义分割的鼻祖,而这片Paper的名字叫做FCNT,看了之后发现我误会了,此FCN非彼FCN,由于是比较早的算法了,性能和MEEM处于同一层次,不过考虑到这是深度学习方法用于跟踪的重要实践,还是做个笔记好了。
博主认为图像跟踪过程的本质就是语义的跟踪(我是这么理解的),所以,使用语义分割来完成图像跟踪是自然而然想到的。事实上深度学习用于图像跟踪,也就是利用了其深层特征中的语义信息。这篇博客就主要介绍这篇文献:Visual Tracking with Fully Convolutional Networks。
LeetCode_057: Insert Interval
这道题就是区间插入问题,目前看到的解法主要有三种,一种是直接分析区间重叠,具有O(n)时间和O(n)空间复杂度,另一种是用二叉搜索树来做,还有一种是借助了STL库中的equal_range方法来做,写法比较优雅。这篇博客主要给出第一种解法和第三种解法的代码
LeetCode_164: Maximum Gap
经典的线性时间排序问题,题目标签是hard,主要是要求了线性时间内解决问题,那么很自然想到基数排序和桶排序了。除此之外还有一种常用的线性时间排序,计数排序可以看做间隔为1的桶排序,在数字比较集中且可转化为整数时比较有效,因此计数排序不适合本题目。