Tag: 算法

如何计算C中两组之间的差异？

我有两个数组，比如说A和B，| A | = 8，| B | = 4。 我想计算设定差异AB。 我该怎么办？ 请注意，任何一组中都没有重复的元素。 编辑：非常感谢大家提供无数优雅的解决方案。 由于我处于项目的原型设计阶段，现在我实施了Brian和Owen所说的最简单的解决方案。 但我很欣赏你们其他人在这里建议的数据结构的巧妙使用，即使我不是计算机科学家而是工程师，从未将数据结构作为课程进行研究。 看起来是时候我应该真正开始阅读我一直拖延了很长一段时间的CLRS :)再次感谢！

如何找出一个点是否在一组区间内？

我正在寻找最快的方法来决定一条线上的一个点是否在该线的子集内。 给我一个整数Point，我也有一个“列表”： 点，由整数（3,10,1000等）表示 间隔，我用2个整数代表（2:10是从2到10的所有整数，50：60等） 在这个例子中，如果我的点的值是5，那么我返回true，因为它包含在一个区间中，相同的是55.如果我的点等于1000，我也返回true，因为它匹配点列表。 我正在寻找一种快速的方法（比线性更快）来检查这种情况，而不必像可能的点那样实现尽可能多的整数（即，对于1：1000的间隔，我不想实现1000个整数）。 这可以在对数时间内完成吗？ 谢谢 编辑：你可以认为任何时候预处理数据列表等于0，因为一旦我的初始间隔被处理，我需要将这个测试应用到10k点

给定n，找到为n得到的最大数字

问题在oracle面试中提出。例如，如果我的输入是6，那么 5 + 1 = 6答案：2 4 + 2 = 6答案：2 3 + 2 + 1 = 6答案：3 所以，最终答案应该是3.（即获得总和6需要3,2,1） 注意 ：不允许重复数字（即1 + 1 + 1 + 1 + 1 + 1 = 6） 我用递归解决了它，但面试官并不满意。 动态编程是否可行？

自动校正，自动完成function

Hii， 当我们在Ms-word，google等中输入单词时，我们会看到建议……他们是如何做到的？ 我想知道如何执行自动纠正，自动完成，拼写检查等技术。 HOw是实际存储的词……遵循什么算法…… ??? 任何建议可行方式的链接都是受欢迎的，

最大尺寸方形子矩阵，全部为1

给定一个二进制矩阵，我找出了全1 s的最大尺寸方形子矩阵。 例如，考虑以下二进制矩阵： 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 具有所有设置位的最大平方子矩阵是 1 1 1 1 1 1 1 1 1 我在网上搜索了解决方案，并找到了构建辅助矩阵的关系： If M[i][j] is 1 then S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + […]

给定一个整数数组，找到第一个唯一的整数

给定一个整数数组，找到第一个唯一的整数。 我的解决方案：使用std::map 将整数（数字作为键，其索引作为值）逐一放入(O(n^2 lgn)) ，如果有重复，则在将所有数字放入之后从地图中删除条目(O(lg n))映射，迭代映射并找到索引为O（n）最小的密钥。 O(n^2 lgn)因为地图需要进行排序。 效率不高。 更好的解决方案？

CRC中的CRC32算法/实现没有查找表和公共许可证

我试图在C中实现一个不使用查找表的CRC32算法（我需要在没有足够内存可用的引导加载程序中使用它）。 是否有可用的公共许可证解决方案？

如何在O（1）时间内找到二进制数的1？

我知道之前已经问过，但我正在看这里列出的特定解决方案： int BitCount(unsigned int u) { unsigned int uCount; uCount = u – ((u >> 1) & 033333333333) – ((u >> 2) & 011111111111); return ((uCount + (uCount >> 3)) & 030707070707) % 63; } 它是如何工作的？ 这里有什么警告吗？ 理论上可以在恒定的时间内找到答案吗？ 我的意思是，我们不是必须迭代这些位来计算？

可以计算位图中的连续区域是否可以改善O（r * c）？

您将获得由卫星拍摄的表面图像。图像是位图，其中水由’。’标记。 和土地用’ * ‘标记。 相邻的’ * ‘组成一个岛屿。 （如果它们是水平，垂直或对角线的邻居，则两个’ * ‘相邻）。 您的任务是打印位图中的岛数。 示例输入： – ………** **……*** ……….. …*……. *……..*. *………* 输出： – 5 这是我的实现，它采用O(r * c)空间和O(r * c)空间，其中r是总数。 行和c是cols的总数。 #include #define COLS 12 void markVisted(char map[][COLS], int visited[][COLS], int row, int col, int rowCount) { if((row = rowCount) || (col = COLS) || (map[row][col] != ‘*’) […]

理解Visual C ++的rand（）函数的算法

在C / C ++中，当我们想要获得一个随机整数时，我们通常会使用rand()和srand() 。 但是当我试图自己重写它时，我发现很难理解算法。 这个函数很容易写成几行，但公式是误解。 主要配方： ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L; 原始代码涉及： void __cdecl srand (unsigned int seed) { _getptd()->_holdrand = (unsigned long)seed; } int __cdecl rand (void) { _ptiddata ptd = _getptd(); return ( ((ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L) >> 16) & 0x7fff ); }