假设您正在从字符流中读取，当您读取第一次出现的回文时，该函数应该返回。
回文的长度应该是偶数。
时间复杂度的要求是O(N)。
例子：
- 第一个字符：4
- 第二个字符：1
- 第三个字符：3
- 第四个字符：3
- 第 5 个字符：1
- 第6个字符：4，返回
问问题
1567 次
8 回答
3
当你读到第一个字符时返回，这是一个单字母回文。
于 2012-04-09T05:24:49.923 回答
3
您需要对Manacher's Algorithm稍作修改。它允许您在线性时间内找到字符串中的所有回文。关于算法的事情，它实际上从左到右进行，在需要时“使用”新字符。所需的修改是您需要读取新字符，仅当您尝试访问它时。
停止，如果你找到回文，那会一直追溯到流的开头。
于 2012-04-09T06:14:46.820 回答
3
在大多数情况下，应该在线性时间 O(n) 内运行的一种近似解决方案是使用滚动哈希。
您跟踪字符串的哈希值及其反向。每次读取一个新字符时，都可以更新 O(1) 中的两个哈希值。然后比较两个哈希值，如果它们相等，则比较字符串及其保留值。如果这也是相等的，退出并且你得到一个回文。
例如，一个非常简单的滚动哈希函数是 hash(ck c(k-1).. c0) = (p^k*ck + p^(k - 1) * c(k - 1) + ... + c0 ) mod m 其中 p 是奇素数。
所以开始：
p = 17 // or your lucky prime number
m = 10^9 // ...
hash = 0
hash_rev = 0
str = ''
str_rev = ''
p_pow = 1
while True
read c
append c to str
prepend c to str_rev
hash = (hash * p + c) mod m
hash_rev = (hash_rev + p_pow * c) mod m
p_pow = p_pow * p
if hash == hash_rev
if str == str_rev
found str to be the first palindrome
为了使其更快，您可以将哈希和 hash_rev 清除为 32 位整数并选择 m = 2^32。然后你可以忽略 (mod m) 操作。
于 2012-04-09T06:58:30.177 回答
0
这个（未经测试的 C#）代码可以做到，但我认为它可能是 O(n^2)。任何人都可以确认/否认吗？
main()
{
string str = "";
char c1;
char c2;
while(true)
{
//has to be even, always get two chars at a time
c1 = GetCharFromStream();
c2 = GetCharFromStream();
str += c1 + c2;
if(isPalindrome(str))
{
Console.WriteLine(str);
return;
}
}
}
bool isPalindrome(string str)
{
if (str.Length % 2 != 0)
throw new InvalidArgumentException("str");
int first = 0;
int last = str.Length - 1;
while(first <= last)
{
if(str[first] != str[last])
return false;
first++;
last--;
}
return true;
}
于 2012-04-09T05:40:11.067 回答
0
使用 Hashset 怎么样？
假设输入流是1221.
Hashset = empty;
if(hashset does not contain the inputelement)
{
add to hashset. // 12 will be in the hashset. //413 for your example.
}
else
{
delete from Hashset. // First deletes 2 and then 1. // First deletes 3, then 1 then 4.
if(hashset is empty)
return true; //Hashset is empty. return true.
}
于 2012-04-10T05:05:19.830 回答
0
这是我的看法。它从字符串的当前中间扫描每个新符号上的累积字符串，因此如果当前字符串不是回文，它将快速失败。
class PalindromeDetector {
private static class DetectorImpl {
final ArrayList<Character> string = new ArrayList<Character>(32);
boolean addSymbol(char symbol) {
string.add(symbol);
return check();
}
private boolean check() {
if (string.size() < 2)
return false;
int lowBound = string.size() / 2 - 1;
int hiBound = lowBound + 1;
while (lowBound >= 0 && string.get(lowBound) == string.get(hiBound)) {
lowBound --; hiBound ++;
}
return lowBound == -1;
}
}
static boolean isPalindrome(String s) {
DetectorImpl detector = new DetectorImpl();
int index = 0;
while (index < s.length())
if (detector.addSymbol(s.charAt(index++)))
return true;
return false;
}
}
这是代码的单元测试：
@Test
public void test() {
assertFalse(PalindromeDetector.isPalindrome("4"));
assertTrue(PalindromeDetector.isPalindrome("44"));
assertFalse(PalindromeDetector.isPalindrome("4343"));
assertTrue(PalindromeDetector.isPalindrome("4334"));
assertFalse(PalindromeDetector.isPalindrome("41331"));
assertTrue(PalindromeDetector.isPalindrome("413314"));
}
于 2012-04-10T16:16:26.480 回答
0
好的，因为我的第一个答案具有O(n^2)时间复杂性，所以这是另一个，O(n)按要求。
class PalindromeDetector {
private static class DetectorImpl {
int firstHalfSum, secondHalfSum;
int size = 0, tensPower = 1;
boolean add(int v) {
if (size % 2 == 1) {
firstHalfSum = firstHalfSum + (secondHalfSum / tensPower) * tensPower;
secondHalfSum = (secondHalfSum % tensPower) * 10 + v;
if (firstHalfSum == secondHalfSum)
return true;
} else {
secondHalfSum = secondHalfSum * 10 + v;
}
size ++;
if (size % 2 == 0)
tensPower *= 10;
return false;
}
}
static boolean isPalindrome(String s) {
if (s == null || s.length() == 0)
return false;
int val = Integer.parseInt(s);
int tensPower = s.length() == 1 ? 1 : (int) (Math.pow(10, s.length() - 1));
DetectorImpl detector = new DetectorImpl();
while (tensPower > 0) {
int digit = val / tensPower;
if (detector.add(digit))
return true;
val = val % tensPower;
tensPower /= 10;
}
return false;
}
}
这是单元测试：
@Test
public void test() {
assertFalse(PalindromeDetector.isPalindrome("4113"));
assertTrue(PalindromeDetector.isPalindrome("3443"));
assertTrue(PalindromeDetector.isPalindrome("473374"));
assertTrue(PalindromeDetector.isPalindrome("413314"));
}
答案假设输入由十进制数字组成，但可以很容易地扩展为字母数字输入（假设英文字母 + 10 位为我们提供基于 36 的数字系统）。
于 2012-04-11T20:47:16.157 回答
0
这个解决方案（在 Haskell 中）依赖于对偶数长度回文在其中心包含重复字符的观察。当我们从输入流中读取字符时，我们会测试这样的对，当找到一个时，我们会播种一个新的候选答案。对于每个候选回文，我们还保留一个“剩余要匹配的字符”列表，并且在读取每个新字符时，我们将其与该列表进行匹配——如果没有匹配，候选者将被丢弃。当匹配列表为空时，已找到解决方案。请注意，虽然每个候选者都维护自己的匹配列表，但这些都只是同一列表的后缀，因此在 Haskell 中，这些都将共享空间，并且即使有很多候选者，它们也不会占用超过 O(n) 的空间。
在答案中心只有一个配对字符并且因此没有“误报”候选者的最佳情况下，时间复杂度为 O(n) - 每个字符检查不超过两次。对于具有许多错误开始的输入字符串，即“abbbbbbbbbbbbba”，我不确定时间复杂度 - 它可能不再是 O(n) 但它比 O(n^2) 更好，因为没有候选人能活得更久min(k, n-k)而不是k候选人中心的位置。
filter_map::(a -> Maybe a)->[a]->[a]
filter_map op = foldr (maybeCons . op) []
where maybeCons Nothing ys = ys
maybeCons (Just y) ys = y:ys
-- Return the first prefix of the input argument that
-- is an even-length palindrome.
prefix_palindrome::(Eq a)=>[a]->[a]
prefix_palindrome (x:xs) = search [x] [] xs
where search seen ([]:_) _ = seen
search (s:seen) candidates (x:xs) | x == s = search seen' (candidates' ++ [seen]) xs
| otherwise = search seen' candidates' xs
where seen' = (x:s:seen)
candidates' = filter_map extend candidates
where extend (c:cs) | c == x = Just cs
| otherwise = Nothing
于 2012-04-14T01:10:38.320 回答