algorithm - 如何更高效地寻找闭环

Question

我有以下数据结构和算法问题，我一直在想更好的解决方案 -

给定

$x 是经度和$y 是纬度

和后面的字符

'>' 东 $x++ ;'<' 西 $x-- ;'^' 北 $y++ ;'v' 南 $y-- ;

样本输入为字符串"^V<>>><^>v<>^<^>^>>v>><^^<>><<<><<><^<^v<^^v<<>>><<<<^>v^>v^v^<<>>v<><^<>>><>>^><>v^v>v<<>v<>v^^><<>>> v<<>>>>^>v>>”

写一个识别所有闭环的函数(下面给出的一些例子是闭环的例子)[ “^v”, “<>”, “<“, “^>v<“, ...]

我已经能够在 O(n^2) 中解决这个问题，方法是从给定的输入中选择每个字符，然后遍历整个字符串并保留两个计数变量——一个用于垂直计数，另一个用于水平计数，在任何情况下点两者的值都为零然后它是一个闭环。但我想知道是否有人可以更有效地做到这一点 - 也许我错过了一些算法。

感谢和问候，外婆

Answer 1

创建任意长度的位集，例如n.

定义一个哈希函数，将一对 x,y 坐标映射到位集中的一个位。

从字符串的开头开始，将当前的 x 和 y 初始化为零。

对于每个字符，计算哈希并检查位集中的相应位。如果设置了 if 则检查是否有循环以当前字符结束，使用您当前的算法，向后工作。然后设置当前位置的位，根据字符调整x和y并移动到下一个字符。

bitset 用于快速检查循环是否可能在当前字符处结束，仅在设置位的情况下才进行全面检查，以避免在哈希冲突的情况下出现误报，并且找到循环的起始字符。它还允许您处理更复杂的循环，这些循环不止一次返回到同一位置(例如在交叉处开始和结束的数字 8 循环)，如果您想将它们单独计算到它们包含的较小循环。