[已解决]Python：每日一题 292

Unicorn#

zltzlt 发表于 2019-12-20 22:11
就是计算超时，我没有在 IDLE 中测试。

用时0.008770596000005071秒鸭

Unicorn#

zltzlt 发表于 2019-12-20 22:11
就是计算超时，我没有在 IDLE 中测试。

1. if True:
   
2.         a = time.perf_counter()
   
3.         ans = solve('a'*40000)
   
4.         b = time.perf_counter()
   
5.         print(b-a)

复制代码

用时0.008770596000005071秒鸭

阴阳神万物主

在原楼层做了更改，也许还阔以

                               
登录/注册后可看大图

Seawolf

1. def func(s):
   
2.     A=s+"*"+s[::-1]
   
3.     cont=[0]
   
4.     for i in range(1,len(A)):
   
5.         index=cont[i-1]
   
6.         while(index>0 and A[index]!=A[i]):
   
7.             index=cont[index-1]
   
8.         cont.append(index+(1 if A[index]==A[i] else 0))
   
9.     return s[cont[-1]:][::-1]+s

复制代码

hrp

1. def func292(s):
   
2.     if s == s[::-1]:
   
3.         return s
   
4.     n = 1
   
5.     z = len(s)
   
6.     while n <= z:
   
7.         r1 = s + s[:n][::-1]
   
8.         r2 = s[:-(n+1):-1] + s
   
9.         if (r1 != r1[::-1]) and (r2 != r2[::-1]):
   
10.             n += 1
    
11.             continue
    
12.         if r1 == r1[::-1]:
    
13.             return r1
    
14.         else:
    
15.             return r2
    

复制代码

闲愚

1. def func_292(s):
   
2.     result = ''
   
3.     for i in range(len(s)):
   
4.         result += s[i]
   
5.     n = len(s)
   
6.     s1 = ''
   
7.     while n > 1:
   
8.         for i in range(1,n):
   
9.             if n <= 1:
   
10.                 pass
    
11.             else:
    
12.                 if s[i] == s[n - i - 1]:
    
13.                     pass
    
14.                 else:
    
15.                     break
    
16.         else:
    
17.             break
    
18.         s1 += s[n - 1]
    
19.         list1 = []
    
20.         for i in range(n - 1):
    
21.             list1.append(s[i])
    
22.         s = ''
    
23.         for item in list1:
    
24.             s += item
    
25.         n = len(s)
    
26.     result = s1 + result
    
27.     return result
    
28. 
    
29. if __name__ == '__main__':
    
30.     print('自测1：输入：\'aacecaaa\'，输出：',func_292('aacecaaa'))
    
31.     print('自测2：输入：\'abcd\'，输出：',func_292('abcd'))
    
32.     print('自测3：输入：\'\'，输出：',func_292(''))
    
33.     print('自测4：输入：\'abccba\'，输出：',func_292('abccba'))
    

复制代码

Stubborn

1. def fun292(s: str) -> str:
   
2.     """
   
3.     * [KMP字符串匹配算法1](https://www.bilibili.com/video/av11866460)
   
4.     * [KMP字符串匹配算法2](https://www.bilibili.com/video/av16828557)
   
5.     """
   
6.     def get_prefix_table(p):
   
7.         prefix_table = [0] * len(p)
   
8.         i = 1
   
9.         j = 0
   
10.         while i < len(p):
    
11.             if p[i] == p[j]:
    
12.                 j += 1
    
13.                 prefix_table[i] = j
    
14.                 i += 1
    
15.             else:
    
16.                 if j > 0:
    
17.                     j = prefix_table[j - 1]
    
18.                 else:
    
19.                     i += 1
    
20.                     j = 0
    
21.         return prefix_table
    
22. 
    
23.     prefix_table = get_prefix_table(s + "#" + s[::-1])
    
24.     return s[prefix_table[-1]:][::-1] + s

复制代码

Stubborn

KMP字符串匹配算法1
KMP字符串匹配算法2

1. def fun292(s: str) -> str:
   
2.     def get_prefix_table(p):
   
3.         prefix_table = [0] * len(p)
   
4.         i = 1
   
5.         j = 0
   
6.         while i < len(p):
   
7.             if p[i] == p[j]:
   
8.                 j += 1
   
9.                 prefix_table[i] = j
   
10.                 i += 1
    
11.             else:
    
12.                 if j > 0:
    
13.                     j = prefix_table[j - 1]
    
14.                 else:
    
15.                     i += 1
    
16.                     j = 0
    
17.         return prefix_table
    
18. 
    
19.     prefix_table = get_prefix_table(s + "#" + s[::-1])
    
20.     return s[prefix_table[-1]:][::-1] + s

复制代码

Stubborn

1. def fun292(s: str) -> str:
   
2.     def get_prefix_table(p):
   
3.         prefix_table = [0] * len(p)
   
4.         i = 1
   
5.         j = 0
   
6.         while i < len(p):
   
7.             if p[i] == p[j]:
   
8.                 j += 1
   
9.                 prefix_table[i] = j
   
10.                 i += 1
    
11.             else:
    
12.                 if j > 0:
    
13.                     j = prefix_table[j - 1]
    
14.                 else:
    
15.                     i += 1
    
16.                     j = 0
    
17.         return prefix_table
    
18. 
    
19.     prefix_table = get_prefix_table(s + "#" + s[::-1])
    
20.     return s[prefix_table[-1]:][::-1] + s

复制代码

hfwei0

1. def huiwen(s):
   
2.     x=str(s)
   
3.     l=len(x)
   
4.     for n in range(l):
   
5.         tmp=x[(l-n)-1::-1]
   
6.         if tmp==x[:(l-n)] :
   
7.             y=x[(l-1):(l-n-1):-1]+x
   
8.             return y
   
9. 
   
10. print(huiwen('aacecaaa'))
    
11. print(huiwen('abcd'))

复制代码

NAMELESSONE

1. string1=input("请输入您的字符串:")
   
2. string2=''
   
3. string=string1
   
4. while len(string1)!=0:
   
5.     if string1[::-1]==string1:
   
6.         break
   
7.     string2+=string1[-1]
   
8.     string1=string1[:len(string1)-1]
   
9. print(string2+string)

复制代码

findland

1. def f292(s):
   
2.     tmp=s[::-1]
   
3.     if tmp==s:
   
4.         return s
   
5.     else:
   
6.         tmp_i=0
   
7.         for i in range(len(s)):
   
8.             tmp=s[0:i]
   
9.             tmp_r=tmp[::-1]
   
10.             if tmp==tmp_r:
    
11.                 tmp_i=i
    
12.         return (s[-1:tmp_i-1:-1])+s
    
13.         
    

复制代码

1270188436

def solve(s):
def reverse_check(s):
for i in range(len(s)//2):
if s[i] != s[-1-i]:
return False
return True
if reverse_check(s):
return s
else:
for i in range(1, len(s)):
if reverse_check(s[:-i]):
return ''.join(reversed(s[-i:])) + s

jinlovelive

1. s = list(input(':'))
   
2. c = 0
   
3. for i in range(len(s),0,-1):
   
4.     s_temp = s[0:i]
   
5.     s_temp.reverse()
   
6.     if s_temp == s[0:i]:
   
7.         c = i
   
8.         break
   
9. s_rev = s[c:]
   
10. s_rev.reverse()
    
11. comlist = s_rev+s
    
12. print(comlist)
    
13. 
    

复制代码

_2_

Stubborn 发表于 2019-12-21 02:34

哇，连小甲鱼都来了

zltzlt

阴阳神万物主 发表于 2019-12-20 21:21
改了一改，康康这回如何。

这回感觉可以

输入 "" 报错

fan1993423

1. def fun292(s):
   
2.     if not len(s) or s==s[::-1]:
   
3.         return s
   
4.     for i in range(1,len(s)):
   
5.         if s[:-i]==s[:-i][::-1]:
   
6.             hw_s=s[-i:][::-1]+s
   
7.             return hw_s
   
8.     else:
   
9.         for i in range(len(s)):
   
10.             if s[i]!=s[i+1]:
    
11.                 hw_s=s[i+1:][::-1]+s
    
12.                 return hw_s

复制代码

zltzlt

Unicorn# 发表于 2019-12-20 22:24
用时0.008770596000005071秒鸭

建议楼主提高时间复杂度。提示：翻转字符串使用 s[::-1]。

zltzlt

沙里爬 发表于 2019-12-20 21:44

会超时

zltzlt

fengo0 发表于 2019-12-20 22:02
def solve(str1):
    str2 = str1[::-1]
    length = len(str1)

解答错误

输入：""
输出；None
预期结果：""