Tag: 算法

使用xor解释在数组中找到两个非重复的整数: 给定[1,1,4,5,5,6]我们可以发现4和6是非重复整数。有一个使用XOR的解决方案。这是作者提出的算法： #include #include /* This finction sets the values of *x and *y to nonr-epeating elements in an array arr[] of size n*/ void get2NonRepeatingNos(int arr[], int n, int *x, int *y) { int xor = arr[0]; /* Will hold xor of all elements */ int set_bit_no; /* Will have only single […]

查找给定集合的所有子集的总和: 建议一种算法，用于查找集合中所有子集的总和。例如，如果k=3且子集为{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}则求和子集是{1}+{2}+{3}+{1+2}+{1+3}+{2+3}+{1+2+3}=24

如何生成最大不平衡的AVL树: 我编写了一个AVL树的C语言库作为通用分类容器。出于测试目的，我希望有一种方法来填充树，使其最大程度地不平衡，即，使其具有包含的节点数的最大高度。 AVL树具有很好的属性，如果从空树开始，按升序（或降序）顺序插入节点，则树始终是完全平衡的（即，对于给定数量的节点，它具有其最小高度）。从空树T 0开始，为每个节点数n生成精确平衡的AVL树T n的一个整数键序列就是简单的 k 1 = 0 k n + 1 = k n +1，即k n = n-1 我正在寻找一个（希望很简单的）整数键序列，当插入最初空的树T 0时，生成最大不平衡的AVL树T 0 ，…，T n 。我也感兴趣的是一种解决方案，其中只有最后一棵树T n最大程度地不平衡（节点数n将是算法的参数）。满足约束的解决方案 max（k 1 ，…，k n ） – min（k 1 ，…，k n ）+1≤2n 是可取的，但不是严格要求的。 4 n而不是2 n的关键范围可能是合理的目标。我无法在互联网上找到关于通过插入生成最大高度的AVL树的任何内容。当然，我正在寻找的生成树的序列将包括所有所谓的Fibonacci树，它们是具有最小节点数的给定深度的AVL树。有趣的是，英语维基百科甚至没有在AVL树的文章中提到斐波那契树（也不是斐波那契数字！），而德语维基百科有一篇非常好的文章完全致力于它们。但对于我的问题，我仍然处于黑暗中。 C语言有点刺耳的黑客是受欢迎的。

如何实现具有延迟传播的分段树？: 我在互联网上搜索了关于Segment树的实现但是在懒惰传播时没有发现任何东西。之前有一些关于堆栈溢出的问题，但他们专注于解决SPOJ的一些特殊问题。虽然我认为这是具有伪代码的分段树的最佳解释，但我需要使用延迟传播来实现它。我发现以下链接： http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Segment_Trees 除了上面的链接，一些博客也在那里，但他们都提供了相同的线程参考。例应用这种数据结构的一个例子就是说，我已经获得了从1到n的一系列数字。现在我执行一些操作，例如向特定范围添加一些常数或从特定范围中减去一些常数。执行操作后，我应该告诉给定数字中的最小和最大数字。一个明显的解决方案是逐个对给定范围内的每个数字执行加法或减法。但是，在没有执行任何操作的情况下，这是不可行的。更好的方法是使用具有延迟传播技术的分段树。它表示不是单独对每个数字执行更新操作，而是跟踪所有操作，直到完成所有操作。然后最后执行更新操作以获得该范围内的最小和最大数量。实际数据示例假设我给出了范围[1,10]，这意味着数字是1,2,3,4,5,6,7,8,9,10。现在假设我执行的操作将范围[3,6]中的数字减少4，所以现在数字看起来像1,2，-1,0,1,2,7,8,9,10。现在我执行另一个操作，将范围[5,9]中的数字增加1，因此数字现在看起来像1,2，-1,0,2,3,8,9,10,10。现在，如果我要求您告诉我最大和最小数字，那么答案将是： Maximum = 10 Minimum = -1 这只是一个简单的例子。实际问题可能包含数千个这样的加法/减法操作。我希望现在很清楚。这是我到目前为止所理解的，但我想互联网上没有统一的链接，可以更好地解释概念和实现。任何人都可以给出一些很好的解释，包括在段树中延迟传播的伪代码吗？谢谢。

二进制搜索算法的平均性能？: http://en.wikipedia.org/wiki/Binary_search_algorithm#Average_performance BinarySearch(int A[], int value, int low, int high) { int mid; if (high value) return BinarySearch(A, value, low, mid-1); else if (A[mid] < value) return BinarySearch(A, value, mid+1, high); else return mid; } 如果我试图找到的整数总是在数组中，有人可以帮我写一个程序，可以计算二进制搜索算法的平均性能吗？编辑：我知道我可以通过实际运行程序和计算调用次数来做到这一点，但我在这里要做的是在不调用函数的情况下执行此操作。 edit2：KennyTM：这是时间复杂度，我正在尝试计算平均呼叫次数。例如，在A [2]中找到整数的平均调用次数，它将是1.67（5/3）

打印日历月: 实现打印给定月份和年份的日历的function。首先，提示用户： Enter the month and year: 一旦用户输入有效输入（由空格分隔的两个整数），以与UNIX cal命令的输出类似的格式打印日历。例如，如果用户输入03 2014 ，则输出应为：我需要帮助才能向用户询问此问题所要求的具体输入。我也无法创建能够根据输入打印不同月份的代码，因为每个月都会在不同的一天开始。我不能使用任何太复杂的东西，因为我正在编程的初学者课程。我到目前为止只编写了3月份的代码： #include int main() { int k, rmd; printf(” March 2014\n”); printf(” Su Mo Tu We Th Fr Sa\n”); for(k = 1; k < 32; ++k) { if(k == 1){ printf(" %2d\n", k); } else if(k % 7 == 1) […]

使用C ++进行2D段/四叉树解释: PS这可能不重复。我搜索了SO并确保我没有得到我想要的东西。我是一个ACM问题求解器，最近我学习了线性数组的Segment Tree和延迟传播的Segment Tree。但是我遇到了一些需要2D段树的问题（在某处被称为Quad树）。但我找不到任何好的教程。我搜索了SO并找到了一个链接http://e-maxx.ru/algo/segment_tree这是一个俄语教程。我需要在2D段树上用源代码（最好用C ++）做一些很好的解释。需要注意的是，我非常了解典型的分段树。

一个很好的参考卡/备忘单与C中的基本排序算法？: 我一直在寻找（没有好运）完美的参考卡与C中的所有基本排序算法（或者可能在伪代码中）。维基百科是一个非常好的信息来源，但这一次我正在寻找一些更便携的东西（如果可能的话口袋大小），当然也可以打印。任何建议将不胜感激！

避免使用srand（）重复生成种子: 我有一个典型的情况，我需要生成一批随机数。我使用了一个循环，每次传递产生100个随机数： for(int i=0; i<npasses; i++) { srand(time(NULL)); //Initialize seed for(int j=0; j<100; j++) printf("%d ", rand()%10); printf("\n"); //New line after 100 numbers } 现在，内循环在不到一毫秒的时间内执行。结果，time（）的值没有变化。这会将种子（srand（））重新初始化为相同的值，并且我的随机数是重复的。任何人都可以建议解决方法/修复。