最长公共子序列

概念

序列的子序列,可以由从这个序列中去掉0个或多个元素而得来。所以子序列
可以是由其父序列中不连续的元素组成,但相对顺序不能改变。公共子序列
的是,假如序列Z既是X的子序列,又是序列Y的子序列,那么称Z为X和Y的公共子序
列。两个序列最长的公共子序列就被称之为最长公共子序列。最长公共子序列,
又被称之为最长公共子串,译自英文名Longgest Common Subsequence,可以缩写
为LCS。求最长公共子序列是一个很有用的问题,它可以用来分析两段序列的相似
度,比方可以用来分析DNA串的相似度,也可以分析两段文字的相似度,来判断是
否剽窃,等等。

Read More

动态规划基础

前一篇笔记有过一个动态编程的实例——rod cutting。这篇笔记主要了解动态
规划的基础理论和弄清楚何时运用动态规划。对于何时来运用动态规划来寻得问
题的解,取决于两个重要因素:最优子结构和重叠子问题。

Read More

动态规划笔记(1)——Rod cutting

动态规划(dynamic programming),与“分治思想”有些相似,都是利用将问题分
为子问题,并通过合并子问题的解来获得整个问题的解。于“分治”的不同之处在
于,对于一个相同的子问题动态规划算法不会计算第二次,其实现原理是将每一
个计算过的子问题的值保存在一个表中。

Read More

Qt Quick 笔记(2)——用户界面相关

Nested ELements

在QML中的 UI 元素是以树形结构组织的,因此“Elements are often nested”——也就是说,
一个元素可以包含很多个其它元素。

Read More

Qt Quick 笔记(1):初识 Qt Quick

废语开篇

在大二的时候思索着学习一界面库,为此煞费脑经。其中有试过十来天的Qt学习,不过最后为
WPF而沦陷,确实WPF界面与逻辑的分离让我很是向往。不过可惜的是WPF并不原生支持与C++
的交互,以致我不得不学习一些C# 。又四处求医问药——获得native code与manage code交互
的良方。这之间寻寻觅觅,虽然也算终于达成所愿——可以用C++与WPF 来完成一些小程序编写
了。但是这注定是一种非主流的配置,主流与否,我虽然不在意。只是结果并不如我想的那般
理想。用C++与WPF来开发并没有带来效率的提升以及逻辑的简化——这些成本都被转移到了他们
之间的交互上,更大的成本其实在于学习的代价——C#、C++/cli 、P/invoke… 有意思的是似乎
转了一圈,又要回到QT上来。为什么要回到QT? 没有太多理由——公司用的最主要的界面库就是
Qt。当然这一切并未有让我有哪怕些须遗憾。我一直坚信,所有的弯路都有其价值。何况win8
确切会支持C++与xaml的交互——我已经尝试了一下。但是对于相关的系统学习可能要推后一些了。
而Qt会是接下来不短一段时间的主旋律了。不过可喜之处在于,Qt Quick 甚合我意。

Read More

又到离别时

捡起《北回归线》脱落的最后一页看完,不免有一些默然。这没有什么值得奇怪的地方 ,看过的很多书都曾有这样的感觉。但这一次却又有一点不一样,它更像是一种静默中 的歇斯底里。有一种不吐不快,吐了也不能畅快的无力。这他妈的发慌发堵的感觉。

老实说,看之前我已经做好了领略它到底有多淫秽,多龌龊的打算。毕竟它原是一本西 方的禁书,毕竟它原是一本在一群精力旺盛的兵痞间传阅的黄书,它理当应该很黄色, 应该能让这群士兵在无人的角落都成为单手“炮兵”。一直到看完最后一个字,我才大呼 受骗,这哪可能被当做黄书。它不但不淫秽,简直很纯洁。后来我又醒悟过来,既然是 中文版,必然在出版之前已经完成“净身”。

Read More

扩展数据结构

在一般的应用中,极少有可能要构建一种全新的数据结构,大部分情况下会使用
一些已有的数据结构,或者已有的数据结构进行扩展,以使得其能支持特殊的功
能。当然即便是扩展也需要做一些工作。

动态顺序统计(Dynamic order statistics)

关于顺序统计这个问题,在中位数和顺序统计量介绍了在O(n)时间内获
取一组数据中第i小的数据。在算导第十四章介绍了另外一种方式来求第i
的数据,它的算法复杂度为O(lgn),但却要依赖于另外一种数据结构顺序统
计树(order statistic tree)。

Read More

在没有父指针情况下的红黑树插入操作

13.3-6
Suggest how to implement RB-INSERT efficiently if the representation for red-black trees includes no storage for parent pointers.

Read More

C++实现红黑树,仿STL封装

在[Chapter 13 Red-Black trees(红黑树)][]这篇笔记中对红黑树的各种操作都有较详尽的伪码,
相信使用C++来实现也并不是难事,我要做的是,在实现的基础上要进行一定的封装。当然风格嘛,
自然参照STL,最终的结果就是要实现一个STL风格的红黑树模板。

Read More

Chapter 13 Red-Black trees (红黑树)

之前的二叉搜索树提供了一系列算法复杂度为O(h)的基本操作:SEARCH,
MINIMUM, MAXIMUM, INSERT, DELETE SUCCESSOR and
PREDECESSOR。无疑,当树的高度比较小的时候这些操作有很好的效率,然而当二叉树总是“一条脚站立”时,树的高度就会很高,此时它效率并不会比链表快。红黑树即是一种从二叉搜索树上发展而来的“平衡”搜索树,它能保证在最坏情况下上述操作的复杂度为
O(lgn) .

Read More