我一直在尝试以下以下数据结构和算法问题，以寻求更好的解决方案-
给定
$ 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
创建任意长度的位集，例如
定义一个哈希函数，该函数将一对x，y坐标映射到位集中的一位。
从字符串的开头开始，将当前的x和y初始化为零。
对于每个字符，计算散列并检查位集中的相应位。如果设置为if，则使用当前算法，检查是否存在以当前字符结尾的循环，并向后工作。然后设置当前位置的位，根据字符调整x和y并移至下一个字符。
该位集用于快速检查是否有可能在当前字符处结束循环，仅在设置了位的情况下才进行完整检查，以避免在哈希冲突时产生误报，并找到起始位置。循环的特征。如果您想将它们分别计入它们包含的较小的循环中，它还允许您处理多次返回同一位置的更复杂的循环（例如，在十字处开始和结束的图8循环）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句