如何更有效地找到闭环

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)中解决这个问题，方法是从给定的输入中选择每个字符，然后遍历整个字符串，并保持两个计数变量--一个用于垂直计数，另一个用于水平计数，在任何一点上，这两个变量的值都是零，这是一个闭环。但我想知道是否有人能更有效地完成这一任务--也许我遗漏了一些算法。

谢谢和问候，Vaibhav

Answer 1

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

定义一个散列函数，它将一对x，y坐标映射到位集中的位。

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

对于每个字符，计算哈希并检查比特集中的对应位。如果设置了If，那么使用当前算法，检查是否存在以当前字符结尾的循环，并向后工作。然后设置当前位置的位，根据字符调整x和y并移动到下一个字符。

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

Answer 2

我建议在以下几个方面进行讨论：

Map (X,Y) => N  as  visited;

for(int i=0; i<input_str.length; ++i){
    ! update (x,y) per input_str[i];

    if(visited.has(x,y))
    {
        last_visit_index = visited[x,y];
        loop = input_str.substring   last_visit_index to i
    }
    visited[x,y] = i;
}

我是O(N)。