Tag: 算法

在重复元素XOR运算符的数组中找到两个非重复元素？

假设我有一个包含2n + 2个元素的数组。 数组中的n个元素出现两次，剩下的两个元素是唯一的。 你必须在O（n）时间和O（1）空间中解决这个问题。 其中一个解决方案是使用XOR。 但我无法理解这一点。 任何人都可以帮助我，或者可以给我更好的解决方案吗？ 问题和解决方案的链接就是这个

算法从中间向外循环一个数组？

我正在研究一种分而治之的算法（事实上，这种算法可以对多个输入点进行曲线拟合）。 对于“除法”部分，我需要计算每个点的误差项，如果误差超过给定的阈值，我希望在该点分割曲线并分别处理输入的左右部分。 一个简单的循环就可以了; 但是对我来说，从当前部分的中间开始并向外工作将是有利的。 （澄清一下：如果我找到一个误差太大的点，我会递归调用并为左右两部分生成单独的曲线 – 如果所有点都在阈值范围内，那么我的曲线适合我返回）。 经过一番搔痒之后，我想出了这个（点数在一个数组中，当前部分是从startIndex到endIndex ）： int steps = (endIndex+1-startIndex); int i = (startIndex+endIndex)>>1; int stepdir = 1; for(int q=0; q<steps; q++, i+=stepdir*q, stepdir=-stepdir) { // test point i here and return early if error exceeds threshold } 换句话说，从中间开始，前进一个指数，前进两个，前进三个，后退四个……它有效，我确信它是有效的，但它让我感到应该有一个更清洁的方法来做到这一点特别是，我最终必须检查Java语言规范，以确保for update表达式中的语句按顺序进行评估（即使它不是C / C ++中的序列运算符）。 感谢任何想法。 有更干净的方式吗？

N皇后放置算法

我正在解决N皇后问题，我们需要在NXN棋盘上放置N个皇后，这样两个皇后就不会互相攻击。 #include #include #include int size=8; char arr[8][8]; int i,j; void initializeBoard() { for(i=0;i<size;i++) { for(j=0;j<size;j++) { arr[i][j]='.'; } } } void printArray() { for(i=0;i<size;i++) { for(j=0;j<size;j++) { printf("%c\t",arr[i][j]); } printf("\n"); } printf("\n\n"); } void placeQueen(int i,int j) { arr[i][j]='Q'; } int isAvailable(int i,int j) { int m,n,flag; for(m=0;m<i;m++) { for(n=0;n<size;n++) { int k=abs(im); int […]

将未排序的连续字符串数组有效地排序到文件中

我有一个包含无序连续数字的字符串数组（范围从0到n），例如[7a, 1b, 2c, 0d, 6e, 5f, 3g, 4h] ，我想将数字按顺序写入文件。 例如： 0d 1b 2c 3g 4h 5f 6e 7a 字符串的长度不尽相同。 我试图找到一种方法，既快速又无需占用太多​​空间。 我找到了一种方法，我可以在O（n）空间复杂度和O（n）性能中做到这一点：我创建一个包含n个单元格的数组，并将每个字符串插入到他的单元格编号中。 for (i = 0; i < n; i++) sortedArray[originalArray[i]] = originalArray[i] …类似的东西（创建原始大小的新数组并在一次运行中填充），然后与另一个for循环将已排序数组的内容写入文件。 但我正在寻找一种更好的方法来做到这一点。

在C中寻找循环单个转置向量

我有输入数组A = [ 2,3,4,1] 输出只是A中元素的所有可能的排列，这可以通过单个转置（两个相邻元素的单个翻转）操作来完成。 所以输出是： [3,2,4,1],[ 2,4,3,1],[2,3,1,4],[1,3,4,2] 允许圆形换位。 因此允许[2,3,4,1] ==> [1,3,4,2]并输出有效值。 怎么用C做？ 编辑在python中，它将按如下方式完成： def Transpose(alist): leveloutput = [] n = len(alist) for i in range(n): x=alist[:] x[i],x[(i+1)%n] = x[(i+1)%n],x[i] leveloutput.append(x) return leveloutput

如何在C中随机混洗链表

我有一个链表，我想实现一个function： Random_Shuffle_List (struct node **Headptr) – 输出一个列表，使每个节点从其原始位置随机移动。 请帮我一个有效的算法来实现这一目标。

64位除法

任何人都可以给我发送交流代码来划分2个64位数字。 我的编译器只支持32/32分区。 Thanx＆Regards 玛尼

MPI：在完成工作后帮助另一个人

这是我的问题： 给定一个初始间隔[a，b]进行并行化并假设流程比其他流程更快，我想做一个流程，当它完成其块（工作）时，我会“帮助”另一个（j），帮助这个case意味着在它和进程i（将要帮助的那个）之间平均分割进程j的块（它仍在工作的块）。 我已经了解了这个算法，但我不知道如何使用MPI通信function（如Broadcast，Allgather，send，recv）来实现它：我想使用所有进程共享的数组“arr” ＆size的大小等于所有进程的数量。 arr [i] = 1表示进程i已完成工作，否则等于-1。 我将其所有元素初始化为-1，当排名“rank”的进程完成其工作时，它确实arr [rank] = 1并且等待工作进程注意它并向它发送新块。 这是我想要实现的“伪代码”： MPI_Init ( &argc, &argv ); MPI_Comm_rank ( MPI_COMM_WORLD, &rank ); MPI_Comm_size ( MPI_COMM_WORLD, &nb_proc ); int i; int a = 0, b = max; //initial interval [a,b] to parallelize int j; arr[nb_proc]; for(j = 0; j < 10; j++) { arr[j] = […]

如何从具有userID和pageID的大型日志文件中查找最常访问的3网页序列

给定访问的网页日志文件： Userid PageID A 1 A 2 A 3 B 2 B 3 C 1 B 4 A 4 查找最常访问的页面ID访问顺序： for A : 1-2-3, 2-3-4 for B : 2-3-4 所以，2-3-4是最常见的。 我的想法： 将文件的每个项目放入map1<key:user_id, list > 。 当list.size() == 3 ，创建一个新的struct three_hits来保存三个pageID。 将它放入map2 。 然后，在map2中找到具有最大计数器值的项目。 声明： struct three_hits { int f_page; int s_page; int t_page; }; map<string, […]

当没有数据类型可以保存完整数字时，将hex转换为十进制

好的，所以我在C中使用PIC微处理器。它是一个16F，因此它不能保存大于32位的整数（unsigned int32是可用的最大数据量） 从阅读器，我收到一个5字节的ID代码。 为了传输它，我必须逐位编码为BCD。 我无法将其打印到字符串，因为它比数据大小大，并且无法处理它。 我无法分割它，因为没有为它定义操作。 我无法找出任何解决方案，有没有人以前处理过这个问题？ 编辑： 我收到一系列5个字节的数字：“FF-FF-FF-FF-FF”。 我需要将其转换为十进制“0123456789012”（13位数，长度为256 ^ 5十进制），以通过RS232发送。 第二个函数（使用ASCII，并发送它）我已经有它工作，但我需要完整数字的字符串表示，然后我可以用它做任何事情。