arrays - 统一具有恒定空间的目录路径的算法

Question

我正在做一些编码练习，但在实现统一目录路径的功能时遇到了一些问题。

Example:

• Input: /dir1/dir2/../dir3/file.txt

• Output: /dir1/dir3/file.txt

我们可以使用堆栈来解决 O(n) 时间/空间复杂度的问题。但是我们不想使用额外的空间。

我们如何解决这个空间复杂度为 O(1) 的问题？我正在努力寻找就地解决方案。

Answer 1

我认为，虽然没有写过它，但您可以通过额外的指针购买。由于最后，您主要只是进行轮类，您可以简单地让一个指针代表您当前扫描字符串的位置，然后将另一个指针作为字符串中的目标位置。关键是您在使用过程中主动使用字符串。

例如:

/dir1/dir2/../dir3/file.txt

当您点击 .. 时，您的“当前指针”将保留在 /dir3 的 / 上。

然后使用目标指针从 .. 向上扫描到 /dir2 的 /。

完成目标指针后，将当前指针(/dir3 的 /)中的所有内容向上移动到字符串中，同时调整当前指针去吧。

然后您冲洗并重复直到完成。 /./ 路径也会发生同样的事情。同样的就地消费即可。

您可以在过渡期间使用目标指针来记录当前标记的开始，但基本上您只是在将字符串移动到位时上下扫描字符串。

这只是一个猜测，需要 200 万的思考才能输入。