标签: palindrome

我甚至不知道是否存在解决方案.这是问题的细节.您是一个接受无限长字符流的程序(为简单起见,您可以假设字符为1或0).在任何时候,我都可以停止流(让我们说N个字符通过后)并询问你到目前为止收到的字符串是否是回文.如何使用较少的线性空间和/或时间来做到这一点.

假设您正在读取字符流,则在您第一次出现回文时,该函数应该返回.

回文的长度应为偶数.

时间复杂度的要求是O(N).

例:

• 第一个字符:4
• 第二个字符:1
• 第3个字符:3
• 第四个字符:3
• 第五个字符:1
• 第6个字符:4,返回

我知道你可以找到最长的回文子在O(N)与manacher的算法,但有可能找到的总人数在O(N)或O的回文子的(N log n)的？如果是这样,你会怎么做呢？

将单个字母计为回文.

因此,例如," xyxyx " 的回文子串的数量是9.

这是因为你有:

5 single letter palindromes (x,y,x,y,x)
3 palindromes with three letters (xyx, yxy, xyx)
1 palindrome with five letters (xyxyx)

for a total of 5+3+1 = 9 palindromic substrings.

这个问题试图理解其中一个答案:如何使用正则表达式检查字符串是回文？

Markus Jarderot给出的答案是:

/^((.)(?1)\2|.?)$/

有人可以解释一下,到底发生了什么......我需要做类似的事Perl,但不能理解这个解决方案!

PS:我在perl方面不是很好所以请放轻松......而且"如果你想要严格的话,这不能算是正则表达式 " - 我读了这一行,所以我知道这不是正则表达式严格

这是我对回文的归纳定义:

Inductive pal { X : Type } : list X -> Prop :=
  | pal0 : pal []
  | pal1 : forall ( x : X ), pal [x]
  | pal2 : forall ( x : X ) ( l : list X ), pal l -> pal ( x :: l ++ [x] ).

我想从Software Foundations中证明这个定理:

Theorem rev_eq_pal : forall ( X : Type ) ( l : list X ),
  l = rev l -> …

我写了下面的代码来检查它是否是回文.我还创建了在列表不是回文时插入元素的逻辑

reverse_list(Inputlist, Outputlist) :-
   reverse(Inputlist, [], Outputlist).    

reverse([], Outputlist, Outputlist).    
reverse([Head|Tail], List1, List2) :-
   reverse(Tail, [Head|List1], List2).

printList([]).
printList([X|List]) :-
   write(X),
   write(' '),
   printList(List).

palindrome(List1) :-
   reverse_list(List1, List2),
   compareLists(List1, List1, List2, List2).

compareLists(L1, [], [], L2) :-
   write("\nList is Palindrome").    
compareLists(L1, [X|List1], [X|List2], L2) :-
   compareLists(L1, List1, List2, L2),
   !.        
compareLists(L1, [X|List1], [Y|List2], [Z|L2]) :-
   write("\nList is not Palindrome. "),
   append(L1, L2, L),
   printList(L).

代码给出了正确的输出

palindrome([a,b,c,a]).
List is not Palindrome. a b c a c b a 

palindrome([a,b,c]).
List is …

我需要帮助编写一个递归函数来检测字符串是否是回文.但我不能使用任何循环,它必须是递归的.任何人都可以帮我告诉我这是如何完成的.我需要为即将到来的中期学习这个.我正在使用Python.

1. 我是否可以获得具有两个参数的递归Prolog谓词,称为reverse,它返回列表的反转:

   示例查询和预期结果:

   ?- reverse([a,b,c], L).
   L = [c,b,a].
   

2. 两个参数的递归Prolog谓词,palindrome如果给定列表是回文,则返回true.

   具有预期结果的示例查询:

   ?- palindrome([a,b,c]).
   false.
   
   ?- palindrome([b,a,c,a,b]).
   true.
   

给定一个长度为N的字符串[AZ],如何确定单个字符的最长回文？

我将用一个例子来说明这一点:

给定字符串:JOHNOLSON 在分析字符串时,我们发现我们有一个带有字符的回文O使得字符串看起来像.它的回文长度基本上看起来像7 .另外,请注意有一个回文,但它只有6个长度.JOHNOLSONOO--O--ON

另一个例子,给定字符串:ABCJOHNOLSON给出与上面相同的结果,其中O长度为7 的回文看起来像.O--O--O

但是,对于给定的字符串ABCJOHNOLSONDA,最长的单个字符回文长度为14,字符A看起来像.A------------A

其他简单的例子包括:

ABA- > (长度3)A-A

ABAXYZ- > (长度3)A-A

ABAXYZA- > (长度5),而不是长度7因为不是信件的回文.A---AA-A---AA

特别注意最后一个例子,因为它说明了问题的一个微妙的细微差别.

我正在尝试解决这个编程难题:

给出正整数N(0 <N <10).你的任务是打印一个大小为N的回文三角形.

例如,大小为5的回文三角形是:

1
121
12321
1234321
123454321

Run Code Online (Sandbox Code Playgroud)

你不能超过两行.您必须使用一个print语句来完成代码.

注意:使用与字符串相关的任何内容都会得分为0.使用多个for-statement将得分为0.

我只能想到'愚蠢'的方式来做到这一点:

for i in range(1, N+1):
    print([0, 1, 121, 12321, 1234321, 123454321, 12345654321, 1234567654321, 123456787654321, 12345678987654321][i])

有更优雅的解决方案吗？