1

我被问到一个问题：

给定一个字符串列表和一个查询列表：START 和 END，它们都是字符串。我必须找到 [START, END) 范围内的字符串数

例如：字符串A, AA, AB, CD, ZS, XYZ 列表：查询列表：

A, AA
A, CC
AB, ZZ
AC, CD

输出应该是：

1
3
3
0

我解决这个问题的方法是：在遍历字符串列表时，我通过一一插入新字符串来创建 AVL 树。（起初，我使用了不平衡的 BST，但我得到了时间限制。）在进行比较时，我使用 java String 中的 compareTo 函数。

创建 AVL 树后，我运行从 [start, end) 开始计数的查询。我的方法是

1. let v = root.

2. if v==null -> return 0 

   else if v.value < start -> count(v.right)

   else if v.value >= end -> count(v.left)

   else 1 + count(v.right) + count(v.left)

但是，我仍然有时间限制 :(

因此，我通过散列成双精度来创建散列函数来改变方法，而不是使用 compareTo，而是比较散列值。

但是，我还有时间限制！

因此，我将子树大小的值存储到每个顶点中，而不是使用计数或时间，而是添加更多条件语句，其中一些可以使用子树的大小而不是递归调用计数函数。

对我有什么建议让它在特定时间运行吗？:\

4

1 回答 1

0

使用订单统计树：http ://en.wikipedia.org/wiki/Order_statistic_tree

它基本上是一个修改后的平衡 bst，其中每个节点存储其子树的大小，它允许您回答有关在 log(n) 时间内给定项目之前有多少项目的查询。

于 2013-08-24T09:39:27.673 回答