LeetCode_210: CourseScheduleII 拓扑排序

这道题与前一版本207一样,只不过前一版本要求判断是否有环,而当前版本还要给出可行顺序,那么这个问题就自然而然的归为拓扑排序了。这篇博客将对有向图和无向图中是否存在环这一问题进行归纳,并且给出一个较为简洁的拓扑排序代码。拓扑排序,简单的说就是不断将度为0的点提取出来,提取的顺序就是拓扑排序。在算法导论中,给出了DFS和BFS解法,其中DFS采用完成时间倒序作为拓扑排序,我们需要了解拓扑排序问题的解法是多样的,这篇博客给出的代码不算唯一的。

阅读更多

算法的嵌入式移植(一)C代码优化

一般C/C++的算法代码不适合直接移植到嵌入式设备,需要做一些优化和处理。一方面是出于速度考虑,另一方面是针对嵌入式设备支持的语言特性差异进行修改,还有就是硬件上的考虑,比如就定点DSP而言,就需要将原来的浮点运算进行转化。

近期博主在整理以往笔记,就将算法嵌入式移植这部分差分成两个章节,一是C代码优化部分,二是DSP代码移植部分,第一章节是语言层面的一般而言是适合所有嵌入式设备的,第二章节是和DSP开发环境相关方面的。特此整理,谨供参考。

阅读更多

OpenCV特征点提取算法对比

除了我们熟知的SIFT、SURF、ORB等特征点提取算法,OpenCV中还提供了十余种特征点提取算法。最近在整理以往的ppt和报告,看到其中一页ppt,发现已经忘得差不多了,就再写篇博客复习下好了,这篇博客注重对比,技术方面的内容不会太过细致,希望能有帮助。当然,文章末尾会提供这些算法OpenCV调用的实例代码。
首先,引发内容的就是下面这张ppt:(不要注意Why Surf了,当时根据具体应用场景所做的选择)左边一栏是特征点的数目,右边一栏是检测的速度,数据是在博主自己的测试集(大概四五百张图片)上测试的。

阅读更多

点云数据处理方法概述

结束目标跟踪的研究,回到课题上,接下来要面对的就是点云数据的处理了。这篇博客主要介绍三维计算机视觉中点云数据处理面对的问题,主要方法和技术,概述其特点。这篇博客主要介绍最基本的点云数据处理技术和概念,不会有任何代码。

ICP点云配准就是我们非常熟悉的点云处理算法之一。实际上点云数据在形状检测和分类、立体视觉、运动恢复结构、多视图重建中都有广泛的使用。点云的存储、压缩、渲染等问题也是研究的热点。随着点云采集设备的普及、双目立体视觉技术、VR和AR的发展,点云数据处理技术正成为最有前景的技术之一。PCL是三维点云数据处理领域必备的工具和基本技能,这篇博客也将粗略介绍。

阅读更多

LeetCode_174: Dungeon Game 动态规划

做了一道很有意思的题目,要求是从左上角开始,在HP不掉到0的情况下,到达右下角。虽然明显是使用动态规划来解,但是其中隐藏了一些技巧 。这里,如果从左上角开始进行DP将使得问题复杂化,技巧就是反向,从终点开始反向DP,这篇博客将详细这种方法的应用条件。

阅读更多

LeetCode_134: Gas Station

这道题目可以使用一般的DP来做,但是博主想到的方法更加直接:对于判断是否存在解,直接把数组累加,如果和非负,那么必然存在一个位置,使得从这个位置开始进行累加的所有结构都非负。在进行累加的过程中,找到累加和最小的位置,从这个位置的下一个位置开始,就可以保证在累加过程中,累加曲线的最小值最大(想象积分曲线的过程,积分的终点sum相同,一个先下降再上升,一个先上升再下降)。有点绕,多想想 :)

阅读更多

LeetCode_068: Text Justification

又是一道通过率不过20%的题,总结这种通过率比较多的题目,发现其中很多原理并不难,导致通过率比较低的原因是各种极端情况,还有就是题目理解和表述不够清晰。比如自己实现Atoi,如果列出要处理的各种情况,写出来并不难。这道题也是一样,其实没什么难度,只是有些情况下,具体说来就是最后一行或者一行的最后一个单词,需要特殊处理。

阅读更多