Tag: 数据结构

树的递归和非反复遍历

通过在二叉搜索树上执行递归和非递归前序遍历，我得不到相同的结果 递归方法 public static void preorder(TreeNode root) { if (root == null) return; else { System.out.print(root); inorder(root.getLeftPtr()); inorder(root.getRightPtr()); } } 非递归方法 public static void preorder2(TreeNode root){ if(root==null)return; Stack stack=new Stack(); while(true){ while(root!=null){ //process current Node System.out.print(root); stack.push(root); root=root.getLeftPtr(); } if(stack.isEmpty())break; root=stack.pop(); root=root.getRightPtr(); } } 结果 recursive method-> 10-> 5-> 6-> 8-> 12-> 15-> 20 non […]

Hackerrank：Sherlock和Anagrams（在Strings部分中等）

问题描述： https ： //www.hackerrank.com/challenges/sherlock-and-anagrams 有人可以告诉我，我做错了什么？ 我的算法是： 输入字符串; 海峡 生成从长度i = 1到str.length-2的模式字符串 检查str.substring（i + 1）中是否存在模式字符串的字谜 以下是未通过的测试用例： input-string My OP Expected OP ifailuhkqq 2 3 我的代码： public class SherlockandAnagrams { static int count = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); generatePairs(sc.next()); int len = 1; } public static void generatePairs(String str) […]

如何在Java中将节点插入完整的二叉树？

众所周知，当插入完整的二叉树时，我们必须从左到右填充所有叶子的所有叶子。 我有以下方法将节点插入完整的二叉树。 //fields private T item; private int size; private CBTree left, right; //add method public void add(T item) { if(left == null) { left = new CBTree(item); size += left.size; } else if(right == null) { right = new CBTree(item); size += right.size; } else if(!((left.left != null) && (left.right != null)) && ((right.left […]

线程安全LinkedHashMap没有Collections.synchronized

我正在使用LinkedHashMap，并且环境是multithreading的，因此这个结构需要是线程安全的。 在特定事件期间，我需要读取整个地图推送到数据库并清除所有。 大多数时候只有写入发生在这张地图上。 此地图限制了50个条目。 我使用的是Oracle MAF，它没有Collections.syncronizedMap。 那么，我需要在synchronized块中放置什么东西以确保写入和读取不会遇到concurrentModificationException等 几个要求： 我需要像循环队列一样表现它，以便重写LinkedHashMap的removeEldestEntry方法。 我需要保留订单

是否存在像“Set”这样的对象，它只能包含唯一的字符串值，还包含字符串值出现次数的计数？

在Java中是否存在像“Set”这样的对象，它只能包含唯一的字符串值，还包含字符串值出现次数的计数？ 这个想法很简单 有了数据集ala … A B B C C C. 我想将每行文本添加到类似Set的对象中。 每次将非唯一文本添加到集合中时，我还希望具有与集合关联的数值，以显示添加的次数。 因此，如果我在上面的数据集上运行它，输出将是这样的： 答：1 B：2 C：3 有任何想法吗？

在修改它的副本时保持原始Vector完好无损

我想复制一个包含以下结构的Vector ，对我来说重要的是在修改复制的一个时保持原始Vector完好无损： public class objet_poid_n { public int Num; public double Poid; } 假设我们有： Vector original = new Vector(); original = filled((Vector) original); // function fills original with many objet_poid_n elements Vector destination = new Vector(); 我试过了 ： destination = original ; 和 destination = original.clone(); 和 destination.setSize(original.size()); Collections.copy(destination,original); 和 destination.addAll((Vector) original); 和 destination.copyInto((Vector) original); […]

在为TreeSet实现自定义比较器时遇到问题（Dijkstra’s）

我目前正在尝试使用Adjacency Lists实现我自己的Dijkstra定制O（N.lgN）解决方案。 现在，如果您熟悉此算法（很可能是您），我就无法存储每个Vertex的元组。 如果你不知道我在说什么，请联系： http ：//qr.ae/LoESY 元组可以很容易地用C ++存储 pair . 无论如何，我找到了解决方案，并且不顾一切地知道类似的类存在它被称为’AbstractMap.SimpleEntry’类。 详情如下： https://stackoverflow.com/a/11253710/4258892 现在您已经阅读了它，它的工作方式几乎与pair 相同，并且足以将Adjacent Edge作为键存储，而Weight则作为元组中的Value存储。 声明：Map.Entry pair = new AbstractMap.SimpleEntry（1,2）; 现在，我将所有输入以元组的forms存储在每个向量的ArrayList中。 我计划将输入的源的元组添加到TreeSet中，并按权重的升序排序（对吗？）。 但是，如果我只是将这些元组添加到TreeSet中，我会抛出一个错误： Exception in thread “main” java.lang.ClassCastException:java.util.AbstractMap$SimpleEntry cannot be cast to java.lang.Comparable 现在我不知道如何为TreeSet实现一个自定义比较器，它会逐步对我的值进行排序（在Dijkstra中，权重最小的边缘会先出现吗？）。 此外，如果TreeSet不可能，你能为我提供一个优先级队列，并实现比较器吗？ 即使你没有关注，这是我的代码。 希望你能理解： 编辑代码根据以下答案的建议编辑 package GRAPH; import java.io.*; import java.util.*; /** * Created by Shreyans on 3/25/2015 at 7:26 PM […]

显示Splay树的方法

我已经构建了一个展开树，我正在尝试按顺序将其打印出来，以便当您将头转向左侧时，您可以正常方式看到树。 我编写了以下代码，它输出树有点正确，但它在最右边的节点上添加了额外的空格，并没有为应该放在根节点下面的所有子节点添加空格： public void printReverseInOrder() { if (root != null) { reverseInOrder(root, 0); } else { System.out.println(); } } public void reverseInOrder(BSTnode h, int indent) { if (h != null) { for (int i = 0; i < indent; i++) { System.out.print(" "); } indent++; reverseInOrder(h.right, indent); reverseInOrder(h.left, indent); System.out.println(h.data); indent–; } } 我觉得这可能是我的递归或我的缩进添加和减少的位置的错误。

马尔可夫链：SQL数据库和Java表示

现在这个问题有点模糊。 我有一个基于文本的马尔可夫链，我通过解析用户输入的文本生成。 它用于生成几乎连贯的乱码串，并根据序列中的当前单词存储给定单词作为文本序列中下一个单词的概率。 在javascript中，此对象看起来如下所示： var text_markov_chain = { “apple” : { “cake” : 0.2, “sauce” : 0.8 }, “transformer” : { “movie” : 0.95, “cat” : 0.025, “dog” : 0.025 } “cat” : { “dog : 0.5, “nap” : 0.5 } // … } 因此，例如，如果当前单词是变换器，那么我们生成的下一个单词将有95％的机会成为电影，并且分别有2.5％的机会成为猫或狗。 我的问题有两个： 在Java中表示此对象的最佳方法是什么？ 我最关心的是50％的快速访问和50％的内存使用率 如何将此对象存储在单个数据库表（例如MySQL）中？ 更新：为了回应@ biziclop的回答，以及@ SanjayTSharma的评论，在我的课程下面我最终写了（这是一项正在进行的工作，麻省理工学院的许可证。它目前只生成一阶Markov链。 import java.io.IOException; import […]

如何确定数据结构的实际内存使用情况

在数据结构中，我知道结构的大小取决于从一个部分到另一个部分的内部链接。 除了JProfiler之外，有没有办法确切地告诉特定结构中有多少内存？ 例如，本学期的课程项目与将各种结构应用于歌曲数据库有关。 这些项目涵盖了数组，列表，展开列表和树。 我想做的是看看使用了多少内存。 例如，链表的内存要求为3N，但我想看看节点在我的项目中占用了多少空间。 JProfiler看起来会起作用，但500美元超出了我的价格范围，我想将它用于本学期涵盖的所有结构，而不是目前为止应用的三种结构。