Tag: 算法

计算O（（n + s）log n）中的圆交点

我试图弄清楚如何设计一个能够用O（（n + s）log n）复杂度完成这项任务的算法。 是交叉点的数量。 我试过在网上搜索，却找不到东西。 无论如何，我意识到拥有一个好的数据结构是关键。 我在java：TreeMap中使用Red Black Tree实现。 我还使用着名的（？）扫描线算法来帮助我处理我的问题。 让我先解释一下我的设置。 我有一个调度程序。 这是一个PriorityQueue，我的圈子根据最左边的坐标排序（升序）。 scheduler.next()基本上轮询PriorityQueue，返回下一个最左边的圆圈。 public Circle next() { return this.pq.poll(); } 我这里也有一个包含4n个事件点的数组。 授予每个圆圈有2个事件点：大多数左x和最右x。 调度程序有一个方法sweepline（）来获取下一个事件点。 public Double sweepline() { return this.schedule[pointer++]; } 我也有状态。 扫描线状态更加精确。 根据该理论，状态包含有资格相互比较的圆圈。 在整个故事中拥有扫描线的关键在于你能够排除很多候选人，因为他们根本不在当前圈子的半径范围内。 我使用TreeMap实现了Status。 Double是circle.getMostLeftCoord(). 此TreeMap保证O（log n）用于插入/删除/查找。 算法本身的实现方式如下： Double sweepLine = scheduler.sweepline(); Circle c = null; while (notDone){ while((!scheduler.isEmpty()) && (c = […]

如何找到比给定数量少2的最大功率

我需要找到比给定数字少2的最大功率。 我卡住了，找不到任何解决方案。 码： public class MathPow { public int largestPowerOf2 (int n) { int res = 2; while (res < n) { res =(int)Math.pow(res, 2); } return res; } } 这不能正常工作。 测试输出： Arguments Actual Expected ————————- 9 16 8 100 256 64 1000 65536 512 64 256 32 如何解决这个问题？

在Java中实现置换算法的技巧

作为学校项目的一部分，我需要编写一个函数，该函数将采用整数N并返回数组{0,1，…，N-1}的每个排列的二维数组。 声明看起来像public static int [] [] permutations（int N）。 http://www.usna.edu/Users/math/wdj/book/node156.html中描述的算法是我决定实现它的方法。 我使用ArrayLists的数组和数组以及ArrayLists的ArrayLists进行了一段时间的摔跤，但到目前为止，我一直很沮丧，特别是试图将2d ArrayList转换为2d数组。 所以我用javascript编写了它。 这有效： function allPermutations(N) { // base case if (N == 2) return [[0,1], [1,0]]; else { // start with all permutations of previous degree var permutations = allPermutations(N-1); // copy each permutation N times for (var i = permutations.length*N-1; i >= 0; i–) […]

从二叉搜索树中递归删除

这是作业; 请不要只给我代码 我有两种方法： remove(T data)和removeRec(Node node, T data) 。 在当前状态下，似乎我的代码只删除了BST的root 。 @Override public T remove(T data) { if (data == null) { throw new IllegalArgumentException(“Data is null”); } if (root == null) { throw new java.util.NoSuchElementException(“BST is empty”); } else { size–; BSTNode dummy = new BSTNode(null); return removeRec(root, data, dummy).getData(); //This is probably wrong […]

二元快速排序

我想从[Robert Sedgewick的书] [1]中实现Binary Quicksort算法。 它看起来像这样： public class quickb{ public static final int bitsword=32; public static void quicksortB(int a[],int l,int r,int d){ int i=l; int j=r; if (rbitsword) return ; while (j!=i) { while (digit(a[i],d)==0 && (ii)) j–; int t=a[i]; a[i]=a[j]; a[j]=t; } if (digit(a[r],d)== 0) j–; quicksortB(a,l,j-1,d+1); quicksortB(a,j,r,d+1); } public static void main(String[]args){ int a[]=new […]

使用哈希表和/或尝试的Anagram算法

我一直在互联网上搜索一段时间，找到一个字符串（单词）的所有字符串（即团队产生单词tame），使用哈希表和trie。 我在SO上找到的所有内容都是validation2个单词是字谜。 我想更进一步，找到一个英文算法，以便我可以用Java编程。 例如， 循环遍历所有角色。 对于每个唯一字符插入哈希表。 等等。 我不想要一个完整的程序。 是的，我正在练习面试。 如果出现这个问题，那么我就会知道它并且知道如何解释它而不仅仅是记住它。

这个算法是否可以找到一系列可接受的无穷大的总和？

可以找到以下系列的无穷大之和： 1 1/2 1/3 1/4 1/5 … 根据某位科学家的解释， 无穷大是指任何点都不存在的点，即inf + x = inf或inf~（inf + x）= 0 。 因此，基于该理论，使用以下算法： float sum=0.0; for(int i=0;;i++){ if((sum+(1.0/i))==sum) break; sum+=(1.0/i); } /* print the value of sum */ 算法在C和JAVA中运行，两者都输出为inf 。 分别用C和Java编写的print语句是 printf(“%6f”,sum); System.out.println(sum); 编辑：之前写的代码（在问题中）有一个错误，因为我键入它，没有复制粘贴。 对不起。 这解决了，这是我的问题所在的代码： float sum=0.0; for(int i=1;;i++){ if((sum+ (1.0/i))==sum) break; sum+=(1.0/i); } /*print the value of sum*/ […]

使用md5扫描重复文档

由于某些原因，我不能使用MessageDigest.getInstance(“MD5”) ，所以我必须手动编写算法代码，我的项目是在Android设备上扫描重复文档（* .doc，* .txt，* .pdf） 。 我的问题是，在输入算法之前我必须写什么，扫描Android设备上MY ROOT目录上的重复文档？ 如果没有选择目录，当我按下按钮扫描时，进程开始， listview显示。 有人可以帮帮我吗？ 我的项目截止日期即将到来。 非常感谢。 public class MD5 { //What must I write here, so I allow to scan for duplicate document on Android root with MD5 Hash //MD5 MANUAL ALGORITHM CODE }

使用具有负边缘权重的Bellman-Ford追踪最长路径

我目前通过否定所有边权和运行Bellman-Ford算法找到有向无环正加权图中最长的路径。 这很有效。 但是，我想打印使用哪些节点/边的轨迹。 我怎样才能做到这一点？ 该程序将节点数，源，目标和边权重视为输入。 输入在-1 -1 -1停止。 我的代码如下： import java.util.Arrays; import java.util.Vector; import java.util.Scanner; public class BellmanFord { public static int INF = Integer.MAX_VALUE; // this class represents an edge between two nodes static class Edge { int source; // source node int destination; // destination node int weight; // weight of the edge […]

我有24个项目需要分成6组4.我可以使用什么算法来查找所有可能的组合？

我有24个独特的项目。 我需要将它们分成6组，每组由4个项目组成。 我可以使用什么算法来迭代考虑订单的这24个项目的所有可能组合/分离是不相关的 例如，一个这样的组合将是： ABCD-EFGH-IJKL-MNOP-QRST-UVWX ^因为顺序不重要，所以这将是： DCBA-HGFE-LKJI-POMN-TSRQ-XWVU ^但他们会有不同于： 渔护署-EBGH-IJKL-MNOP-QRST-UVWX ……这是一个独特的组合。 所以只是重申：我正在试图弄清楚如何从24个项目中获得所有可能的组合，考虑到我需要将它们分成6组，每组4个。 此外，6组的排序也不重要。 含义：“ABCD-EFGH-IJKL-MNOP-QRST-UVWX”与“EFGH-IJKL-MNOP-QRST-UVWX-ABCD”相同 注意：在Java中实现这一点的帮助会很棒。 谢谢！ 编辑： 解决方案如何： （1）我首先尝试找到所有可能的四个组，给出24个项目。 （2）然后我找到所有可能的六个组，给出由＃1产生的组 思考？