| by msbeta | No comments

数据结构与算法-计算二叉树中节点的最大距离

1.问题定义

如果把二叉树看做无向图,我们姑且定义二叉树的“距离”为节点之间边的个数。现在要计算二叉树中相距最远的两个节点之间的距离。

二叉树的节点距离计算有几种情况:

1) 根节点为空,路径长度为0;

2) 根节点非空的情况下,分为两种情况:

情况A: 路径经过左[……]

继续阅读

Read More
| by msbeta | No comments

动态规划-最长公共子序列

1.公共子序列

给定两个字符串m和n,如果它们的子串a和b内容相同,则称a和b是m和n的公共子序列。子串中的字符在原字符串中不要求连续,只要保持原有相对顺序即可。

例如,字符串“abcfbc”和“abfcab”,其中“abc”同时出现在两个字符串中,因此“abc”是它们的公共子序列。

[……]

继续阅读

Read More
| by msbeta | No comments

数据结构排序算法-堆排序

1.什么是堆排序

堆排序是利用堆这种数据结构设计的一种排序算法。它的最好、最坏、平均的时间复杂度都是nlogn,是一种非稳定排序算法。

2.什么是堆

堆(heap)是计算机科学中一类特殊的数据结构的统称,它满足以下的性质:

1) 堆中某个节点的值总是不大于或不小于其父[……]

继续阅读

Read More