gpt4 book ai didi

algorithm - 在链表中查找回文

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:36:46 25 4
gpt4 key购买 nike

这又是一道面试题。

Given a singly connected linked list, find the largest palindrome in the list. (You may assume the length of the palindrome is even)

我采用的第一种方法是使用堆栈 - 我们从头开始遍历列表并不断插入字母。每当我们发现堆栈顶部的字母与链表中的下一个字母相同时,就开始弹出(并递增链表指针)并设置匹配字母数的计数。在我们发现不匹配后,将您从堆栈中弹出的所有字母推回,并继续您的插入和弹出操作。此方法的最坏情况复杂度为 O(n2),例如当链表只是一串相同字母的时候。

为了提高空间和时间复杂度(通过一些常数因子),我建议将链表复制到数组中并在数组中找到最大的回文,这同样需要 O(n2) 时间复杂度和 O(n)空间复杂度。

有什么更好的方法可以帮助我吗? :(

最佳答案

可以想出一个 O(n²) 空间复杂度为 O(1) 的算法,如下所示:

考虑f→o→b→a→r→r→a→b:

在访问时通过列表反转链接。从 x=fy=f.next 开始:

  • 设置x.next = null
  • f o→b→a→r→r→a→b^ ^|  \x   y
    并检查两个列表(x 和 y)相等的链接数。
  • 现在继续。 (tmp=y.next, y.next=x, x=y, y=tmp)例如。在第二步中,它将产生 f←o b→a→r→r→a→b,其中 x=oy=b,现在你再次检查它是否是回文并继续:
  • f←o←b a→r→r→a→b
  • f←o←b←a r→r→a→b
  • f←o←b←a←r r→a→b 是的:)
  • 等等

如果需要再次恢复链表,在O(n)内再次反转

关于algorithm - 在链表中查找回文,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7049210/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com