标签: data-structures

之前有一个类似的问题,但这里的问题与它相反,使用两个队列作为堆栈.问题......

鉴于两个队列与他们的标准操作(enqueue,dequeue,isempty,size),实现堆栈与它的标准操作(pop,push,isempty,size).

应该有两个版本的解决方案.

• 版本A:推送项目时堆栈应该是高效的; 和
• 版本B:弹出项目时堆栈应该是高效的.

我比任何特定的语言实现更感兴趣的算法.但是,我欢迎用我熟悉的语言表达的解决方案(java,c#,python,vb,javascript,php).

在Java中创建链表的最佳方法是什么？

我在算法书(Algorithms,第4版,Robert Sedgewick和Kevin Wayne)中遇到了这个问题.

队列有三个堆栈.实现具有三个堆栈的队列,以便每个队列操作采用恒定(最坏情况)的堆栈操作数.警告:难度很高.

我知道如何使用2个堆栈创建一个队列,但我找不到3个堆栈的解决方案.任何的想法 ？

(哦,这不是作业:))

因此,如果我必须在哈希表或前缀树之间进行选择,那么哪些区别因素会导致我选择一个而不是另一个.从我自己的天真的角度来看,似乎使用trie有一些额外的开销,因为它没有存储为数组但是就运行时而言(假设最长的键是最长的英语单词)它可以基本上是O (1)(就上限而言).也许最长的英文单词是50个字符？

获得索引后,哈希表会立即查找.然而,散列获得索引的关键似乎很容易接近50步.

有人能为我提供更有经验的观点吗？谢谢!

我正在尝试找到二叉搜索树的定义,并且我一直在寻找不同的定义.

有人说,对于任何给定的子树,左子键小于或等于根.

有人说,对于任何给定的子树,右子键大于或等于根.

我的旧大学数据结构书中说"每个元素都有一个键,没有两个元素具有相同的键."

是否存在bst的通用定义？特别是关于如何处理具有相同密钥的多个实例的树.

编辑:也许我不清楚,我看到的定义是

1)左<= root <右

2)左<root <=右

3)左<root <右,这样就不存在重复的密钥.

我正在探索这种HashSet<T>类型,但我不明白它在收藏中的位置.

可以用它来代替List<T>吗？我认为a的表现HashSet<T>会更好,但我看不到个人对其元素的访问.

它只用于枚举吗？

从学术上讲,数据结构Tree和Graph之间的本质区别是什么？那么基于树的搜索和基于图的搜索呢？

在ASP.NET C#中我有一个结构:

public struct Data
{
    public int item1;
    public int item2;
    public int category_id;
    public string category_name;
}

我有一份清单.我要选择category_id和category_name,运行的DISTINCT最后一个ORDERBY上category_name.

这就是我现在拥有的:

List<Data> listObject = getData();
string[] catNames = listObject
                    .Select(i=> i.category_name)
                    .Distinct()
                    .OrderByDescending(s => s)
                    .ToArray();

这显然只是获得了类别名称.我的问题是,我如何获得多个字段,以及将其存储在(不是a string[])中的数据结构？

编辑

使用结构列表并不是一成不变的.如果建议更改我的支持数据结构以使选择更容易(我将写很多这些),那么我很乐意接受建议.

我有一个类似的数据结构

public DespatchGroup(DateTime despatchDate, List<Products> products);

而我正在努力......

var list = new List<DespatchGroup>();

foreach (var group in dc.GetDespatchedProducts().GroupBy(i => i.DespatchDate))
{
    // group.Values is not correct... how do I write this?
    list.Add(new DespatchGroup(group.Key, group.Values);
}

我显然不理解,IGrouping因为我无法看到如何实际访问组内的数据记录!

假设我有一个n侧加载的模具,当我滚动它时,每个侧面k都有一些概率p _k.我很好奇是否存在静态存储此信息的良好算法(即,对于一组固定的概率),以便我可以有效地模拟模具的随机滚动.

目前,我有一个针对此问题的O(lg n)解决方案.想法是存储所有k的前k个边的累积概率的表,它们生成范围[0,1)中的随机实数并且对表执行二元搜索以获得其累积的最大索引值不大于所选值.我更喜欢这个解决方案,但运行时没有考虑概率似乎很奇怪.特别是,在一方总是出现或值均匀分布的极端情况下,可以使用朴素的方法在O(1)中生成滚动的结果,尽管我的解决方案仍然需要采用多个步骤的对数.

有没有人对如何以某种方式在运行时"自适应"的方式解决这个问题有任何建议？

编辑:基于这个问题的答案,我写了一篇文章,描述了这个问题的许多方法,以及他们的分析.看起来Vose的别名方法的实现给出了Θ(n)预处理时间和每次掷骰的O(1)时间,这确实令人印象深刻.希望这是对答案中包含的信息的有用补充!