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

阴阳神万物主

zltzlt 发表于 2020-1-23 21:34
解答错误

输入：

想康康我的解法能不能解对这个，但是单单拷贝就让我的 idle 陷入无响应状态QWQ

zltzlt

阴阳神万物主 发表于 2020-1-23 21:48
想康康我的解法能不能解对这个，但是单单拷贝就让我的 idle 陷入无响应状态QWQ

呵呵用记事本试试

阴阳神万物主

我来康康能否承受住这道题目。

1. def solve(lst:'list of int >= 0',debug=False)->list:
   
2.     if lst:
   
3.         loop = lst[:1]
   
4.         for i in range(len(lst)-1):
   
5.             l = len(loop)
   
6.             if lst[i] != loop[i%l] or lst[i+1] != loop[(i+1)%l]:
   
7.                 loop = lst[:i+1] if lst[i+1] == loop[0] else lst[:i+2]
   
8.                 if debug:
   
9.                     print('调试',loop)
   
10.         return len(loop)
    
11.     else:
    
12.         return 0
    
13. if __name__ == '__main__':
    
14.     print('示例1 输出：',solve([1,2,1,2,1,2]))
    
15.     print('示例2 输出：',solve([1,2,1,2,1]))
    
16.     print('示例3 输出：',solve([1,2,1,2,1,4],debug=1))
    
17.     print('别人错的12#',solve([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 1]))
    
18.     print('别人错的11#',solve([1]))
    
19.     print('别人错的16#',solve([1, 1, 1, 3, 2, 1, 1, 1, 1, 3, 2, 1]))
    

复制代码

zltzlt

阴阳神万物主 发表于 2020-1-23 21:51
我来康康能否承受住这道题目。

解答错误

输入：[1, 1, 1, 3, 2, 1, 1, 1, 1, 3, 2, 1]
输出：11
预期结果：6（循环节为 [1, 1, 1, 3, 2, 1]）

阴阳神万物主

zltzlt 发表于 2020-1-23 21:53
解答错误

输入：[1, 1, 1, 3, 2, 1, 1, 1, 1, 3, 2, 1]

唉~又增加了一个耗时间的环节。

1. def solve(lst:'list of int >= 0',debug=False)->list:
   
2.     if lst:
   
3.         loop = lst[:1]
   
4.         for i in range(len(lst)-1):
   
5.             l = len(loop)
   
6.             if lst[i] != loop[i%l] or lst[i+1] != loop[(i+1)%l]:
   
7.                 if lst[i] == loop[0]:
   
8.                     a = loop[:]
   
9.                     b = lst[l:i+l]
   
10.                     d = (len(b)-len(a))//2
    
11.                     a += b[:d]
    
12.                     b = b[d:]
    
13.                     #print('调试',a,b)
    
14.                     if a == b:
    
15.                         loop = a
    
16.                         continue
    
17.                 loop = lst[:i+1] if lst[i+1] == loop[0] else lst[:i+2]
    
18.                 if debug:
    
19.                     print('调试',loop)
    
20.         return len(loop)
    
21.     else:
    
22.         return 0
    
23. if __name__ == '__main__':
    
24.     print('示例1 输出：',solve([1,2,1,2,1,2]))
    
25.     print('示例2 输出：',solve([1,2,1,2,1]))
    
26.     print('示例3 输出：',solve([1,2,1,2,1,4]))
    
27.     print('别人错的12#',solve([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 1]))
    
28.     print('别人错的11#',solve([1]))
    
29.     print('之前错的23#',solve([1, 1, 1, 3, 2, 1, 1, 1, 1, 3, 2, 1]))
    

复制代码

优化后：

1. def solve(lst:'list of int >= 0',debug=False)->list:
   
2.     if lst:
   
3.         loop = 1
   
4.         for i in range(1,len(lst)-1):
   
5.             if lst[i] != lst[i%loop] or lst[i+1] != lst[(i+1)%loop]:
   
6.                 if lst[i] == lst[0]:
   
7.                     r = loop+i
   
8.                     l = r//2
   
9.                     if lst[:l]==lst[l:r]:
   
10.                         loop = l
    
11.                         continue
    
12.                 loop = i+1 if lst[i+1] == lst[0] else i+2
    
13.                 if debug:
    
14.                     print('调试',loop)
    
15.         return loop
    
16.     else:
    
17.         return 0
    
18. if __name__ == '__main__':
    
19.     print('示例1 输出：',solve([1,2,1,2,1,2]))
    
20.     print('示例2 输出：',solve([1,2,1,2,1]))
    
21.     print('示例3 输出：',solve([1,2,1,2,1,4]))
    
22.     print('别人错的12#',solve([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 1]))
    
23.     print('别人错的11#',solve([1]))
    
24.     print('之前错的23#',solve([1, 1, 1, 3, 2, 1, 1, 1, 1, 3, 2, 1]))

复制代码

zltzlt

阴阳神万物主 发表于 2020-1-23 22:15
唉~又增加了一个耗时间的环节。

优化后：

通过了

阴阳神万物主

zltzlt 发表于 2020-1-23 22:22
通过了

欧耶！(手舞足蹈状)

Jetty

1. def array_diff(arr1, arr2):
   
2.     for i in range(len(arr2)):
   
3.         if arr1[i] != arr2[i]:
   
4.             return False
   
5.     return True
   
6. 
   
7. def arr_proc(lst):
   
8.     if len(lst) < 2: return lst
   
9.     find_index = lst.index(lst[0], len(set(lst)))
   
10.     loop_arr = []
    
11.    
    
12.     is_loop = True
    
13.     while len(loop_arr) < len(lst) and is_loop:
    
14.         if lst[0] in lst[find_index:]:
    
15.             loop_arr = lst[:lst.index(lst[0], find_index)]
    
16.         else:
    
17.             loop_arr = lst
    
18.         arr_len = len(loop_arr)
    
19.         for i in range(arr_len, len(lst)):
    
20.             tmp_arr = lst[i:i+arr_len]
    
21.             if not array_diff(loop_arr, tmp_arr):
    
22.                 find_index += 1
    
23.                 break
    
24.             
    
25.             if i + len(tmp_arr) == len(lst):
    
26.                 is_loop = False
    
27.         
    
28.     return loop_arr
    
29.    
    
30. print arr_proc([1,1,1,3,2,1,1,1,1,3,2,1])
    

复制代码

新手挑战一下。。。

zltzlt

Jetty 发表于 2020-1-23 23:14
新手挑战一下。。。

解答错误

输入：[1,2,1,2,1,2]
输出：[1,2,1,2]
预期结果：2

TJBEST

事情真多，晚上再发吧

Croper

阴阳神万物主 发表于 2020-1-23 22:15
唉~又增加了一个耗时间的环节。

优化后：

讲道理，这个解法不对吧，不用kmp我是没看出有什么好方法的

试试用例[1,2,1,2,3,1,2,1,2,1]，预期结果应该是7，循环节[1,2,1,2,3,1,2]。

Stubborn

1. def func303(arr):
   
2.     k = [arr[0],]
   
3.     ki = 0
   
4.    
   
5.     idx = 0
   
6.     while True:
   
7.         for i in k:
   
8.             if idx >= len(arr):
   
9.                 return len(k)
   
10.             if arr[idx] == i:
    
11.                 idx += 1
    
12.             else:
    
13.                 if ki:
    
14.                     k = k * ki
    
15.                     k.append(arr[len(k)])
    
16.                     idx = len(k)
    
17.                     ki = 0
    
18.                     break
    
19.                 else:
    
20.                     k.append(arr[len(k)])
    
21.                     idx += 1
    
22.                     break
    
23.         ki += 1

复制代码

TJBEST

可能速度有些慢，楼主写的那个4003周期的东西 我速度2s左右 不过数对了也是不错的

1. def fun313(arr):
   
2.     def check():
   
3.         M = len(checkList)
   
4.         state = True
   
5.         div = N//M
   
6.         res = N%M
   
7.         for i in range(0,div):
   
8.             if arr[(i*M):((i+1)*M)]!= checkList:
   
9.                 state = False
   
10.                 break
    
11.         
    
12.         if state == False:
    
13.             return False
    
14.         else:
    
15.             if res == 0 or arr[(N-res):N]== checkList[0:res]:
    
16.                 return True
    
17.             else:
    
18.                 return False
    
19.         
    
20.     N = len(arr)
    
21.     if N < 2:
    
22.         return N
    
23.     checkList = [arr[0]]
    
24.    
    
25.     state = True
    
26.     for each in  arr:
    
27.         if each!= arr[0]:
    
28.             state = False
    
29.             break
    
30.     if state == True:
    
31.         return 1
    
32.    
    
33.     for each in arr[1:]:
    
34.         if each == arr[0]:
    
35.             checkList.append(each)
    
36.         else:
    
37.             break
    
38.    
    
39.     M = len(checkList)
    
40.     for each in arr[M:]:
    
41.         if each != arr[0]:
    
42.             checkList.append(each)
    
43.         else:
    
44.             if check():
    
45.                 break
    
46.             else:
    
47.                 checkList.append(each)
    
48.     return len(checkList)

复制代码

TJBEST

Croper 发表于 2020-1-24 16:43
结果:

你是正确的，我算的也是7

TJBEST

楼主有时间测测我这个吧

zltzlt

TJBEST 发表于 2020-1-24 22:36
楼主有时间测测我这个吧

抱歉，现在测不了，得等到明天

阴阳神万物主

Croper 发表于 2020-1-24 16:40
讲道理，这个解法不对吧，不用kmp我是没看出有什么好方法的

试试用例[1,2,1,2,3,1,2,1,2,1]，预期结果 ...

你是对的，但是好像测试数据里面没有这种的。

zltzlt

Croper 发表于 2020-1-24 16:43
结果:

输入 [1] 会报错，帮你改了，最终用时 254 ms

zltzlt

Stubborn 发表于 2020-1-24 17:09

输入大数据超时

zltzlt

TJBEST 发表于 2020-1-24 17:37
可能速度有些慢，楼主写的那个4003周期的东西 我速度2s左右 不过数对了也是不错的

确实有点慢，不过勉强通过了，用时 3431 ms