Tag: algorithm

理解递归中的堆栈展开（树遍历）

我正在编写一个遍历二叉搜索树的程序。这是我的代码： Main.java public class Main { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); binaryTree.add(50); binaryTree.add(40); binaryTree.add(39); binaryTree.add(42); binaryTree.add(41); binaryTree.add(43); binaryTree.add(55); binaryTree.add(65); binaryTree.add(60); binaryTree.inOrderTraversal(binaryTree.root); } } Node.java public class Node { int data; Node left; Node right; Node parent; public Node(int d) { data = d; left = null; right = null; […]

无法在Java中向二进制搜索树添加1,000,000个元素

我正在将二进制搜索树作为一项任务。 当我尝试添加1,000,000个元素时，我遇到了问题。 插入15,000个元素后，我收到错误： 线程“main”java.lang.StackOverflowError中的exception 我的代码有问题我无法找到我做错的地方。 public class BinarytreeInsert { public static void main(String[] args) { new BinarytreeInsert().run(); } static class Node { Node left; Node right; int value; public Node(int value) { this.value = value; } } public void run() { Node rootnode = new Node(25); System.out.println(“Building tree with root value ” + rootnode.value); System.out.println(“=================================”); […]

从csv生成树结构

我已经暂时解决了这个问题一段时间了。 我基本上试图从一组CSV数据生成树层次结构。 CSV数据不一定是有序的。 这类似于以下内容： Header: Record1,Record2,Value1,Value2 Row: A,XX,22,33 Row: A,XX,777,888 Row: A,YY,33,11 Row: B,XX,12,0 Row: A,YY,13,23 Row: B,YY,44,98 我试图尽可能灵活地进行分组。 最简单的分组是为Record1和Record2做的，Value1和Value2存储在Record2下，这样我们得到以下输出： Record1 Record2 Value1 Value2 这将是： A XX 22,33 777,888 YY 33,11 13,23 B XX 12,0 YY 44,98 我目前正将我的群组设置存储在列表中 – 我不知道这是否会妨碍我的想法。 此列表包含组的层次结构，例如： Record1 (SchemaGroup) .column = Record1 .columns = null .childGroups = Record2 (SchemaGroup) .column = […]

树中下降路径的最大长度始终向左

我正在准备技术面试，所以基本上从一开始就学习算法:)我们给了一个BST。 我需要在其中找到desc路径的最大长度，它始终向左或向右。换句话说，示例树的下行路径为2，即15-10-6 5 / \ 2 15 / 10 / \ 6 14 我对算法问题很新。我解决这个问题的步骤是什么？ 我的想法是使用DFS和计数器来存储最长的路径。 但我无法弄清楚如何使用递归来完成这项工作，而递归对于这种数据结构来说似乎更自然。 有什么建议/指示吗？

在2Darrays中找到峰值的算法

假设我在java int[][] array有一个2D累加器int[][] array 。 该数组可能如下所示： （x和z轴表示数组中的索引，y轴表示值 – 这些是int[56][56] ，值为0~4500） 要么 我需要做的是在arrays中找到峰值 – 第一个峰值有2个峰值，第二个arrays有8个峰值。 这些峰值总是“明显的”（峰值之间始终存在间隙），但它们不必像这些图像那样相似，它们可能或多或少是随机的 – 这些图像不是基于真实数据，只是样本。 真正的arrays可以有5000×5000的大小，峰值从几千到几十……算法必须是通用的，我不知道arrays或峰值有多大，我也不知道那里有多少个峰值是。 但我确实知道某种阈值 – 峰值不能小于给定值。 问题是，一个峰可以由附近的几个较小的峰组成（第一个图像），高度可以是非常随机的，并且在一个arrays中大小可以显着不同（大小 – 我的意思是它在arrays中占用的单位数 – 一个峰值可以包含6个单位，其他峰值可以包含90个单位。 它也必须快速（全部在1次迭代中完成），arrays可能非常大。 任何帮助表示赞赏 – 我不希望你的代码，只是正确的想法:)谢谢！ 编辑：你询问了域名 – 但它很复杂，而且它无法解决问题。 它实际上是一个带有3D点的ArrayLists数组，如ArrayList [] []，并且有问题的值是ArrayList的大小。 每个峰包含属于一个簇的点（在这种情况下为平面） – 该数组是算法的结果，它对点云进行分段。 我需要在峰值中找到最高值，这样我就可以将“最大”的arraylist中的点拟合到一个平面，从中计算一些参数，然后正确地聚集来自峰值的大部分点。

反转线性链表

线性链表是一组节点。 这是节点的定义方式（为了方便起见，我们不区分节点和列表）： class Node{ Object data; Node link; public Node(Object pData, Node pLink){ this.data = pData; this.link = pLink; } public String toString(){ if(this.link != null){ return this.data.toString() + this.link.toString(); }else{ return this.data.toString() ; } } public void inc(){ this.data = new Integer((Integer)this.data + 1); } public void lappend(Node list){ Node child = this.link; while(child […]

找到所有“字符相等”字符串的高效算法？

我们如何编写一个输出输入字符串“ homoglyph equivalent ”的高效函数？ 例1 （伪代码）： homoglyphs_list = [ [“o”, “0”], // “o” and “0” are homoglyphs [“i”, “l”, “1”] // “i” and “l” and “1” are homoglyphs ] input_string = “someinput” output = [ “someinput”, “s0meinput”, “somelnput”, “s0melnput”, “some1nput”, “s0me1nput” ] 例2 ： homoglyphs_list = [ [“rn”, “m”, “nn”], ] input_string = “rnn” output […]

算法 – O（n）中二进制搜索树的每两个节点之间的距离之和？

问题是找出BinarySearchTree的每两个节点之间的距离总和，假设每个父子对由单位距离分开。 每次插入后都要计算。 例如： ->first node is inserted.. (root) total sum=0; ->left and right node are inserted (root) / \ (left) (right) total sum = distance(root,left)+distance(root,right)+distance(left,right); = 1 + 1 + 2 = 4 and so on….. 我提出的解决方案： 蛮力。 脚步： 执行DFS并跟踪所有节点： O(n) 。 选择每两个节点并使用最低公共祖先方法计算： O(nC2)_times_O(log(n))=O(n2log(n))之间的距离并将它们相加。 总体复杂性： -O(n2log(n)) 。 O(nlog(n)) 。 脚步：- 在插入之前执行DFS并跟踪所有节点： O(n) 。 计算插入节点与之间的距离： O(nlog(n)) […]

在文本正文中找到一个ASCII艺术图像，并具有一定的容错性

是否有任何算法可以找到以下ASCII艺术图像？ + + +++ +++++++ ++ ++ ++ + ++ ++ +++ ++ ++ + ++ ++ ++ +++++++ +++ 在下面的文本体内？ complete_file_here + + + ++ + +++ + + + ++ + + ++++ + + + + + + +++ +++ + + + + ++ ++ ++ + ++ + + + […]

Quicksort比Mergesort慢？

我昨天正在努力实现一个快速排序，然后我运行它，期望比Mergesort更快的运行时间（我也已实现）。 我运行了两个，虽然快速排序对于较小的数据集<100个元素更快（并且我确实validation了它的工作原理），但mergesort很快就成为了更快的算法。 有人告诉我，快速排序几乎总是比mergesort“更快”，我知道在这个主题上有一些争论，但我至少预计它会比这更接近。 对于数据集> 10000个元素，mergesort的速度提高了4倍多。 这是预期的，还是我的快速排序代码中有错误？ 归并排序： public static void mergeSort(int[ ] e) { if (e.length <= 1) return; int[] first = new int[e.length/2]; int[] second = new int[e.length – first.length]; System.arraycopy(e, 0, first, 0, first.length); System.arraycopy(e, first.length, second, 0, second.length); mergeSort(first); mergeSort(second); System.arraycopy(merge(first, second), 0, e, 0, e.length); } private static int[] merge(int[] first, […]