Tag: 数据结构

给定n和k，返回第k个排列序列

集合[1,2,3，…，n]总共包含n！ 独特的排列。 通过按顺序列出和标记所有排列，我们得到以下序列（即，对于n = 3）： “123” “132” “213” “231” “312” “321”给定n和k，返回第k个排列序列。 例如，给定n = 3，k = 4，ans =“231”。 那里有多种解决方案。 但是它们都使用阶乘或者复杂度大于O（n），例如O（n！）。 如果你使用阶乘并在位置找到k /（n-1）!,那么当n很大（n = 100）时会出现问题。 这里n很大，（n-1）！ 溢出并变为0.结果，我得到一个零除错误…任何解决方案或算法？ 这是我的代码： public class KthPermutation { public String getPermutation(int n, int k) { // initialize all numbers ArrayList numberList = new ArrayList(); for (int i = 1; i <= n; i++) […]

需要内存有效的方法来存储大量的字符串（是：在Java中的HAT-Trie实现）

我正在处理一大组（5到2千万）字符串键（平均长度为10个字符） ，我需要将其存储在内存数据结构中，该结构在恒定时间或接近恒定时间内支持以下操作： // Returns true if the input is present in the container, false otherwise public boolean contains(String input) 就吞吐量而言，Java的Hashmapcertificate是令人满意的，但占用了大量内存。 我正在寻找一种内存效率高的解决方案，并且仍然支持良好的吞吐量（与散列相当或几乎一样好）。 我不关心插入/删除时间。 在我的应用程序中，我将仅执行插入（仅在启动时），并且随后将仅使用应用程序生命周期中的contains方法查询数据结构。 我读到HAT-Trie数据结构最接近我的需求。 我想知道是否有一个具有实现的库。 其他建议与实现的指针欢迎。 谢谢。

二进制搜索以在旋转的排序列表中查找旋转点

我有一个已旋转的排序列表，并希望在该列表上进行二进制搜索以找到最小元素。 让我们假设初始列表是{1,2,3,4,5,6,7,8}，旋转列表可以像{5,6,7,8,1,2,3,4} 在这种情况下，正常的二进制搜索不起作用。 不知道怎么做。 – 编辑 我有另一个条件。 如果列表没有排序怎么办？

如何实施基尔霍夫规则

1.用于电路表示的数据结构 用于Kirchoff规则计算目的 如何区分不同类型的电子元件 如何’识别’它们之间的电线互连 2.如何实施基尔霍夫规则 如何获得电流和电压回路 如何存储和评估基尔霍夫方程 [原始问题文本]具体来说，程序如何识别串联和并联的东西，如何区分电池，电阻器，电容器，电感器等。

Java数据结构参考

任何人都可以给我一个网站的引用，其中包含主要Java数据结构的摘要，以及它们各自的复杂性（对于某些给定的操作，如添加，查找，删除），例如Hashtable是O（1）用于查找，而LinkedList是O（n）。 像内存使用这样的一些细节也会很好。 这对于在算法的数据结构中进行思考非常有用。

哈希数组映射Trie（HAMT）

我试图了解HAMT的细节。 我已经用Java实现了一个只是为了理解。 我熟悉Tries，我认为我得到了HAMT的主要概念。 基本上， 两种类型的节点： 核心价值 Key Value Node: K key V value 指数 Index Node: int bitmap (32 bits) Node[] table (max length of 32) 为对象生成32位哈希。 一次遍历5位哈希。 (0-4, 5-9, 10-14, 15-19, 20-24, 25-29, 30-31)注意：最后一步（第7步）仅为2位。 在每个步骤中，找到位图中该5位整数的位置。 例如， integer==5 bitmap==00001 如果该位为1，则存在该部分哈希。 如果该位为0，则密钥不存在。 如果密钥存在，通过计算位图中0和位置之间的1的数量，找到它在表中的索引。 例如， integer==6 bitmap==0101010101 index==3 如果表指向键/值节点，则比较键。 如果表指向索引节点，则转到2向前移动一步。 我不太了解的部分是碰撞检测和缓解。 在链接的论文中，他暗示： 然后将现有密钥插入新的子哈希表中并添加新密钥。 每次使用5个比特的散列时，碰撞的概率减少1/32。 有时可能会消耗整个32位哈希值，并且必须计算新的哈希值才能确定两个密钥。 如果我要计算一个“新”哈希并将该对象存储在该新哈希中; 你怎么能够在结构中查找对象？ […]

最简单的扑克手评估算法

我正在考虑Java扑克牌（5张牌）评价。 现在我正在寻求简单和清晰，而不是性能和效率。 我可能会写一个“天真”的算法，但它需要很多代码。 我还看到了一些扑克评估库，它们使用散列和按位操作，但它们看起来相当复杂。 什么是扑克牌手评估的“最干净，最简单”的算法？

为什么这个奇怪的顺序发生在java的PriorityQueue中？

我阅读文档和我能找到的关于PriorityQueue的一切，但仍然不明白为什么输出是如此奇怪我的意思是我不能得到一个添加顺序的点，任何人都可以解释？ PriorityQueue pq = new PriorityQueue(); pq.offer(“2”); System.out.println(“add 2 : ” + pq); pq.offer(“4”); System.out.println(“add 4 : ” + pq); System.out.println(pq.peek() + ” “); pq.offer(“1”); System.out.println(“offer 1 : ” + pq); pq.offer(“3”); System.out.println(“add 3 : ” + pq); pq.remove(“1”); System.out.println(“remove 1 : ” + pq); 输出： add 2 : [2] add 4 : [2, 4] […]

列表或容器O（1） – 插入/删除性能，具有数组语义

我正在寻找一个提供列表语义的集合，但也允许数组语义。 说我有一个包含以下项目的列表： apple orange carrot pear 然后我的容器数组将： container[0] == apple container[1] == orangle container[2] == carrot 然后说我删除了橙色元素： container[0] == apple container[1] == carrot 我想在不必显式resize的情况下折叠数组中的间隙，即如果我删除容器[0]，则容器会崩溃，因此容器[1]现在被映射为容器[0]和容器[2]作为容器[1]等我仍然需要使用数组语义访问列表，并且不允许空值（在我的特定用例中）。 编辑： 回答一些问题 – 我知道O（1）是不可能的，但我不希望容器的数组语义接近O（log N）。 排序失败的目的，我可以迭代列表。 我最初在排序顺序上有一些措辞，我不确定我当时的想法（周五啤酒时钟最有可能）。 其中一个用例是包含图像的Qt列表 – 从列表中删除图像应该折叠列表，不必从列表中取出最后一项并将其放入其中。 在这种情况下，我确实希望保留列表语义。 我看到的主要区别是分隔列表和数组：数组 – 常量时间访问列表 – 任意插入 如果重新平衡使迭代器失效，我也不会过分担心。

何时在ArrayList或LinkedList上使用GlueList？

我遇到了一个名为GlueList的新列表实现 我想知道何时应该使用ArrayList或LinkedList。