Tag: algorithm

为什么quicksort比mergesort更好？: 面试中我被问到了这个问题。他们都是O（nlogn），但是大多数人使用Quicksort而不是Mergesort。这是为什么？

algorithm随机生成一个美观的调色板: 我正在寻找一个简单的algorithm来生成大量的随机，美观的颜色。所以没有疯狂的霓虹灯颜色，让人想起粪便的颜色等我已经find了这个问题的解决scheme，但他们依赖于替代调色板比RGB。我宁愿只使用直线RGB而不是来回映射。这些其他解决scheme最多也只能生成32个左右随意的颜色。任何想法都会很棒。

从一串数字中存储最大的5000个号码: 鉴于以下问题： “从一串数字中存储最大的5000个号码” 想到的解决scheme是一个二叉search树，一旦计数达到5000，就保持树中节点数量的计数和最小节点的引用。当计数达到5000时，每个要添加的新数字可以与树中最小的项目。如果更大，可以添加新的数字，然后删除最小的和新的最小的计算（这应该是非常简单的，已经有以前最小）。我对这个解决scheme的担心是二叉树自然会偏斜（因为我只是在一边删除）。有没有办法解决这个问题，不会造成一个可怕的歪斜的树？如果有人愿意，我已经在下面列出了我的解决scheme的伪代码： process(number) { if (count == 5000 && number > smallest.Value) { addNode( root, number) smallest = deleteNodeAndGetNewSmallest ( root, smallest) } } deleteNodeAndGetNewSmallest( lastSmallest) { if ( lastSmallest has parent) { if ( lastSmallest has right child) { smallest = getMin(lastSmallest.right) lastSmallest.parent.right = lastSmallest.right } else { smallest […]

子集合algorithm: 我正在处理这个问题：子集和问题以input为n整数的集合X = {x1, x2 ,…, xn}和另一个整数K 问题是检查是否存在X'的子集X' ，其元素总和为K ，如果有的话find子集。例如，如果X = {5, 3, 11, 8, 2}且K = 16那么答案是YES因为子集X' = {5, 11}具有16的和。实现运行时间至less为O(nK)的algorithm。注意复杂度O(nK) 。我认为dynamic编程可能会有帮助。我发现了一个指数时间algorithm，但它没有帮助。有人可以帮我解决这个问题吗？

PHPalgorithm从一个集合中生成一个特定大小的所有组合: 我试图推导出一种algorithm，它可以生成特定大小的所有可能的组合，就像接受一个字符和大小数组作为参数的函数，并返回一个组合数组。例子：假设我们有一组字符：Set A = {A，B，C} a）大小2的所有可能的组合：（3 ^ 2 = 9） AA, AB, AC BA, BB, BC CA, CB, CC b）尺寸3的所有可能的组合：（3 ^ 3 = 27） AAA, AAB, AAC, ABA, ABB, ACC, CAA, BAA, BAC, …. ad so on total combinations = 27 请注意，这一对尺寸可能会大于整体的尺寸。防爆。如果设置包含3个字符，那么我们也可以创build尺寸4的组合。编辑：另请注意，这是从排列不同。在置换中，我们不能有重复的字符，例如，如果我们使用置换algorithm，AA不能来。在统计中，它被称为抽样。

什么是在一个位置或更低位置计数设置位的有效方法？: 给定std::bitset<64> bits ，设置任意数量的位并将位位置X （0-63）在X位或更低位计数位的最有效方法是什么，如果X位没有设置则返回0 注意：如果该位被设置，返回将总是至less为1 蛮力的方式很慢： int countupto(std::bitset<64> bits, int X) { if (!bits[X]) return 0; int total=1; for (int i=0; i < X; ++i) { total+=bits[i]; } return total; } bitset的count()方法会给你所有位的popcount ，但是bitset不支持范围注意：这不是一个重复的如何计算一个32位整数的设置位数？因为这要求所有的位不是从0到X的范围

将arrays1更改为arrays2所需的最小交换次数？: 例如，input是 Array 1 = [2, 3, 4, 5] Array 2 = [3, 2, 5, 4] 所需的最小交换次数是2 。交换不需要与相邻的单元格交换，任何两个元素都可以交换。

圆圈碰撞: 我要开发一个两个球（圆圈）相撞的二维球类游戏。现在我有确定碰撞点的问题（实际上，确定它们是否在X轴/ Y轴上碰撞）。我有一个想法，当两个球的y坐标之间的差异大于x坐标差时，他们碰撞他们的y轴，否则，他们碰撞在他们的x轴。我的想法是否正确？我在游戏中实现了这个东西。通常它运作良好，但有时它失败。谁能告诉我，我的想法是对的？如果没有，那么为什么，还有更好的办法？通过x轴的碰撞，我的意思是圆的第1，第4，第5或第8个八分圆，y轴表示圆的第2,3,6或7个八分圆。提前致谢！