Tag: 算法

给定一组间隔，找出包含点的间隔数: 假设您有一组N个区间（表示为左右坐标）和M个点。对于每个点，P算法应该找到P所属的区间数。这是我的算法： 1）将间隔的左右坐标分别放在“左”和“右”arrays中 2）排序“左”，同时用“右”交换条目 3）给定点P，找到最大i，使得left [i] <= P. 4）对于每个j = P，则将结果加1 5）退货结果在Java中实现： import java.util.*; class Intervals { public static int count(int[] left, int[] right, int point) { int k = find(left, point), result = 0; for (int i=0; i < k; i++) if (point <= right[i]) result++; return result; } private static int […]

计算最多N个整数的素数: 我正在尝试自己编写一个小脚本来计算所有素数到n（用户提交的参数），并希望得到一些帮助。我想使用ArrayLists来编写这个函数，并希望尽可能高效 – 对于我来说，我似乎无法掌握的另一件大事就是做所有标准和良好实践（即用大写字母等等））所以，如果你不介意，请指出这方面的任何错误，以便我可以解决它们。这是我到目前为止编写的代码，但我知道有很多方法可以优化它 – 具体来说，我有一个布尔数组存储数字是否为素数。当然有一个更好的方法来做这个，而不是循环通过数组并使一切都是素数，然后摆脱不是的数字？非常感谢你的时间！ 🙂 （tl; dr – 将脚本编写到计算机素数最多为N.我希望使用ArrayLists来执行此操作。如何使我的代码更好 – 特别是低效的布尔数组）。 import java.util.*; public class Prime { public static void main( String[] args ){ } public static void prime( int initialCapacity){ int index=0; ArrayList listOfPrimeNumbers = new ArrayList( ); boolean[] isPrimeNumber = new boolean[initialCapacity + 1]; // boolean defaults […]

在Java中实现循环调度算法: 经过数小时的脑筋训练后，我终于崩溃了，结果我不知道如何在java中实现循环法。我尝试了不同的方法，而且我得到的最接近……我用一个例子来解释.. AT =到达时间BT =突发时间（执行时间）首先，我有这一行数字(0,5;6,9;6,5;15,10) ，其中位置0-2-4元素表示到达时间，位置1-3-5元素表示突发时间。我的代码到目前为止，这个输入变成了一个类，名为Process，它带有一个构造函数： Process(String name, int AT, int BT) 。我在ArrayList分离了进程。所以现在我有一个ArrayList alst = [P0,P1,P2,P3] where P0 has AT 0 and BT 5 and so on 。我创建了一个方法，它将返回一个已经被削减了一段时间的进程列表 – 例如在(0,5;6,9;6,5;15,10)情况下，我将得到一个结果： [P0,P0,P1,P1,P1,P2,P2,P3,P3,P3,P3] 因此循环方法是一种方法，其中每个进程都获得了我选择的量子执行时间3。带有AT 0和BT 3的P0进入 – 添加到最终列表（时间过去= 3）带有AT 0和BT 2的P0进入 – 添加到最终列表（时间过去= 5） P0完了带有AT 6和BT 3的P1进入 – 添加到最终列表（时间过去= […]

在java中添加两个大数组的元素: 我必须想出一个算法，它添加了两个大数组的元素（每个数组的大小是10⁹整数，可以达到10⁹）。在java中声明两个大小为10⁹的数组时，我得到一个内存exception！问题陈述： http ： //bit.ly/1XWbUca

动态编程中的第n个Fibonacci数: 每个人都知道斐波那契系列的逻辑 Fib0 = 0 Fib1 = 1 Fibn = Fibn-1 + Fibn-2 , n > 1 我的问题是我必须计算fib(n)%(100000000+7) ，输出应该是n 比如for n=0 output 1 for n=5 output 5 for n=10 output 55 for n=100 output 24278230 我在scala使用tail recursion成功编写了它 def fi( n : Int) : Long = { def fib_tail( n: Int, a:Int, b:Int): Int = n […]

1 + 2的所有组合，加上n: 我正在尝试解决这个问题，作为编程面试的准备：青蛙只向前移动，但它可以步长1英寸或跳跃2英寸长。青蛙可以使用不同的步骤和跳跃组合覆盖相同的距离。编写一个函数，计算青蛙可以用来覆盖给定距离的不同组合的数量。例如，可以通过三种方式覆盖3英寸的距离：步进步骤，步进跳跃和跳跃步骤。我认为有一个非常简单的解决方案，但我似乎无法找到它。我想使用递归，但我看不出如何。这是我到目前为止： public class Frog { static int combinations = 0; static int step = 1; static int jump = 2; static int[] arr = {step, jump}; public static int numberOfWays(int n) { for (int i = 0; i < arr.length; i++) { int sum = 0; sum += […]

在为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 […]

如何以更有效的方式从大型集合文件中删除停用词？: 我有200,000个文件，我将为每个文件处理和提取令牌。所有文件的大小为1.5GB。当我编写用于从每个文件中提取标记的代码时，它运行良好。在所有执行时间是10分钟。在那之后，我试图删除stopwords性能严重下降。这需要25到30分钟。我正在使用网站上的停用词这里有大约571个停用词。一般过程是一次从文本文件中提取每个停用词，并与文件中的每个令牌进行比较。这是代码的存根 StringBuilder sb = new StringBuilder(); for(String s : tokens) Scanner sc=new Scanner(new File(“stopwords.txt”)); while(sc.hasNext()) { if(sc.next().equals(s)){ flag = true; break; } } if(flag) sb.append(s + “\n” ); flag = false; } String str = sb.toString() **忽略错误。上述代码的性能至少比代码低10倍。执行需要50到60分钟。 StringBuilder sb = new StringBuilder(); String s = […]

快速SVD算法: 我正在寻找一个快速库来计算Java中的SVD（奇异值分解）。我已经尝试了一些我发现的库，并且我已经做了一些基准测试（值显示了我的基准测试运行的平均时间……）它不是真正有效的基准测试，但是我测试了我需要处理的数据，对我来说够了.. Jama – 152 102ms ujmp – 156 603ms Commons Math – 183 877ms 小马 – 203 866ms jblas – 慢一点…… 我真的不希望找到比贾特更快的东西，但我可以尝试一下……你能推荐我一些其他的图书馆吗？谢谢！编辑：我找到了一个很好的页面，其中包含线性代数库的基准，所以我想结束这个问题… EJML看起来很有希望……

有效地找到随机序列的中值: 数字随机生成并传递给方法。编写程序以在生成新值时查找并维护中值。堆大小可以相等，或者下面的堆有一个额外的堆。 private Comparator maxHeapComparator, minHeapComparator; private PriorityQueue maxHeap, minHeap; public void addNewNumber(int randomNumber) { if (maxHeap.size() == minHeap.size()) { if ((minHeap.peek() != null) && randomNumber > minHeap.peek()) { maxHeap.offer(minHeap.poll()); minHeap.offer(randomNumber); } else { maxHeap.offer(randomNumber); } } else { // why the following block is correct? // I think it may create unbalanced heap […]