迭代所有最短長度字符串的算法？

我正在做一個URL縮短器，我想爲每個給定的URL使用盡可能最短的字符串。每個網址將有不同的到期日期。迭代所有最短長度字符串的算法？

例如，讓我們提交得到縮短爲以下列表中的URL：

a, b, c, ..., z, 0 ..., 9, aa, ab, ac, ... a9, ba

然後說c到期，所以接下來的URL縮短爲c，而不是bb，因爲c較短並沒有被採取。

什麼樣的數據結構對於追蹤這個很好？

2016-04-27 Cisplatin

這是一個有趣的問題。你需要幾個數據結構。這是我會做的。

1）哈希表，以短URL作爲鍵，以及所有URL信息（完整URL，到期時間等）作爲值。

2）過期網址的最小堆。這將允許您快速獲取並重新使用可用的最短網址。

3）一個字符串，用於跟蹤正在使用的最長的短URL。這樣，如果沒有過期時間較短的用戶，可以快速生成新的URL。

4）有些東西要記錄到期時間，所以你可以有效地過期URL。它可以是日期 - > ShortURL形式的哈希表，並具有有序的鍵，因此您可以輕鬆獲取下一個到期的URL。

2016-04-28 00:01:40 Macondo2Seattle

我會使用一個優先級隊列，其比較器有嵌套規則，第一個是空的或採取的標誌，第二個是在字符串上。請記住，PQ會將您最熱門的對象放在隊列頂部。作爲結果的對象應該是字符串名稱和布爾標誌的組合。

2016-04-28 00:02:37 mohsenmadi

中PQ是行不通的對於任何數量的參賽作品來說，都必須有一個限制。 – Cisplatin

不是我所知道的。 PQ是[unbounded]（https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html），除非它以編程方式設置爲某個限制。 – mohsenmadi

你說得對，實際上有一個簡單的方法。另一個問題是，如果添加了大量元素，那麼他們永遠處於PQ中，佔用大量空間。我想我可以定期清除它們。 – Cisplatin

我會使用2堆。

當你需要一個新的URL，從堆1.當URL過期頂部拉出，從堆2拉URL，並將其插入到堆1

2016-04-28 00:52:06

回答