问题标签 [array-algorithms]

我正在尝试建立一个后缀范围

如果我有字符串 "catalog" "catalyst" "ban" "bany"

然后后缀树就像

我现在想找到每个字符串的后缀范围 .. 如果我使用字符串“Cat”，那么它应该给我一个包含其所有后缀的范围，其中“cat”是一个前缀。我需要使用哨兵来分隔每个字符串..可能是“$”

任何人都可以建议我使用 c++ 找出这一点的最佳方法。任何参考资料都会有所帮助。谢谢你

在一个应用程序中，我测量了许多图案的二维坐标 (x,y)。该模式由网格上的一组点组成，在 x 和 y 方向具有固定间距。这些坐标都有一个质量分数，并按这个分数排序。我想要做的是首先在 x 上对这些坐标进行排序，并定义属于一起的 x 坐标组（区域）。在这一步之后，我想对 y 区域中的不同 x 区域进行排序。

在此之后，我可以将坐标标记为相应的模式（网格）标签。

示例：测量坐标 (x,y)= (2,2),(2,3),(1,2),(1,3),(2,1),(1,1),(3,2 ),(3,3),(3 ,1)

在步骤 1 之后： (x,y)= (1,2),(1,3),(1,1) (2,2),(2,3),(2,1) (3,2), (3,3),(3,1)

在第 2 步之后：(x,y)= (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1 ),(3,2),(3 ,3)

是否有已经执行此任务的排序例程？如果不测量图案的某些坐标，该例程也应该有效。

有人可以给我一些线索吗，我不是一个经验丰富的 c++ 程序员，但也许有一些提示我可以完成这项工作！

编写将比较 n 个列表并返回所有未出现在所有列表中的所有值的方法的最有效方法是什么？

以便

列表.GetNonShared();

返回 1、5、8、9、10

我有

但我不确定这是否有效。顺序无所谓。谢谢！

我在准备考试时遇到了这个问题。

给定两个数字数组 a1,..., an 和 b1,....,bn，其中每个数字为 0 或 1，找到最大跨度 (i,j) 的最快算法使得 , ai + ai+1 +....+aj = bi + bi+1 +....+bj 或报告没有这样的跨度。

(A) 如果允许散列，则需要 O(3^n) 和 omega(2^n) 时间。

(B) 在关键比较模式下需要 O(n^3) 和 omega(n^2.5) 和时间

(C) 占用 theta(n) 时间和空间

(D) 仅当 2n 个元素之和为偶数时才花费 O(square-root(n)) 时间。

可能吗？如果不是，给定一个大小为 n 的数组，我怎么知道对数组进行排序是否更好？

您有一个包含 n=2k+2 个元素的数组，其中 2 个元素没有配对。8 个元素数组的示例：1 2 3 47 3 1 2 0。“47”和“0”在数组中没有配对。如果我有一个只有 1 个元素没有配对的数组，我用 XOR 解决这个问题。但我有 2 个未配对元素！我能做些什么？解决方案可能是 O(n) 时间性能和 O(1) 额外内存。

想象一个 3x3 的网格：

百分比%代表空白/位置。

这些行可以像串上的珠子一样移动，这样第一行的配置排列可以是以下任何一个：

第二行也是如此。第三行不包含空槽，因此无法更改。

考虑到每一行的可能排列，我正在尝试生成所有可能的网格。

输出应产生以下网格：

我尝试了一种查看每一行并左右移动空间的方法，然后从中生成新的网格并递归。我将所有网格保存在一个集合中，并确保我只生成尚未检查的位置以防止无限递归。

但是，我的算法似乎效率极低（每个排列约 1 秒！！）而且看起来也不是很好。我想知道是否有一种雄辩的方式来做到这一点？特别是在python中。

我有一些模糊的想法，但我确信有一种方法可以做到这一点，我忽略了它的简短而简单。

编辑： 3x3 只是一个例子。网格可以是任何大小，真正重要的是行组合。例如：

也是一个有效的网格。

编辑2：字母必须保持顺序。例如[A, %, B] != [B, %, A]并且[B, A, %]无效

我在面试中被问到一个问题，在 O(n) 时间内对一个二维数组进行排序。如何在 O(n) 中做到这一点。有人能解释一下吗.. 谢谢。

输入：

输出

我想检查列表值是否具有某种程度的“接近性”。有没有一个好的算法来做到这一点？最pythonic方式的奖励积分。

有效的

无效

这将是一个很长的问题，请在阅读之前深呼吸。

我想了解将一维数组的索引转换为多维数组的向量索引的最快算法是什么。

让我们通过一个例子来理解我为什么需要它：

我有一个二维数组： Array[i1][i2]

i1 从 i1_b=0 运行到 i1_e=2

i2 从 i2_b=0 运行到 i2_e=1

所以这个数组被逐行输出到文件中：

数组[0][0]

数组[0][1]

数组[0][2]

数组[1][0]

数组[1][1]

数组[1][2]

现在我逐行读取文件，索引 k 是最后读取的行号。

我读了第一行是 Array[0][0] 和 k=0

我读了第二行，即 Array[0][1] 和 k=1

...

可以注意到 k 将从 k_b=0 运行到 k_e=5 并且

k=0 将对应于 i1=0, i2=0

k=1 将对应于 i1=0, i2=1

...

问题：所以我的问题是如何以最快的方式将 k 转换为 i1 和 i2？（我在读取文件时不需要它，但稍后在我的程序中）

在此示例中，解决方案之一是

i1=k/(i1_e - i1_b + 1);

i2=k%(i1_e - i1_b + 1);

问题 1：就周期和计算机时间而言，这是最快的解决方案吗？

好的。问题 2：我们如何将这个算法推广到多维数组？

数组[i1][i2][i3][i4]

i1=k/(i1_e - i1_b + 1);

i2=k%(i1_e - i1_b + 1);

i3=i2/(i1_e - i1_b + 1);

i4=i2%(i1_e - i1_b + 1);

问题3：这是最快的方法吗？

问题 4：相关问题是模除法、整数除法、整数相加和整数相乘的延迟是多少？如果这些数字取决于架构，请告诉我。

提前致谢！

PS 有人可能更容易将此问题视为将秒转换为天-小时-分钟-秒的最快算法。