Tag: 算法

面试问题：递归生成素数的最快方法是什么？: 质数的生成很简单但是找到它并以递归方式生成（素数）的最快方法是什么？这是我的解决方案。但是，这不是最好的方法。我认为它是O（N * sqrt（N））。如果我错了，请纠正我。 public static boolean isPrime(int n) { if (n < 2) { return false; } else if (n % 2 == 0 & n != 2) { return false; } else { return isPrime(n, (int) Math.sqrt(n)); } } private static boolean isPrime(int n, int i) { if (i < […]

Java编程：楼梯动态编程示例: 一个人正在爬楼梯，有n个台阶，可以一次走1步，2步或3步。现在编写一个程序来计算孩子跑楼梯的可能方式。给出的代码如下 public static int countDP(int n, int[] map) { if (n-1) return map[n]; else { map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map); return map[n]; } } 我知道C和C ++，而不是JAVA。这是来自Cracking the Coding的采访书。任何人都可以解释一下为什么以及如何在这里使用function图？这里的地图是arrays吗？我没有看到任何行保存输入到地图数组，但它会如何返回一些东西？有人知道这段代码的C ++或C版本吗？很难理解这段代码。也许不是因为JAVA语法，而是动态编程的隐式结构。这个算法的时间复杂度是多少？它应该小于O（3 ^ n）？我将不胜感激。多谢你们

在两个数组中搜索匹配项，没有额外的内存: 前几天我和亚马逊进行了一次采访，他们问我的一个问题是关于以下问题。给定2个整数数组，包含任意数量的正数和负数元素，找到两个数组中出现的数字。我能够使用HashMaps很容易地解决这个问题，因此它会有O(n)计算复杂度，但不幸的是，这也会产生O(n)空间复杂度。这可以通过遍历每个数组中的所有元素而没有额外的内存来完成，但这将是O(n^2) 。在我完成HashMap方法的解释之后，面试官问我是否可以想到一个O（n）计算方法，但不会使用任何额外的内存。我无法想到任何动态，并且无法为此找到解决方案。在线性时间内，有没有办法在不使用额外内存的情况下找到这些值？注意：我在CareerCup上发布了这个问题，但是那里的每个人似乎都没有得到我不需要使用额外空间的概念，并且它必须是O(n)计算。这是我在采访中使用的代码。它有效，但空间不是O（1）。 import java.util.*; public class ArrayFun { public static void main(String[] args) { int[] a = {1,2,3,4}; int[] b = {2,5,6,7,3,2,2,2,2,1,2,2,2,2}; ArrayList matches = ArrayFun.findMatches(a,b); for (int i = 0;i<matches.size();++i) { System.out.println(matches.get(i)); } } public static ArrayList findMatches(int[] a, int[] b) { HashMap map = […]

使用Java和PHP进行AES加密: 我最近在Java中使用AES算法来加密文本。现在我需要在PHP中重建该算法，但我不知道如何，因为互联网上的PHP算法会返回不同的结果。也许你可以帮助我。这是要加密的Java代码： private static final String KEY = “57238004e784498bbc2f8bf984565090”; public static String encrypt(final String plaintext) throws GeneralSecurityException { SecretKeySpec sks = new SecretKeySpec(hexStringToByteArray(KEY), “AES”); Cipher cipher = Cipher.getInstance(“AES”); cipher.init(Cipher.ENCRYPT_MODE, sks, cipher.getParameters()); byte[] encrypted = cipher.doFinal(plaintext.getBytes()); return byteArrayToHexString(encrypted); } public static byte[] hexStringToByteArray(String s) { byte[] b = new byte[s.length() / 2]; for (int […]

两个球员网格遍历游戏: 给定一个M * N网格和两个玩家p1和p2在网格上的位置。有n个球放在网格上的不同位置。设这些球的位置为B(1), B(2), B(3) …, B(n) 。我们需要计算选择所有球所需的最小曼哈顿距离。如果i < j则应按升序选择球，即如果在B(j)之前选择B(j) 。请考虑以下示例案例： p1 = (1, 1) p2 = (3, 4)让我们考虑球的位置为B(1) = (1, 1), B(2) = (2, 1), B(3) = (3, 1), B(4) = (5, 5) 输出将为5因为p1将首先选择B(1), B(2), B(3)并且p1将选择B(4) 我的方法我做了一个贪婪的方法并计算了给定球B(i)的p1和p2距离（从i = 1 to n ）并且将最小值加到输出并相应地更新了玩家的位置。但是这种方法在许多测试用例中都失败了。 PS：在我过去的一次采访中提出了这个问题， O(n)解决了这个问题的预期。编辑：更多的测试用例可以是 […]

用Java创建迷宫求解算法: 我被赋予了在Java中创建迷宫求解器的任务。这是作业： Write an application that finds a path through a maze. The maze should be read from a file. A sample maze is shown below. OOOOOXO XXOXOOX OXOOXXX XXXOOXO XXXXOOX OOOOOOO XXOXXXO 字符“X”表示墙壁或阻挡位置，字符“O”表示打开位置。你可以假设迷宫的入口总是在右下角，出口总是在左上角。您的程序应将其输出发送到文件。如果找到路径，则输出文件应包含路径。如果未找到路径，则应将消息发送到该文件。请注意，迷宫可能有多个解决方案路径，但在本练习中，您只需要找到一个解决方案，而不是所有解决方案。您的程序应该使用堆栈来记录它正在探索的路径，并在它到达阻塞位置时回溯。在编写代码之前，请务必编写完整的算法。您可以随意创建任何可帮助您完成作业的其他课程。 Here’s my Algorithm: 1)Initialize array list to hold maze 2)Read text file holding […]

确定可能的项目组的算法: 我正试图这样做，它正在吃我。我知道这不复杂。我有很多项目，这个数字可以等于或大于3。然后我需要确定将完成总计的项目组的可能组合。唯一的限制是团体应该有三件或更多件，不超过（但包括）七件。例如：如果我有7个项目，那么我可以拥有这些可能的组： 1组7项。 1组4项和1组3项。如果我有12个项目，我可以拥有这些可能的组： 4组3项。 3组4项。 2组6项。 1组7项+ 1组5项。 2组3组和1组6项。 1组3组，1组4组和1组五项。 … 我考虑了递归并开始实现算法。它显然不起作用。我吮吸递归。很多。 //Instance Fields public List<ArrayList> options; //Method that will generate the options. The different options are //stored in a list of “option”. An individual option will store a list of //strings with the individual […]

我在网上找到一个有趣的谷歌访谈算法需要线性时间: 所以我在网上发现了这个Google采访算法问题。这真的很有趣，我还没有找到一个好的解决方案。请看一下，并给我一个提示/解决方案，如果你能用Java编写代码那将是很好的。 “设计一个算法，给定一个数组中n个元素的列表，找到列表中出现超过n / 3次的所有元素。算法应该以线性时间运行。（n> = 0）你应该使用比较并实现线性时间。没有散列/过多空间/并且不使用标准线性时间确定性选择算法“

如何实现最低频繁使用（LFU）缓存？: 最不常用（LFU）是一种用于管理计算机内存的缓存算法。该方法的标准特征涉及系统跟踪块在存储器中被引用的次数。当缓存已满并需要更多空间时，系统将清除具有最低参考频率的项目。实现最近使用的对象缓存的最佳方法是什么，比如Java？我已经使用LinkedHashMap实现了一个（通过维护对象被访问的次数）但我很好奇是否有任何新的并发集合是更好的候选者。考虑这种情况：假设缓存已满，我们需要为另一个缓存腾出空间。假设在缓存中记录了两个对象，这些对象仅被访问一次。如果我们知道其他（不在缓存中）对象被多次访问，那么要删除哪一个？谢谢！

Java中的Spaced重复算法的开源实现: 我在一个Spaced Repetition必不可少的项目上工作，但是我不是这个主题的专家，我害怕重新发明方形轮。我的研究指出了两个不同的系统，即Leitner系统和SM系列算法。我还没有确定哪个系统最适合我的项目。如果我要采用SM方向，我想我会尝试实现类似于Anki使用的东西。我最好的选择是使用现有的Java库。它可能非常简单，我只需要计算下一次重复的时间。有没有人听说过这样的倡议？