Python:每日一题 42

ooxx7788

难一点的题目翻译题目太长了，今天出个简单一些的吧。
文字回文联
要求：
1、给定字符串是不能改动。
2、生成的回文联应当尽量短。
3、当有多种可能的情况时，给定文字处于起始位置的优先。列入例子中的，ab。当然bab也是结果，但是因为aba中ab处于开始位置，所以aba优先。

1. makePalindrome('a') --> 'a'
   
2. makePalindrome('ab') --> 'aba'
   
3. makePalindrome('abc') --> 'abcba'
   
4. makePalindrome('race') --> 'racecar'
   
5. makePalindrome('leveled') --> 'deleveled'                #注意哦，这个策略有点不一样的哦。

复制代码

测试代码：

1. test.assert_equals(makePalindrome('ab'), 'aba');
   
2. test.assert_equals(makePalindrome('abb'), 'abba');
   
3. test.assert_equals(makePalindrome('abc'), 'abcba');
   
4. test.assert_equals(makePalindrome('rad'), 'radar');
   
5. test.assert_equals(makePalindrome('race'), 'racecar')

复制代码

本题冬雪的答案已然很简单了，所以我就给个链接吧!
http://bbs.fishc.com/forum.php?mod=redirect&goto=findpost&ptid=87034&pid=2886595

新手·ing

@冬雪雪冬 @jerryxjr1220 @lumber2388779

jerryxjr1220

没理解题目，要去处重复？

新手·ing

jerryxjr1220 发表于 2017-5-10 17:01
没理解题目，要去处重复？

生成回文联

ooxx7788

jerryxjr1220 发表于 2017-5-10 17:01
没理解题目，要去处重复？

不要去重复，要保留原有的字符串。
在原有的字符串加工成回文。

jerryxjr1220

主要不理解的是如果ab的回文是aba, 那么leveled的回文怎么可以deleveled?
如果这个可以，那么ab生成bab应该也可以啊？

ooxx7788

jerryxjr1220 发表于 2017-5-10 17:46
主要不理解的是如果ab的回文是aba, 那么leveled的回文怎么可以deleveled?
如果这个可以，那么ab生成bab应 ...

是可以啊，但是还有第3条要求啊。

1. 3、当有多种可能的情况时，给定文字处于起始位置的优先。列入例子中的，ab。当然bab也是结果，但是因为aba中ab处于开始位置，所以aba优先。

复制代码

jerryxjr1220

ooxx7788 发表于 2017-5-10 17:53
是可以啊，但是还有第3条要求啊。

就是要生成从头循环的和从尾循环的，再比较那个循环短，一样短的再优先取从头循环的？
逻辑是这样？

ooxx7788

jerryxjr1220 发表于 2017-5-10 17:56
就是要生成从头循环的和从尾循环的，再比较那个循环短，一样短的再优先取从头循环的？
逻辑是这样？

我认为是这样吧。
其实题目的难点，我认为是在于如果给定单词部分存在可以形成回文的结构，如何判定并利用这个回文结构。
而普通单词必然是在最后一个字母后面接一段前文翻转最短。
例如level本身就是回文词，leveled就要在这个基础上利用回文。
class，ss本身也是回文结构，所以要返回classalc。
popular,pop本身是回文结构，所以要在这个回文的基础上反转，变成ralupopular。

冬雪雪冬

先判断字符串中有无回文部分，如果有利用次部分，但回文部分只能在两端才有用。

1. def makePalindrome(string):
   
2.     for i in range(len(string), 1, -1):
   
3.         if string[:i] == string[i - 1::-1]:
   
4.             return string[: i - 1: -1] + string
   
5.     for i in range(-len(string), -1):
   
6.         if string[i:] == string[:i - 1:-1]:
   
7.             return string + string[i - 1::-1]
   
8.     return string + string[-2::-1]
   
9. 
   

复制代码

jerryxjr1220

ooxx7788 发表于 2017-5-10 18:12
我认为是这样吧。
其实题目的难点，我认为是在于如果给定单词部分存在可以形成回文的结构，如何判定并 ...

1. def get_string(string):
   
2.     sub = ''
   
3.     for i in range(1, len(string)):
   
4.         if string[:i + 1] == string[i:2 * i + 1][::-1]:
   
5.             sub = string[:i]
   
6.     if sub != '':
   
7.         newstring = string[len(sub):]
   
8.     else:
   
9.         newstring = string
   
10.     return newstring
    
11. 
    
12. def recycle(string):
    
13.     newstring = get_string(string)
    
14.     newstring = newstring[::-1] + newstring[1:]
    
15.     newantstring = get_string(string[::-1])[::-1]
    
16.     newantstring = newantstring + newantstring[:-1][::-1]
    
17.     if len(newstring) < len(newantstring):
    
18.         return newstring
    
19.     else:
    
20.         return newantstring
    
21. 
    
22. print(recycle('popular'))

复制代码

按照这个逻辑写的，没有验证过

ooxx7788

jerryxjr1220 发表于 2017-5-10 20:53
按照这个逻辑写的，没有验证过

1. print(recycle('abb'))
   
2. abbba
   

复制代码

不对哟

jerryxjr1220

ooxx7788 发表于 2017-5-10 20:57
不对哟

嗯，我只判断了奇数位的回文，还有偶数位的回文漏了

版主的代码比较简洁 ，那我的就不写了

badaoqingchen

冬雪雪冬 发表于 2017-5-10 20:06
先判断字符串中有无回文部分，如果有利用次部分，但回文部分只能在两端才有用。

摩拜单车

当回首遇上转身

最后一个还没解决，先发着占楼先

1. #!/usr/bin/env python3
   
2. # -*- coding: utf-8 -*-
   
3. 
   
4. '''
   
5. Created on 2017.05.10 20:17
   
6. @author: 当回首遇上转身
   
7. '''
   
8. 
   
9. 
   
10. def a_mix(shuru):
    
11.     a = []
    
12.     shuchu = ''
    
13.     for i in range(len(shuru)):
    
14.         if shuru[len(shuru)-1-i:len(shuru)-i] != shuru[len(shuru)-1]:
    
15.             while i != len(shuru):
    
16.                 a.append(shuru[len(shuru)-1-i:len(shuru)-i])
    
17.                 i += 1
    
18.             break
    
19.     a.insert(0,shuru)
    
20.     for each in a:
    
21.         shuchu += each
    
22.     return shuchu
    
23. 
    
24. def makePalindrome(shuru2):
    
25.     b = []
    
26.     shuru1 = ''
    
27.     for i in range(len(shuru2)):
    
28.         shuru1  = shuru1 + (shuru2[len(shuru2)-1-i:len(shuru2)-i])
    
29. 
    
30.     a2 = a_mix(shuru1)
    
31.     a1 = a_mix(shuru2)
    
32.     print("'",end = '')
    
33.     if len(a1) > len(a2):
    
34.         print(a2,end = '')
    
35.         
    
36.     else:
    
37.         print(a1,end='')
    
38.     print("'")
    
39. 
    
40. makePalindrome('race')
    

复制代码

当回首遇上转身

没错，我又回来了

1. #!/usr/bin/env python3
   
2. # -*- coding: utf-8 -*-
   
3. 
   
4. '''
   
5. Created on 2017.05.10 20:17
   
6. @author: 当回首遇上转身
   
7. '''
   
8. 
   
9. def Input_mix(shuru1,shuru2):
   
10.     shuchu = ''
    
11.     for k in range(len(shuru1)):
    
12.         if shuru1[len(shuru1)-1-k:] == shuru2[:k+1]:
    
13.             j = (len(shuru1)-1-k)
    
14.         k += 1
    
15.     shuchu = shuru1[:j] + shuru2
    
16.     return shuchu
    
17. 
    
18. def makePalindrome(shuru):
    
19.     shuru1 = ''
    
20.     for i in range(len(shuru)):
    
21.         shuru1  += (shuru[len(shuru)-1-i:len(shuru)-i])
    
22. 
    
23.     a2 = Input_mix(shuru1,shuru)
    
24.     a1 = Input_mix(shuru,shuru1)
    
25.     print("输出字符为：'",end = '')
    
26.     if len(a1) > len(a2):     
    
27.         print(a2,end = '')
    
28.     else:
    
29.         print(a1,end = '')
    
30.     print("'")
    
31. 
    
32. while 1:
    
33.     Input = input("请输入字符：")
    
34.     makePalindrome(Input)

复制代码

用了好多局部变量有点乱别见怪，逻辑是这样没办法

程序输出：

1. ====== RESTART: C:\Users\Tony\OneDrive\文档\practice\2017.05.10\huiwen.py ======
   
2. 请输入字符：a
   
3. 输出字符为：'a'
   
4. 请输入字符：ab
   
5. 输出字符为：'aba'
   
6. 请输入字符：abc
   
7. 输出字符为：'abcba'
   
8. 请输入字符：race
   
9. 输出字符为：'racecar'
   
10. 请输入字符：leveled
    
11. 输出字符为：'deleveled'

复制代码

solomonxian

从0开始到n-1，逐步缩短字符串，找出往前回文和往回后文的边界，
输出最先找到的（最短）

1. # 正反两个方向循环切片判断回文边界，至少切边长度为1时成立，根据边界拼接最短的
   
2. def makePalindrome(s):
   
3.     """最短回文制造器，为您的输入s制造回文"""
   
4.     i = 0
   
5.     while 1:
   
6.         if s[i:] == s[i:][::-1]:
   
7.             axis = i
   
8.             break
   
9.         elif s[:-i] == s[:-i][::-1] and s[:i]:
   
10.             axis = -i
    
11.             break
    
12.         i += 1
    
13.     # 哪边短就往哪边加切片
    
14.     out = s+s[:i][::-1] if axis>=0 else s[-i:][::-1]+s
    
15.     return out

复制代码

shigure_takimi

1. def isP(s): # 判断是否回文
   
2.     return s[::-1] == s  
   
3. 
   
4. def makePalindrome(s):
   
5.     if isP(s):  # 如果参数本身回文，返回其本身
   
6.         return s
   
7.     else:
   
8.         p = [] # 存储左看、右看最大回文位置
   
9.         length = len(s)
   
10.         for i in range(length,0,-1): #左看
    
11.             if isP(s[:i]):
    
12.                 p.append(i)
    
13.                 break
    
14.         for i in range(length): # 右看
    
15.             if isP(s[i:]):
    
16.                 p.append(i)
    
17.                 break
    
18.         a = s+s[:p[1]][::-1]
    
19.         b = s[p[0]:][::-1]+s
    
20.     return a if len(a)<=len(b) else b
    
21. 
    
22. # 验证通过

复制代码

jrro452

1. def checkPalindrome(string):
   
2.     if string == string[::-1]:
   
3.         return True
   
4.     return False
   
5. 
   
6. 
   
7. def makePalindrome(string):
   
8.     length = len(string)
   
9.     if length==1:
   
10.         return string
    
11.     else:
    
12.         for i in range(1,length-1):
    
13.             if checkPalindrome(string[i:]):
    
14.                 return string+string[:i][::-1]
    
15.             elif checkPalindrome(string[:-i]):
    
16.                 return string[length-i:][::-1]+string
    
17.             else:
    
18.                 continue
    
19.         return string+string[:length-1][::-1]
    
20. print(makePalindrome('deleveled'))

复制代码

jrro452

jrro452 发表于 2018-10-26 16:44

可以删掉多余的代码列：

1. def checkPalindrome(string):
   
2.     if string == string[::-1]:
   
3.         return True
   
4.     return False
   
5. 
   
6. 
   
7. def makePalindrome(string):
   
8.     length = len(string)
   
9.     for i in range(1,length-1):
   
10.         if checkPalindrome(string[i:]):
    
11.             return string+string[:i][::-1]
    
12.         elif checkPalindrome(string[:-i]):
    
13.             return string[length-i:][::-1]+string
    
14.     return string+string[:length-1][::-1]

复制代码