1 from locale import atoi
2
3 from keras.preprocessing import sequence
4 from pandas import Series
5
6 ##！！！！！注意^是异或而不是平方！！！！x**2才是平方
7 def list_basic():
8 A0 = dict(zip(('a', 'b', 'c', 'd', 'e'), (1, 2, 3, 4, 5)))
9 # A1 = range(10)#输出 range(0, 10)
10 # A2 = [i for i in A1 if i in A0]#在第一个循环中可以依次从0到9的循环，但if i in A0中的i只能获取key值而不是键值
11 A3 = [A0[s] for s in A0] # 得到的结果没有顺序，因为字典构建的时候就是乱序的
12 # A4 = [i for i in A1 if i in A3]
13 # A5 = {i: i * i for i in A1} # 构建字典
14 # A6 = [[i, i * i] for i in A1]#得到嵌套的列表
15 print(A0)
16 # print(A1)
17 print(A3)
18 for s in A0:
19 print(A0[s])
20 # print(A4)
21 # print(A5)
22 # print(A6)
23 def zhengshu_num_1(n):
24 if n==1:
25 return 1
26 else:
27 num_1 = 0
28 for num in range(1, n+1):
29 print(num)
30 for k in range(len(str(n))):
31 if (num - pow(10, k)) % pow(10, k + 1) < pow(10, k):
32 num_1 += 1
33 return num_1
34 # print(zhengshu_num_1(10))
35 #判断丑数
36 def GetUglyNumber_Solution(index):
37 # write code here
38 if index==1:
39 return 1
40 res=[1]#先把默认的1放入丑叔数组
41 x=y=z=0
42 ind=1
43 while ind<index:
44 minnum=min(2*res[x],3*res[y],5*res[z])
45 res.append(minnum)
46 if minnum>=2*res[x]:
47 x+=1
48 if minnum>=3*res[y]:
49 y+=1
50 if minnum>=5*res[z]:
51 z+=1
52 ind=ind+1
53 return res[index-1]
54 # print(GetUglyNumber_Solution(3))
55 # -*- coding:utf-8 -*-
56 #求1+2+3+....+n 但是这个递归会超时
57 def Sum_Solution(n):
58 # write code here
59 ans=n#由于要控制结束是到n所以从n递减
60 temp=ans and Sum_Solution(n-1)#这个函数是为了控制递减到0的时候结束递归,由于短路性质，当ans递减到0时，不再进入后面的判断，结束递归
61 ans=ans+temp#求和 第一次求和时temp与ans均为0，然后递归上一个ans=1,此时的Sum_Solution()为0，求和。。。。依次递归求和
62 # print(temp)
63 return ans
64 #下面这种方法貌似答案不对？
65 def Sum_Solution_2(n):
66 try:
67 i=1%n
68 return n+Sum_Solution_2(n-1)
69 except:
70 return 0
71 # m=Sum_Solution_2(10000)
72 def Sum_Solution_3(n):
73 return (pow(n,2)+n)>>1
74
75 # print(Sum_Solution_3(50000))
76
77 # print(Sum_Solution(5))
78 # def GetNumberOfK_first(data, k):
79 # # write code here
80 # first = 0
81 # end = len(data) - 1
82 # mid = int((first + end) / 2)
83 # while first <= end:
84 # print('2',end - first)
85 # if data[mid] < k:
86 # first = mid + 1
87 # elif data[mid] > k:
88 # end = mid - 1
89 # else:
90 # if data[mid] == k and (mid == 0 or data[mid-1] != k):
91 # return mid
92 # else:
93 # end = mid - 1 # 注意这里是对end进行更新，也就是在左边查找
94 # mid = int((first + end) / 2)
95 # def GetNumberOfK_end(data, k):
96 # first = 0
97 # end = len(data) - 1
98 # mid = int((first + end) / 2)
99 # while first <= end:
100 # print(end-first)
101 # if data[mid] < k:
102 # first = mid + 1
103 # elif data[mid] > k:
104 # end = mid - 1
105 # else:
106 # if data[mid] == k and (mid == end or data[mid+1] != k):
107 # return mid
108 # else:
109 # end = mid + 1 # 注意这里是对end进行更新，也就是在右边查找
110 # mid = int((first + end) / 2)
111 # def getnum(data, k):
112 # return GetNumberOfK_end(data, k) - GetNumberOfK_first(data, k) + 1
113 # print(getnum([1,2,2,3],2))
114 #二分查找实现
115 #递归
116 # l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
117
118 def find(l,aim,start = 0,end = None):
119 end = len(l) if end is None else end
120 mid_index = (end - start) // 2 + start
121 if start <= end:
122 if l[mid_index] < aim:
123 return find(l,aim,start = mid_index+1,end=end)
124 elif l[mid_index] > aim:
125 return find(l,aim,start=start,end=mid_index-1)
126 else:
127 return print('找到了，index为：%s'%mid_index,)
128 else:
129 return '找不到这个值...'
130 # ret = find(l,44)
131 # print(ret)
132 #循环实现
133 def find_2(l,aim,start = 0,end = None):
134 while start<=end:
135 mid=start+(start+end)//2
136 if l[mid]==aim:
137 return '找到了'
138 elif l[mid]<aim:
139 mid=mid+1
140 else:
141 mid=mid-1
142 return '没有这样的数字'
143
144
145
146 class Solution:
147 def GetNumberOfK(self, data, k):
148 # write code here
149 if not data or not k:
150 return 0
151
152 frist = self.getFrist(data, k)
153 last = self.getLast(data, k)
154
155 if frist > -1 and last > -1:
156 return last - frist + 1
157 return 0
158 # 二分查找数组中k的第一位
159
160 def getFrist(self, data, k):
161 begin = 0
162 end = len(data) - 1
163 mid = int((begin + end) / 2)
164 while begin <= end:
165 if data[mid] < k:
166 begin = mid + 1
167 elif data[mid] > k:
168 end = mid - 1
169 else:
170 if mid <= begin or data[mid - 1] != k:
171 return mid
172 else:
173 end = mid - 1
174 mid = int((begin + end) / 2)
175 return -1
176
177 # 二分查找数组中k的最后一位
178 def getLast(self, data, k):
179 begin = 0
180 end = len(data) - 1
181 mid = int((begin + end) / 2)
182 while begin <= end:
183 if data[mid] < k:
184 begin = mid + 1
185 elif data[mid] > k:
186 end = mid - 1
187 else:
188 if mid >= end or data[mid + 1] != k:
189 return mid
190 else:
191 begin = mid + 1
192 mid = int((begin + end) / 2)
193 return -1
194 import numpy as np
195 # n=[[0.0013703592121601105, -0.0016458103200420737]]
196 # m=[]
197 #
198 # text_vec=sequence.pad_sequences(np.array(n).transpose(), maxlen=5,padding='post',dtype='float32')
199 #
200 # m.append(text_vec.transpose())
201 # print(m)
202 # print(len(m[0]),len(m[0][0]))
203 # mm=np.array(m)
204 # print(mm)
205 #堆排序
206 class Sort_dui:
207 def __init__(self):
208 pass
209 def GetLeastNumbers_Solution(self,tinput,k):
210 size=len(tinput)
211 if size==0 or k>size:
212 return []
213 array=self.sort(tinput,size)
214 return array[:k]
215 def sort(self,array,size):
216 for i in range(int(size/2-1),-1,-1):
217 array1=self.adjust(array,i,size-1)#所有非叶子节点与最后一个节点进行调整
218 for j in range(size-1,-1,-1):
219 temp=array1[j]
220 array[j]=array1[0]
221 array1[0]=temp
222 array1=self.adjust(array1,0,j-1)#第一个元素与仍需调整的最后节点进行调整
223 return array1
224 def adjust(self,array,start,end):
225 temp=array[start]
226 i=start*2+1#左孩子
227 while i<=end:
228 if i+1<=end and array[i+1]>array[i]:
229 i=i+1
230 if array[i]<temp:
231 break
232 array[start]=array[i]
233 start=i
234 i=start*2+1
235 array[start]=temp
236 return array
237 class Solution1:
238 def GetLeastNumbers_Solution(self, tinput, k):
239 # write code here
240 size=len(tinput)
241 if size==0 or k>size:#注意k是个数，不是第k个，所以是or k>size-1
242 return []
243 array=self.sort(tinput,size)
244 return array[:k]
245 def sort(self,array,size):
246 #首先构建为大顶堆
247 for i in range(int(size/2)-1,-1,-1):#从下到上第一个非叶子节点到根节点，range取不到最后边的元素所以是-1
248 self.adjust(array,i,size-1)
249 #从最后一个节点开始排序，没排一个节点，都要调整一次堆。
250 for j in range(size-1,-1,-1):
251 temp=array[j]
252 array[j]=array[0]
253 array[0]=temp
254 array=self.adjust(array,0,j-1)#每次元素个数减1.由于此次交换只是根节点不符合大顶堆要求，所以只需要调整该节点对应的堆顺序
255 return array
256 def adjust(self,array,start,end):
257 temp=array[start]
258 i=start*2+1
259 while i<=end:
260 if i+1<=end and array[i+1]>array[i]:#小顶堆改array[i+1]<array[i]
261 i+=1
262 if array[i]<temp:##小顶堆改array[i]>temp
263 break
264 array[start]=array[i]#这步不要落下！！！！！
265 start=i#往下面一层非叶节点进行判断
266 i=start*2+1
267 array[start]=temp
268 #所有层级找完后将要判断的temp与目前最大值交换！！！！！！！！！！！这步要注意，temp记录了此次循环的非叶节点的值，array[start]为目前被最大值覆盖了的节点（即本轮最大值对应的节点的ID）
269 return array
270 # s=Solution1()
271 # # arr=s.GetLeastNumbers_Solution([50, 16, 30, 10, 60, 90, 2, 80, 70],8)
272 # arr=s.GetLeastNumbers_Solution([4,6,8,5,9],5)
273 # print(arr)
274 ##############堆排序-小顶堆(得到的结果是降序排列的数组) 不需要建树，输入的数组为完全二叉树
275 def msort():
276 array=[4,6,8,5,9]
277 size=len(array)
278 array_sort=sort(array,size)
279 print(array_sort)
280 def sort(array,size):
281 for i in range(int(size/2)-1,-1,-1):#注意int(size/2)-1一定要减1！！！！！！
282 adjust(array,i,size-1)
283 for j in range(size-1,-1,-1):
284 tem=array[0]
285 array[0]=array[j]
286 array[j]=tem
287 adjust(array,0,j-1)
288 print(array)
289 return array
290 def adjust(array,start,end):
291 temp=array[start]
292 i=start*2+1
293 while i<=end:
294 if i+1<=end and array[i+1]<array[i]:#注意这个条件！！
295 i+=1
296 if array[i]>temp:#注意这个条件！！！小顶堆
297 break
298 array[start]=array[i]#注意这里把i的值赋给start！！！
299 start=i
300 i=start*2+1
301 array[start]=temp
302 # msort()
303 #通过堆排序实现输出数组中最小的k的数字
304 def msort1(k):
305 array=[4,6,8,5,9]
306 size=len(array)
307 array_sort=sort1(array,size,k)
308 print(array_sort)
309 def sort1(array,size,k):
310 for i in range(int(size/2)-1,-1,-1):#注意int(size/2)-1一定要减1
311 adjust1(array,i,size-1)
312 for j in range(size-1,size-k-1,-1):#依次从最后一个节点找到最大值然后交换.如果只循环k次得到前最小的k个值？（但是是返回数组中后k个数值）
313 tem=array[0]
314 array[0]=array[j]
315 array[j]=tem
316 adjust1(array,0,j-1)
317 return array
318 def adjust1(array,start,end):
319 temp=array[start]
320 i=start*2+1
321 while i<=end:
322 if i+1<=end and array[i+1]<array[i]:
323 i+=1
324 if array[i]>temp:
325 break
326 array[start]=array[i]
327 start=i
328 i=start*2+1
329 array[start]=temp
330 # msort1(2)
331 #选择排序
332 def xuanze_sort(s):
333 for fillslot in range(len(s)-1,0,-1):#列表的最后一个元素存储最大值，依次向前存储较小值
334 pos_max=0#最大值所在的位置
335 for location in range(1,fillslot+1):#从第2个元素开始到最后一个未排序的元素依次比较，大小，存储最大值对应的位置
336 if s[location]>s[pos_max]:
337 pos_max=location
338 s[fillslot],s[pos_max]=s[pos_max],s[fillslot]#交换两个元素位置，fillslot为此次得到的最大值的位置
339 return s
340 # s=[50, 16, 30, 10, 60, 90, 2, 80, 70]
341 # sort_s=xuanze_sort(s)
342 # print(sort_s)
343 #请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
344 # 例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。
345 # 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
346 def isNumeric( s):
347 # write code here
348 length = len(s)
349 # 需要判断的三种符号
350 hase = False
351 hasdot = False
352 hassigh = False
353 if length <= 0:
354 return False
355 else:
356 for i in range(length): # 对每个元素依次判断
357 if s[i] == 'e' or s[i] == 'E':
358 if hase: # 若已经有了e或E则false
359 return False
360 else: # 若之前没有，则记录为True
361 hase = True
362 if i == length - 1: # e的位置不能是最后一个
363 return False
364 elif s[i] == '.':
365 if hasdot or hase:
366 return False
367 else:
368 hasdot = True # 不能用==，之前用错了！！！！
369 if hase: # 若已经有了e,后面不能有.
370 return False
371 elif s[i] == '+' or s[i] == '-': # +-可以出现在e后面,或者第一个位置
372 if hassigh: # 注意！！！！！！！这个地方，判断条件是如果之前出现过+-
373 if s[i - 1] != 'e' and s[i - 1] != 'E':
374 return False
375 else: # 没有e的话，+-只能出现在开头 注意！！这里判断的不是是否有e而是之前是否有符号位出现过
376 hassigh = True
377 if i != 0 and s[i - 1] != 'e' and s[i - 1] != 'E': # 若+-不在第一个位置或者不在e后面
378 return False
379 elif s[i] < '0' or s[i] > '9':
380 return False
381 # 不能在循环中返回，否则在判断第一个元素后就会返回，不再继续比较
382 # else:
383 # return True
384 return True
385
386 #归并排序（归并排序与快排的代码很像，第一个函数递归调用本函数（都有一个判断条件if）以及直接调用另一个函数，第二个函数解决主要问题）
387
388 def merge_sort(arr,temp,s,end):
389 temp=[None for i in range(len(arr))]#在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
390 if s<end:
391 mid=int((s+end)/2)
392 merge_sort(arr,temp,s,mid)#左边归并排序，使得左子序列有序
393 merge_sort(arr,temp,mid+1,end)#右边归并排序，使得右子序列有序
394 merge1(arr,temp,s,mid,end)#将两个有序子数组合并操作
395 # print(arr)
396 return arr#因为是对数组本身进行操作的，所以不需要返回arr，每次递归的时候都是在他本身进行的操作，最后需要返回是便于输出排序好后的数组内容
397
398 def merge1(arr,temp,s,m,end):#合并操作每轮重新对temp赋值
399 i=s#左序列指针
400 j=m+1#右序列指针
401 t=0#临时数组指针
402 while(i<=m and j<=end):
403 if arr[i]<=arr[j]:#顺序 前半段对应数字更小，则赋值到temp
404 temp[t]=arr[i]
405 i+=1
406 else:#逆序 后半段对应数字更小，则赋值到temp j+1比较后半段下一个元素与前半段对应的i元素
407 temp[t]=arr[j]
408 j+=1
409 t += 1
410 while(i<=m):#将左边剩余元素填充进temp中
411 temp[t]=arr[i]
412 t+=1
413 i+=1
414 while(j<=end):#将右序列剩余元素填充进temp中
415 temp[t]=arr[j]
416 t+=1
417 j+=1
418 #下面很重要，需要把排序过的重新赋值给arr
419 t=0
420 while(s<=end):#s到end
421 arr[s]=temp[t]
422 s+=1
423 t+=1
424 # arr=[8,4,5,7,1,3,6,2]
425 # print(merge_sort(arr, arr, 0, len(arr)-1))
426
427
428 # print(arr)
429 #得到数组中的逆序对数
430 def InversePairs(data,length):
431 if data==None or length<0:
432 return 0
433 #copy内初始化为data（上面的归并排序初始化为None）
434 copy=[]
435 for i in range(length):
436 copy.append(data[i])
437 count=InversePairsCore(data,copy,0,length-1)
438 return count
439 def InversePairsCore(data,copy,start,end):
440 if start==end:
441 copy[start]=data[start]
442 return 0#将数组划分为只有一个元素时，逆序对为0 并且copy内容为该start对应的元素
443 length=int((end-start)/2)#start+end
444 # 递归传入实参需要把copy（已经排序好）传入，data当作辅助数组 所以先copy后data
445 #下面的start+length都可以换为length
446 left=InversePairsCore(copy,data,start,start+length)#！！注意这里copy与data要互换位置
447 right=InversePairsCore(copy,data,start+length+1,end)
448 #与我上面的归并排序有区别，上面是从头开始放元素，下面是从最后一个元素开始放置
449 i=start+length#指向前半段的最后一个元素
450 j=end#指向后半段的最后一个元素
451 indexCopy=end#辅助空间指针指向最后一个位置
452 count=0
453 while i>=start and j>=(start+length+1):#由于i，j指向的是最后位置
454 if data[i]>data[j]:
455 copy[indexCopy]=data[i]
456 count+=j-start-length
457 indexCopy-=1
458 i-=1
459 else:
460 copy[indexCopy]=data[j]
461 j-=1
462 indexCopy-=1
463 while i>=start:
464 copy[indexCopy]=data[i]
465 indexCopy-=1
466 i-=1
467 while j>=start+length+1:
468 copy[indexCopy]=data[j]
469 indexCopy-=1
470 j-=1
471 return left+right+count#返回的值注意；另外，没有像我上面的为辅助空间重新赋值的操作（因为copy和data在递归的时候交换了位置）
472 # l=[364,637,341,406,747,995,234,971,571,219,993,407,416,366,315,301,601,650,418,355,460,505,360,965,516,648,727,667,465,849,455,181,486,149,588,233,144,174,557,67,746,550,474,162,268,142,463,221,882,576,604,739,288,569,256,936,275,401,497,82,935,983,583,523,697,478,147,795,380,973,958,115,773,870,259,655,446,863,735,784,3,671,433,630,425,930,64,266,235,187,284,665,874,80,45,848,38,811,267,575]
473 # print(InversePairs(l,len(l)))
474 #插入排序
475 def insert_sort(lis):
476 length=len(lis)
477 for i in range(1,length):
478 if lis[i]<lis[i-1]:
479 temp=lis[i]
480 j=i-1
481 while j>=0 and lis[j]>temp:
482 lis[j+1]=lis[j]
483 j-=1
484 lis[j+1]=temp
485
486 #希尔排序
487 def shell_sort(lis):
488 length=len(lis)
489 increment=length
490 while increment>1:
491 increment=int((increment/3))+1#依次对increment做处理
492 for i in range(increment+1,length):
493 if lis[i]<lis[i-increment]:
494 temp=lis[i]
495 j=i-increment
496 while lis[j]>temp and j>=0:
497 lis[j+increment]=lis[j]
498 j=j-increment
499 lis[j+increment]=temp
500 return lis
501 ######################快速排序
502 def swap(a,b):
503 temp=a
504 a=b
505 b=temp
506 return a,b
507
508 def qs():
509 lis=[23,46,0,8,11,18]
510 quik_sort(lis,0,len(lis)-1)#调用排序函数
511 print(lis)
512 def quik_sort(lis,low,high):
513 #每轮内部比较时，初始指针low<最后一个指针high
514 if (low<high):#注意这里是if，不是循环 无等号！！！
515 key=partion(lis,low,high)
516 quik_sort(lis,low,key-1)#key-1结束
517 quik_sort(lis,key+1,high)#key+1开始
518
519 def partion(lis,low,high):#每轮partion得到lis[low]的最终位置，即可直接得到他是将来排序后的第几个元素
520 key_word=lis[low]
521 # print(low,high)
522 while(low<high):#无等号！！！！
523 #注意下面是while循环且与key_word判断大小时，要有等于号！！！
524 while low<high and lis[high]>=key_word:#一直判断右边的值是否比key值大，若大则直接往左继续判断
525 high-=1
526 # swap(lis[high],lis[low])#遇到右边的比key小，交换两次交换 的代码一致
527 # （若调用函数因为不是在原位置上改的，所以不可行）
528 temp1=lis[high]
529 lis[high]=lis[low]
530 lis[low]=temp1
531 while low<high and lis[low]<=key_word:
532 low+=1
533 # swap(lis[low],lis[high])#两次交换 的代码一致
534 temp2 = lis[high]
535 lis[high] = lis[low]
536 lis[low] = temp2
537 print(lis)
538 return low#返回的是low
539 # qs()
540 ###############桶排序(用于对【0.1】的小数排序)时间复杂度O(N)
541 def bucket_sort(old):
542 tmp = []
543 #设置要排序的数组的元素个数，作为桶的个数
544 for i in range(len(old)):
545 tmp.append([])#每个桶用列表表示
546 #对每个元素，桶序号为int(i * len(old))的桶内放入i元素，进过乘法放入到桶内的肯定是越小的放在桶的序号越小的
547 for i in old:
548 tmp[int(i * len(old))].append(i)
549 #对每个桶内的元素排序
550 for i in range(len(old)):
551 # tmp[i].sort()
552 shell_sort(tmp[i])#该桶内为从小到大排好序的列表
553 #分别输出各桶元素
554 for i in range(len(old)):
555 if (len(tmp[i]) > 0):
556 print(tmp[i])
557 ###############桶排序(用于对整数排序)时间复杂度O(N) https://blog.csdn.net/weixin_39859512/article/details/84833582
558 def bucket_sort2(old):
559 maxnum=max(old)
560 f=[0]*(maxnum+1)
561 for i in old:
562 f[i]+=1
563 for j in range(maxnum+1):
564 if f[j]!=0:
565 for p in range(f[j]):
566 print(j)
567 # bucket_sort2([6,3,9,2,1,4,3,2,1,9,8,7,6])
568
569 # # test case
570 # old = [0.3333333333333333, 0.8333333333333334, 0.5, 0.0, 0.333333336, 0.5, 0.0, 0.6]
571 # bucket_sort(old)
572 # insert_sort(old)
573 ###############基数排序
574 import random
575 def radixSort(arr):
576 i=0
577 max_num=max(arr)#数组中最大值
578 max_len=len(str(max_num))#最大值的位数
579 while i<max_len:#循环最大数字的位数，从最低位到最高位
580 temp=[[] for k in range(10)]#建10个桶
581 for a in arr:
582 temp[int(a/(10**i))%10].append(a)#把数a放到个位数对应的桶中
583 #########此时相当于按桶的顺序对数据已经做了一次排序
584 arr.clear()#将arr清空
585 #按桶的从前到后依次将桶内的数据放入原数组中
586 for a in temp:#循环每个桶
587 if len(a)!=0:#若桶不空
588 for t in a:#循环桶内的每个元素
589 arr.append(t)#得到第一轮排序后的数组，通过while循环继续下一轮的排序
590 i+=1
591 return arr
592 # A=[64,8,216,512,27,729,0,1,343,125]
593 # arr=radixSort(A)
594 # print(arr)
595 #从文本中搜索并打印内容，要求支持通配符星号和问号
596 def find_string(str,pat):
597 import re
598 return re.findall(pat,str,re.I)#re.I忽略大小写 为str匹配pat中的字符
599 # print(find_string('abc','A'))
600 #删除list中重复元素
601 def deletedup():
602 a=[1,2,4,2,4,5,6,5,7,8,9,0]
603 b={}
604 b=b.fromkeys(a)#dict.fromkeys(seq[, value]) seq为要作为字典键值的列表，value是初始值默认None
605 print(b)#{0: None, 1: None, 2: None, 4: None, 5: None, 6: None, 7: None, 8: None, 9: None}
606 li=b.keys()
607 print(li)#dict_keys([0, 1, 2, 4, 5, 6, 7, 8, 9])
608 # deletedup()
609 def getscore():#得到多类别标签的各评估标准值
610 from sklearn.metrics import precision_recall_fscore_support
611
612 predicted=[1,2,3,4,5,1,2,1,1,4,5]
613 y_test=[1,2,3,4,5,1,2,1,1,4,1]
614 precision,recall,fscore,support=precision_recall_fscore_support(y_test,predicted)
615 print(precision,recall,fscore,support)
616
617 #正则表达式匹配
618 def match(s, pattern):
619 # write code here
620 if len(s) == 0 and len(pattern) == 0:
621 return True
622 if len(s) != 0 and len(pattern) == 0:
623 return False
624 if len(s) == 0 and len(pattern) != 0:
625 # 注意模式中*不可能在第一个位置，*前面必须有字符
626 if len(pattern) > 1 and pattern[1] == '*': # 首先pattern长度要大于1，且第二个位置为*
627 return match(s, pattern[2:]) # 从第三个元素开始递归
628 else:
629 return False # 不满足a*a*a*这种格式的直接返回false
630 else: # s与pattern都不为空
631 # if s[0]!=pattern[0] and pattern[1]!='*':#若当前位置两者未能匹配，且下一个元素不是*，直接返回false
632 # return False
633 # if s[0]!=pattern[0] and pattern[1]=='*':
634 # return self.match(s,pattern[2:])
635 # if s[0]==pattern[0] and pattern[1]!='*':
636 # return self.match(s[1:],pattern[1:])
637 # if s[0]==pattern[0] and pattern[1]=='*':
638 # return self.match(s[1:],pattern[2:]) or self.match(s,pattern[2:]) or self.match(s[1:],pattern)
639 if len(pattern) > 1 and pattern[1] == '*':
640 if s[0] != pattern[0] and pattern[0] != '.': # 没匹配上，则pattern后移两位
641 return match(s, pattern[2:])
642 else:
643 return match(s[1:], pattern[2:]) or match(s, pattern[2:]) or match(s[1:], pattern)
644
645 else:
646 if s[0] == pattern[0] or pattern[0] == '.':
647 return match(s[1:], pattern[1:])
648 else:
649 return False
650 def ReverseSentence(s):
651 # write code here
652 if s==" ":
653 return " "
654 string=s.split()
655 for i in range(int(len(string)/2)):
656 temp=string[i]
657 string[i]=string[len(string)-1-i]
658 string[len(string)-1-i]=temp
659 return ' '.join(string)
660
661
662 def LeftRotateString(s, n):
663 # write code here
664 s1 = reverse(s[:n], 0, n - 1)
665 s2 = reverse(s[n:], 0, len(s) - 1 - n)
666 return reverse((s1 + s2), 0, len(s) - 1)
667 def reverse( s, left, right):
668 print(s)
669 while left < right:
670 temp = s[left]
671 print(temp)
672 print(s[right])
673 s[left] = s[right]#'str' object does not support item assignment
674 s[right] = temp
675 left += 1
676 right -= 1
677 return s
678
679 #找到数组中出现一次的数字
680 def FindNumsAppearOnce(array):
681 num = 0 # 注意与0异或还是原数
682 for i in array: # 所有数字依次做异或操作
683 num = i^num
684 print(num)
685 bit = 0
686 while ((num & 1) == 0): # 从低位到高位找到第bit位为1（找到一个即可）
687 print(num & 1)
688 num=num >> 1
689 bit += 1
690 # print(bit)
691 a = b = 0
692 for i in array: # 将array按照第bit位是否为1划分为两个数组，分别依次求异或
693 if bitpos(i, bit): # 若右移bit位&1=1分为1组
694 a = a ^ i
695 else: # 若右移bit位&1！=1分为2组
696 b = b ^ i
697 return a, b
698
699
700 def bitpos(num, bit):
701 return ((num >> bit) & 1)
702 # print(FindNumsAppearOnce([2,4,3,6,3,2,5,5]))
703 #二叉树深度
704 class TreeNode:
705 def __init__(self, x):
706 self.val = x
707 self.left = None
708 self.right = None
709 #后序遍历树的节点，只要有一个节点的左右子树深度差大于1则返回false
710 def IsBalanced_Solution(p):
711 return dfs(p)!=-1
712 def dfs(p):
713 if p is None:
714 return 0
715 left=dfs(p.left)
716 if left==-1:
717 return -1
718 right=dfs(p.right)
719 if right==-1:
720 return -1
721 #######上面的操作会递归到最后一个节点，即先算最后一个节点的左右子树深度，
722 #然后依次向上递归
723 if abs(left-right)>1:
724 return -1
725 return max(left,right)+1
726 #从上到下依次判断每个节点的深度，会导致每个节点的深度计算多次
727 def depth_get(p):
728 if p==None:
729 return 0
730 nleft=depth_get(p.left)
731 nright=depth_get(p.right)
732 if nleft>nright:
733 return nleft+1
734 elif nleft<=nright:
735 return nright+1
736 def isbalance(p):
737 if p==None:
738 return True
739 mleft=depth_get(p.left)
740 mright=depth_get(p.right)
741 if abs(mleft-mright)>1:
742 return False
743 return isbalance(p.left) and isbalance(p.right)
744
745 #查找数组中k出现的次数
746 def GetNumberOfK(data, k):
747 # write code here
748
749 return endk(data, k, 0, len(data) - 1) - firstk(data, k, 0, len(data) - 1) + 1
750
751 def firstk(data, k, first, end):
752 if first > end:
753 return -1
754 mid = int((first + end) / 2)
755 middata = data[mid]
756 if middata == k:
757 if (mid > 0 and data[mid - 1] != k) or mid == 0: # 若mid在大于0的时候对应的前一个位置的值不是k,或者此时mid=0
758 return mid # 找到第一个位置的k
759 else:
760 end = mid - 1
761 elif middata < k:
762 first = mid + 1
763 elif middata > k:
764 end = mid - 1
765 return firstk(data, k, first, end)
766
767 def endk(self, data, k, first, end):
768 if first > end:
769 return -1
770 mid = int((first + end) / 2)
771 middata = data[mid]
772 if middata == k:
773 if (mid + 1 < (len(data)) and data[mid + 1] != k) or mid == (len(data) - 1):
774 return mid # 找到第一个位置的k
775 else:
776 first = mid + 1
777 elif middata < k:
778 first = mid + 1
779 elif middata > k:
780 end = mid - 1
781 return firstk(data, k, first, end)
782
783 #得到旋转数组中最小的数字
784 def minNumberInRotateArray(rotateArray):
785 # write code here
786 if len(rotateArray) == 0:
787 return 0
788 else:
789 ind1 = 0
790 ind2 = len(rotateArray) - 1
791 mid = 0
792 while (rotateArray[ind1] > rotateArray[ind2]):
793 mid = int((ind1 + ind2) / 2)
794 if ind2 - ind1 == 1:
795 # mid = ind2
796 # break
797 return rotateArray[ind2]
798 if rotateArray[mid] >= rotateArray[ind1]:
799 ind1 = mid
800 if rotateArray[mid] <= rotateArray[ind2]:
801 ind2 = mid
802 # return rotateArray[mid]
803
804 #跳台阶
805 def jumpFloorII(number):
806 # write code here
807 if number == 1:
808 return 1
809 else:
810 n = 1
811 for i in range(number):
812 n = n * 2
813 return n
814 #输出该链表中倒数第k个结点
815 def FindKthToTail(head, k):
816 # write code here
817 # 方法一：先遍历一遍得到链表长度，再遍历到第n-k+1个节点即为倒数第k个节点
818 # 方法二：设置两个指针，一个先走k-1步，然后另一个指针开始走，两个始终相差k-1,直到前面的指针走到
819 # 最后一个节点输出后面指针指向的节点
820 if head == None or k == 0:
821 return None
822
823 else:
824 bef = head
825 for i in range(k):
826 if bef.next != None:
827 bef = bef.next
828 else:
829 return None
830 after = head
831 while bef.next != None:
832 bef = bef.next
833 after = after.next
834 return after
835 #面试题43 和为s的n个骰子，打印出s的所有可能的值出现的概率
836 def printprobability(number):
837 g_maxValue=6
838 #初始化两个数组为0
839 probabilitis=[]
840 prob1=[]
841 prob2=[]
842 for i in range(g_maxValue*number+1):
843 prob1.append(0)
844 prob2.append(0)
845 probabilitis.append(prob1)
846 probabilitis.append(prob2)
847
848 flag=0
849 #1个骰子时，1-6都是1次
850 for i in range(1,g_maxValue+1):
851 probabilitis[flag][i]=1
852 #2-number个骰子时，通过计算本次循环对应的和为n的骰子出现的次数
853 # 是上次循环中骰子点数中和为n-1,n-2,n-3,n-4,n-5,n-6的次数之和
854 for k in range(2,number+1):
855 for i in range(k):
856 probabilitis[1-flag][i]=0
857 for i in range(k,g_maxValue*k+1):
858 probabilitis[1-flag][i]=0
859 m=min(i,g_maxValue)
860 for j in range(1,m+1):
861 probabilitis[1-flag][i]+=probabilitis[flag][i-j]
862 flag=1-flag
863 #求和之后除以6的n次方（和的可能数）求概率
864 total=pow(g_maxValue,number)
865 for i in range(number,g_maxValue*number+1):
866 ratio=probabilitis[flag][i]/total
867 print(ratio)
868 # printprobability(2)
869
870 #实现两个函数，分别用来序列化和反序列化二叉树
871 #序列化 得到二叉树对应的字符串序列
872
873 def Serialize(root):
874 sarializeCore(root)
875 return s
876 def sarializeCore(root):
877 if root is None:
878 s=s+'#,'
879 return
880 s+=str(root.val)+','
881 sarializeCore(root.left)#左
882 sarializeCore(root.right)#右
883 s = '' # 全局变量
884
885 #反序列化
886 def Deserialize(s):
887 if s is None:
888 return None
889 if len(s)==1 and s[0]=='#':
890 return None
891 index=0
892 s=s.split(',')
893 root=DeserializeCore(s)
894 return root
895 def DeserializeCore(s):
896 t=s[index]#index从0开始，并且由于构建是先序遍历构建的，前面是左节点
897 if t.isdigit():
898 root=TreeNode(int(t))#构建节点
899 index+=1
900 left=DeserializeCore(s)#由于上面的原因 所以首先递归得到的是左节点
901 right=DeserializeCore(s)
902 root.left=left#放入左节点
903 root.right=right#放右节点
904 return root
905 elif t=='#':
906 index+=1
907 return None#返回None节点
908
909 #约瑟夫环
910
911 def LastRemaining_Solution(n, m):
912 # write code here
913 child = list(range(n))
914 cur = 0
915 while len(child) > 1:
916 for i in range(1,m):#从第0个开始数m个，则只需移动两次
917 cur += 1
918 if cur == len(child):
919 cur = 0
920 child.remove(child[cur])#移除一个元素后cur指向的是原列表中的下一个，即cur不需动
921 if cur==len(child):#由于移除了一个元素，则cur需要注意是否为新的列表的长度
922 cur=0
923 return child[0]
924 # print(LastRemaining_Solution(5,3))
925 #twosum 方法二是通过构建哈希表得到对应下标
926 # 先排序，再通过建立两个前后夹逼的指针得到最终结果
927 def twoSum(nums, target):
928 if len(nums) == 0:
929 return []
930
931 # nums1=sorted(nums)#排序后元素下标与原来的不一样了 直接排序会导致最后返回的下标是排序后元素的下标，而不是原列表
932 nums1=sorted(range(len(nums)),key=lambda k:nums[k])
933 #对range(len(nums))按照nums中元素大小，从小到大排序。key=是sorted函数的关键词，k是参数，nums[k]是对k的操作，此处是直接取nums[k]
934 print(nums1)
935 one = 0
936 two = len(nums) - 1
937 final = []
938 while one < two:
939 if (nums[nums1[one]] + nums[nums1[two]]) == target:
940 final.append(nums1[one])
941 final.append(nums1[two])
942 return final
943 elif target < (nums[nums1[one]] + nums[nums1[two]]):
944 two -= 1
945 elif target > (nums[nums1[one]] + nums[nums1[two]]):
946 one += 1
947 return []
948 # print(twoSum([3,2,4],6))
949 #二维数组中元素查找
950 def findinarray(target,array):
951 row=0
952 col=len(array[0])-1
953 while row>=0 and row<len(array[0]) and col>=0:
954 print(row,col)
955 if array[row][col]==target:
956 return True
957 elif array[row][col]>target:
958 col-=1
959 elif array[row][col]<target:
960 row+=1
961 return False
962 # a=np.array([[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]])
963 # print(findinarray(7,a))
964 #将一个字符串中的每个空格替换成“%20”
965 def replaceSpace( s):
966 # write code here
967 '''
968 #复杂度为o(n^2)
969 if ' 'in s:
970 b=s.replace(' ','%20')
971 return b
972 else:
973 return s'''
974 # 方法2 从后往前替换 复杂度o(n)
975 kongge = s.count(' ') # 空格个数
976 newlist = list(s)
977 for i in range(kongge*2):
978 newlist.append(' ')
979 p1 = len(s) - 1 # 原字符串最后一个元素位置
980 p2 = len(newlist) - 1 # 新字符串最后一个元素位置
981 while p1 != p2:
982 print(p1,p2)
983 if newlist[p1] != ' ':
984 newlist[p2] = newlist[p1]
985 p1 -= 1
986 p2 -= 1
987 elif newlist[p1] == ' ':
988 newlist[p2] = '0'
989 newlist[p2 - 1] = '2'
990 newlist[p2 - 2] = '%'
991 p1 -= 1
992 p2 -= 3
993 newstr=''
994 for i in newlist:
995 newstr=newstr+i
996 return newstr
997 # print(replaceSpace(" helloworld"))
998 #python 中list的pop()操作：
999 def listpop():
1000 li=[1,2,3]
1001 li.pop(1)#若无参数，默认删除最后一个元素；参数为1表示删除第2个元素 默认只要执行pop操作就会删除掉最后一个元素
1002 m=li.pop()#若将pop的结果赋值，则m为目前的最后一个元素
1003 print(m)
1004 print(li)
1005 #重建二叉树:注意list[n:m]取不到下标为m的元素 如
1006 # pre=[1, 2, 4, 7, 3, 5, 6, 8] print(pre[0:3])输出为[1,2,4]
1007 def reconstructtree(pre,tin):
1008 if pre==None:
1009 return None
1010 root=pre[0]
1011 print(root)
1012 ind=tin.index(pre[0])
1013 left=reconstructtree(pre[1:ind+1],tin[:ind])
1014 print(left)
1015 right=reconstructtree(pre[ind+1:],tin[ind+1:])
1016 print(right)
1017
1018 # pre=[1, 2, 4, 7, 3, 5, 6, 8]
1019 # tin=[4, 7, 2, 1, 5, 3, 8, 6]
1020
1021 # reconstructtree(pre,tin)
1022 #递归的斐波那契数列
1023 def fibbaqi(n):
1024 if n==0:
1025 return 0
1026 if n==1:
1027 return 1
1028
1029 return (fibbaqi(n-1)+fibbaqi(n-2))
1030
1031 #循环的斐波那契数列
1032 def fibbaqi_1(n):
1033 a=0
1034 b=1
1035 while b<=n:
1036 print(b)
1037 a,b=b,a+b
1038 #第二种方法实现斐波那契数列
1039 def fibbaqi_2(n):
1040 if n<=1:
1041 return n
1042 else:
1043 res=[0,1]
1044 for i in range(2,n):
1045 res.append(res[i-2]+res[i-1])
1046 return res
1047
1048 #数值的整数次方
1049 def power(base,exp):
1050 if base==0 or exp<1:
1051 print(base)
1052 return 0
1053 result=1
1054 if exp>1:
1055 while exp>0:
1056 result=result*base
1057 exp-=1
1058 return result
1059 if exp<0:#负的小数没考虑
1060 exp=-exp
1061 while exp>1:
1062 result=result*base
1063 exp-=1
1064 return 1/result
1065 # print(power(0.0,3))
1066 # print(2.5 + 10 / 4)
1067 #twosum 两数之和 (twoSum1()在数组中有相同元素的情况下不通过，因为我是备份了一个待排序的列表nums,然后再获
1068 #取元素下标，如[3.3]，target=6,我的结果是[0,0]而本应得到[0,1]
1069 #twosum()可以直接通过 )
1070 class Solution3:
1071 def twoSum1(self, nums, target):
1072 if len(nums)==0:
1073 return None
1074 newnums=nums.copy()
1075 nums=self.sort(nums)
1076 first=0
1077 end=len(nums)-1
1078 while(first!=end):
1079 if nums[first]+nums[end]>target:
1080 end-=1
1081 elif nums[first]+nums[end]<target:
1082 first+=1
1083 elif nums[first]+nums[end]==target:
1084 final=[]
1085 final.append(newnums.index(nums[first]))#取列表元素的下标
1086 final.append(newnums.index(nums[end]))
1087 return final
1088 return None
1089 #冒泡排序
1090 def sort(self,nums):
1091 for i in range(len(nums)):
1092 for j in range(i+1,len(nums)):#注意第二个循环的控制条件，从i+1开始，到最后一个元素结束
1093 if nums[i]>nums[j]:
1094 temp=nums[i]
1095 nums[i]=nums[j]
1096 nums[j]=temp
1097 return nums
1098 def twosum(self,nums,target):
1099 #不对列表元素排序，而是根据列表元素大小对列表下标排序
1100 sorted_id=sorted(range(len(nums)),key=lambda k:nums[k])#!!!!!!!
1101 first=0
1102 end=len(nums)-1
1103 while first!=end:
1104 if nums[sorted_id[first]]+nums[sorted_id[end]]>target:
1105 end-=1
1106 elif nums[sorted_id[first]]+nums[sorted_id[end]]<target:
1107 first+=1
1108 elif nums[sorted_id[first]] + nums[sorted_id[end]] == target:
1109 final=[]
1110 final.append(sorted_id[first])
1111 final.append(sorted_id[end])
1112 return final
1113 return None
1114 # s=Solution3()
1115 # print(s.twosum([2,4,3,1,0,5],4))
1116 # x_str=[1,2,3]
1117 # for i in range(len(x_str)-1,0,-1):#第三个参数是控制循环的步长，
1118 # # 第一个参数是从第几个开始，第二个参数是到第n+1个结束。如上，输出到第0+1个元素结束
1119 # print(x_str[i])
1120 # print(int('-12'))
1121 def func1():
1122 l=['1','2']
1123 print(''.join(l))#字符串通过某字符链接
1124 #两个队列实现一个栈pop和push操作
1125 #push()操作：
1126 #为了保证先进栈的元素一直在栈底，需要将两个队列交替使用，才能满足需求。
1127 # 因此，想法是，我们只在空的那个队列上添加一个元素，然后把非空的那个队列中的元素依次从前到后全部追加到当前这个队列。
1128 # 这样一来，我们又得到一个空的队列，供下一次添加元素。
1129 # pop()操作：
1130 #因为在添加元素时，我们已经按照进栈的先后顺序把后进栈的元素放在一个队列的头部，所以出栈操作时，
1131 # 我们只需要找到那个非空的队列，并依次取出数据即可。
1132 class stack_com:
1133 def __init__(self):
1134 self.que1 = []
1135 self.que2 = []
1136 def stack_com_push(self,x):
1137 if len(self.que1)==0:#先用的que1
1138 self.que1.append(x)
1139 elif len(self.que2)==0:#后用的que2 则下一步判断两个队列哪个只有1个元素的时候，先为que2加入元素，则符合后面进来的在最前面
1140 self.que2.append(x)
1141 if len(self.que2)==1 and len(self.que1)>=1:#第一次两个队列都是1个元素的情况下，将que1的内容加入que2
1142 #之后肯定是一个列表为空（或有1个元素），另一个有多个元素。然后哪个有1个元素则将有多个元素的队列的内容从前到后依次加入其中
1143 while self.que1:
1144 self.que2.append(self.que1.pop(0))
1145 elif len(self.que1)==1 and len(self.que2)>1:
1146 while self.que2:
1147 self.que1.append(self.que2.pop(0))
1148 def stack_com_pop(self):
1149 if len(self.que1)!=0:
1150 return self.que1.pop(0)
1151 elif len(self.que2)!=0:
1152 return self.que2.pop(0)
1153 else:
1154 return None
1155 #调整数组顺序 奇数在前偶数在后，且调整前后相对位置不变
1156 #插入排序的思想，只是把判断大小改为判断奇数偶数
1157 def reOrderArray(array):
1158 # write code here
1159 # ood,even=[],[]#新建两个列表，分别存储奇数、偶数
1160 #
1161 # for a in array:#数组可以通过循环依次得到各个元素
1162 # if a%2==0:
1163 # even.append(a)
1164 # else:
1165 # ood.append(a)
1166 # return ood+even
1167 for i in range(len(array)):
1168 #如果遇到奇数，则判断前面是否有偶数，如果有偶数，则交换顺序，没有，则不动，则不会改变相对位置
1169 if (array[i] % 2) != 0 and i != 0:#第0个元素若是偶数，不用处理；若是奇数，由于下面有i-1的处理，则需要判断
1170 temp = array[i]
1171 print(temp)
1172 j = i - 1
1173 while j >= 0 and array[j] % 2 == 0:
1174 array[j + 1] = array[j]
1175 j -= 1
1176 array[j + 1] = temp
1177 return array
1178 # print(reOrderArray([1,2,3,4,5,6,7]))
1179
1180 #树的子结构
1181 class TreeNode1:
1182 def __init__(self,x):
1183 self.val=x
1184 self.left=None
1185 self.right=None
1186 def findnode(self,root1,root2):
1187 result=False
1188 if root1 and root2:#若两个都非None才继续
1189 if root1.val==root2.val:#找到值相同的节点后，判断两节点下面的子结构是否一样
1190 result=self.doeshave(root1,root2)
1191 if not result:#若上面找到的值相同的节点对应的结构不同，去左节点找
1192 result=self.findnode(root1.left,root2)#!!!!!!!左边要赋值
1193 if not result:
1194 result=self.findnode(root1.right,root2)
1195 #判断两个节点下面的子结构是否一样
1196 def doeshave(self,root1, root2):
1197 #若只需要root1中有root2对应的树的结构即可，则前两个if条件如下注释所示
1198 # if root2 is None:
1199 # return True
1200 # if root1 is None:
1201 # return False
1202 #若两棵树的子结构必须完全一致，即root1在找到root2子结构后，下面没有与root2不一致的节点。前两个if代码如下
1203 if root2 is None and root1 is None:#
1204 return True
1205 if root1 is None or root2 is not None:
1206 return False
1207 if root1.val!=root2.val:
1208 return False
1209 #return关键词不能少
1210 return self.doeshave(root1.left,root2.left) and self.doeshave(root1.right,root2.right)
1211 #顺时针打印矩阵
1212 #方法一
1213 #打印的同时pop掉二维列表中的元素，则可以每次只考虑还剩余的元素
1214 def start_get1(matrix):
1215 # matrix=[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
1216 # #[[13, 14, 15, 16], [9, 10, 11, 12], [5, 6, 7, 8], [1, 2, 3, 4]]
1217 # print(matrix[::-1])#只是输出了矩阵的逆序，原矩阵序列没有改变
1218 # print(matrix)
1219 res=[]
1220 while matrix:
1221 #每轮循环肯定有从左到右，所以不需判断
1222 res+=(matrix.pop(0))#输出第一行。由于得到的是列表，所以与原列表相加，而不是append
1223 #判断是否需要从上到下访问，如果在上一步结束后仍然有元素，说明需要从上到下访问
1224 if matrix and matrix[0]:
1225 for row in matrix:
1226 res.append(row.pop())#该列最后一个元素是res.append(row[-1])，但是我们要pop掉该元素，所以不能这么用
1227 #从右到左
1228 if matrix and matrix[-1]:
1229 res+=(matrix.pop()[::-1])
1230 #从下到上
1231 if matrix and matrix[0]:
1232 for row in matrix[::-1]:
1233 res.append(row.pop(0))
1234 print(res)
1235 #方法二:下标控制比较麻烦，方法一比较简单
1236 def start_get2(matrix):
1237 start=0
1238 columns=len(matrix[0])
1239 rows=len(matrix)
1240 while columns>start*2 and rows>start*2:
1241 printcircle(matrix,columns,rows,start)
1242 start+=1
1243 def printcircle(matrix,columns,rows,start):
1244 endx=columns-1-start#一行最后一个下标
1245 endy=rows-1-start#一列最后一个下标
1246 #每个循环都与start相关
1247 for i in range(start,endx+1):
1248 print(matrix[start][i])
1249 #从上到下
1250 if endy>start:#比start大，即需要往下走
1251 for j in range(start+1,endy+1):#start对应的元素已经访问过
1252 print(matrix[j][endx])
1253 #从右到左,有从右到左则接下来一定有从下到上，所以还有第二个条件
1254 if endx>start and endy>start:
1255 #range取到开头取不到结尾 第三个参数为步长 -1表示逆序
1256
1257 for i in range(endx-1,start-1,-1):#range(endx-1,start-1,-1)第二个元素表示从下标为endx-1到start,取不到start-1
1258 print(matrix[endy][i])
1259 #从下到上
1260 if endy>start:
1261 for j in range(endy-1,start,-1):
1262 print(matrix[j][start])
1263 # start_get2(matrix=[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]])
1264
1265 #二叉树中和为某一值的路径.代码通过。 实际上是二叉树的先序遍历递归实现，
1266 # 只是在递归的过程中加入了比较操作.特别是注意对当前值的求和操作，由于递归操作，栈会记录求和值，所以currentSum只需写求和操作
1267 def findpath(root,expectNumber):
1268 if not root:
1269 return []
1270 result=[]
1271 def FindPathMain(root,path,currentSum):
1272 currentSum+=root.val#递归调用的时候，会用栈存储当前值
1273 path.append(root)
1274 isLeaf=(root.left==None and root.right==None)#左右子节点都是None此时为叶子节点
1275 if currentSum==expectNumber and isLeaf:#路径之和=期望值 且为叶子节点 达到期望则此时path为符合条件的路径
1276 onePath=[]
1277 for node in path:
1278 onePath.append(node.val)
1279 result.append(onePath)
1280 if currentSum<expectNumber:#currentSum较小时才继续查找左右子节点
1281 if root.left:
1282 FindPathMain(root.left,path,currentSum)
1283 if root.right:
1284 FindPathMain(root.right,path,currentSum)
1285 path.pop()#左右子树都遍历完，删除当前点 确保path中是从上到下的一条路径
1286 FindPathMain(root,[],0)
1287 return result
1288 #判断是否为对称二叉树
1289 class Node:
1290 def __init__(self,x):
1291 self.val=x
1292 self.left=None
1293 self.right=None
1294 class Solution4:
1295 #方法一 别人的代码，可以通过，但是由于涉及递归，不是很清楚为什么这么写
1296 def isSymmetrical(self, pRoot):
1297 # write code here
1298 if not pRoot:
1299 return True
1300 def Traversal(left, right):
1301 if left is None and right is None:
1302 return True
1303 elif left and right and left.val == right.val:
1304 return Traversal(left.left, right.right) and Traversal(left.right, right.left)
1305 else:
1306 return False
1307 return Traversal(pRoot.left, pRoot.right)
1308 #方法二：代码通过 两种前序遍历：左-》右 右-》左 分别得到的列表，判断两列表是否相同
1309 # def isSymmetrical2(self, pRoot):
1310 # self.res1=[]
1311 # self.res2=[]
1312 # # node1=pRoot
1313 # # node2=pRoot
1314 # self.l2r(pRoot)
1315 # self.r2l(pRoot)
1316 # print(self.res1)
1317 # print(self.res2)
1318 # if self.res1==self.res2:
1319 # return True
1320 # else:
1321 # return False
1322 # def l2r(self,pRoot):
1323 # if not pRoot:
1324 # self.res1.append('#')#遇到叶子节点依然要加入self.res中
1325 # return None
1326 # self.res1.append(pRoot.val)
1327 # left=self.l2r(pRoot.left)
1328 # right=self.l2r(pRoot.right)
1329 # def r2l(self,pRoot):
1330 # if not pRoot:
1331 # self.res2.append('#')
1332 # return None
1333 # self.res2.append(pRoot.val)
1334 # right=self.r2l(pRoot.right)
1335 # left=self.r2l(pRoot.left)
1336 #二叉树反序列化，即输入是先序遍历得到的节点序列列表（叶节点的孩子为‘#’）建树（不是判断对称二叉树那道题）
1337 def Deserialize(self,s):#输入先序遍历后的节点值列表（孩子为None的加入#）
1338 self.index=0
1339 root=self.De(s)
1340 return root
1341 def De(self,s):
1342 t=s[self.index]
1343 self.index += 1
1344 if t!='#':#t.isdigit()只能用于判断字符是否为数字
1345 root=Node(int(t))
1346
1347 left=self.De(s)
1348 right=self.De(s)
1349 root.left=left
1350 root.right=right
1351 return root
1352 elif t=='#':
1353 # self.index+=1
1354 return None
1355
1356 def FindPath(self, root, expectNumber):
1357 if not root:
1358 return []
1359 result = []
1360
1361 def FindPathMain(root, path, currentSum):
1362 currentSum += root.val
1363 path.append(root)
1364 isLeaf = (root.left == None and root.right == None) # 左右子节点都是None此时为叶子节点
1365 if currentSum == expectNumber and isLeaf:
1366 onePath = []
1367 for node in path:
1368 onePath.append(node.val)
1369 result.append(onePath)
1370 if currentSum < expectNumber:
1371 if root.left:
1372 FindPathMain(root.left, path, currentSum)
1373 if root.right:
1374 FindPathMain(root.right, path, currentSum)
1375 path.pop()
1376
1377 FindPathMain(root, [], 0)
1378 return result
1379 # # #手动建树
1380 # node8=Node(8)
1381 # node61=Node(6)
1382 # node62=Node(6)
1383 # node51=Node(5)
1384 # node52=Node(5)
1385 # node71=Node(7)
1386 # node72=Node(7)
1387 # node8.left=node61
1388 # node8.right=node62
1389 # node61.left=node51
1390 # node61.right=node71
1391 # node62.left=node72
1392 # node62.right=node52
1393 # s=Solution4()
1394 # # print(s.isSymmetrical(node8))#判断对称二叉树
1395 # print(s.FindPath(node8,26))
1396 # tree=s.Deserialize(['8','6','5','#','#','7','#','#','6','7','#','#','#'])#反序列化
1397 # print(tree.val,tree.left.val,tree.right.val)
1398
1399 # print(-np.log2(1/6))
1400 #中兴笔试题：工资排序
1401 def solution(num,salaries):
1402 if num != len(salaries):
1403 return 0
1404 dic = {}
1405 sal = []
1406 for i in salaries:
1407 if i not in sal:
1408 sal.append(i)
1409 for i in sal:
1410 dic[i] = salaries.count(i)
1411
1412 temp = sorted(dic.items(),key=lambda x:x[1],reverse=True)
1413
1414 res = []
1415 for key,value in temp:
1416 for j in range(value):
1417 res.append(key)
1418 return res
1419 # print(solution(14,[1,2,1,2,2,3,4,1,3,5,6,87,32,3]))
1420 #不用比较找出两数中的较大值和较小值 https://blog.csdn.net/qq_34342154/article/details/77871202
1421 # print(((-3)>>31)&1)
1422 #判断n的二进制表示中有几个1
1423 def Numberof1(n):
1424 m=0
1425 result=0
1426 while m<32:
1427 if n&1:#判断n的最后一位是否为1
1428 result+=1#统计最后一位是1的次数
1429 n=n>>1#右移一位
1430 m+=1#移位次数统计
1431 return result
1432 # print(numberof1(3))
1433 def num_1(n):
1434 ans=0
1435 if n<0:
1436 n = n & 0xffffffff
1437 while n:
1438 # print(n)
1439 n=n&(n-1)
1440 ans+=1
1441 return ans
1442 # print(num_1(-3))
1443 # print(1^1)#^为异或，相异为1，相同为0
1444
1445
1446
1447 #不用比较判断两数字大小
1448 def num_judge(a,b):
1449 c=a-b
1450 s=sigh(c)#c的正负号，返回0或1，正数返回0，负数返回1
1451 w=flip(s)#与c的符号相反的符号。依然得到1或0
1452 print(a*s+b*w)#s与w一0一1，相加得到其中一个较小的数，
1453 # if w==0:
1454 # print(b,'较大')
1455 # else:
1456 # print(a,'较大')
1457 def sigh(n):##正数和0 返回0；负数返回1
1458 return (n>>32)&1
1459 def flip(n):#n是1则返回0，是0返回1
1460 return n^1
1461 # num_judge(2,3)
1462 #简单解释一下。
1463 #如果a和b的符号不同（difSab = 1, sameSab = 0），则有：
1464 # 如果a为0或正，那么b为负（sa = 1, sb = 0），应该返回a
1465 # 如果b为0或正，那么a为负（sb = 1, sa = 0），应该返回b
1466 #如果a和b的符号相同（difSab = 0, sameSab = 0），此时一定不会发生溢出:
1467 # 如果a - b为0或者为正(sc = 1)，返回a
1468 # 如果a - b为负(sc = 0 )，返回b
1469
1470 def num_judge2(a,b):
1471 sa=sigh(a)
1472 sb=sigh(b)
1473 sc=sigh(a-b)#a-b的正负号
1474 difsab=sa^sb
1475 samesab=flip(difsab)#与difsab符号相反的数
1476 returnA=sa*difsab+sc*samesab
1477 returnB=flip(returnA)
1478 print(a*returnA+b*returnB)
1479 # num_judge2(2,3)
1480 #三数之和:给定一个列表，找出其中符合a+b+c=0的三个数字
1481 def threesum(lis):
1482 lis.sort()
1483 solution=[]
1484 for i in range(len(lis)):
1485 left=i+1
1486 right=len(lis)-1
1487 while left<right:
1488 #既判断三者和是否为0,；还判断这三个数组成的列表是否已经在结果集中
1489 if lis[left]+lis[right]==(-lis[i]) and [lis[left],lis[right],lis[i]] not in solution:
1490 solution.append([lis[left],lis[right],lis[i]])
1491 left+=1
1492 right-=1
1493 elif lis[left]+lis[right]<(-lis[i]):
1494 left+=1
1495 elif lis[left]+lis[right]>(-lis[i]):
1496 right-=1
1497 #从m个数中随机选出n个数，要求每个数的概率均等，时间复杂度为o(n)
1498 def choose_n():
1499 #1.输入m个数字
1500 #map函数解释 https://www.cnblogs.com/ConnorShip/p/10004008.html
1501 #以空格为分隔符输入一行数字，split为字符串列表，通过map（int）转为整形，再经过list转成数字列表
1502 m=list(map(int,input().split()))#input()以字符串的方式获取用户输入,split()默认通过空格分割字符串
1503 print(m)
1504 #2.输入想选出的数字个数
1505 n=map(int,input().split())
1506 print(n)
1507 #3.依次迭代n的每个元素
1508 nn=next(n)
1509 print(nn)
1510 #
1511 for i in range(nn):#循环nn次
1512 num=random.randint(0,len(m))#随机生成[0,len(m)]的整数,当num=0时，num-1=-1即取到列表最后一个元素，没问题？？？
1513 print(num)
1514 m[i],m[num-1]=m[num-1],m[i]#将原本在m前面的nn个数字置换为随机数对应位置的数字
1515 print(m[:nn])
1516 # choose_n()
1517 # print(list(map(int,input().split())))
1518 #字符列表转为字符串
1519 # l=['w','d']
1520 # print(''.join(l))
1521 #KMP算法
1522 #1.这个链接计算next数组的动图很好理解，但是与我们的代码实现不一样https://blog.csdn.net/qq_37969433/article/details/82947411
1523 #2.代码是这个链接的https://www.cnblogs.com/imzhr/p/9613963.html
1524 #2得到的next数组可以由1得到的next数组右移一位，整体减1，最前面补一个-1得到。即这种方法得到的next数组永远为-1
1525 def getNextArray(t):
1526 #初始化next数组：第一个元素为-1，其余为0
1527 next=[-1,0]#默认next[0]=-1,由于第一个元素的前后缀公共子序列总是为0，所以直接初始化为0
1528 for j in range(2, len(t)):
1529 next.append(0)
1530 #从next第二个元素开始计算其前面字符串的公共子序列
1531 for j in range(2,len(t)):
1532 k=next[j-1]#k为上一个位置的next值
1533 while k!=-1:
1534 if t[j-1]==t[k]:#若通过判断模式字符串中元素发现有相同元素
1535 next[j]=k+1#
1536 break#！！！！！注意这个时候要break
1537 else:
1538 k=next[k]
1539 next[j]=0#//当k==-1而跳出循环时，next[j] = 0，否则next[j]会在break之前被赋值
1540 print('next数组',next)
1541 return next
1542 def kmpMatch(s,t):
1543 #！！！！！！注意先把字符串转换成字符数组的操作在python中可以不需要写
1544 s_arr=s
1545 t_arr=t
1546 next=getNextArray(t_arr)
1547 i=0
1548 j=0
1549 while i<len(s_arr) and j<len(t_arr):
1550 if j==-1 or s_arr[i]==t_arr[j]:#若第一个元素就没有匹配成功（next数组第一个元素为-1） 或者 两字符串对应的元素匹配成功
1551 #则两个字符串的下标分别加1
1552 i+=1
1553 j+=1
1554 else:#其它未匹配成功的情况
1555 j=next[j]#被匹配的字符串s对应的下标i不变，模式t的下标j更新为next[j]，即从next[j]对应的位置开始往后匹配。
1556 # 此时对应的模式t向右移动的位数为：已经匹配的字符数-next[j]
1557 if j==len(t_arr):#若匹配结束
1558 return i-j#返回i-j
1559 else:#未匹配结束，返回-1
1560 return -1
1561 # print(kmpMatch("abcabaabaabcacb", "abaabcac"))
1562 #从尾到头打印链表
1563 class ListNode:
1564 def __init__(self,x):
1565 self.val=x
1566 self.next=None
1567 self.l=[]
1568 def printlist(self,listNode):
1569 head=listNode
1570 if head:
1571 if head.next:#若有下一个节点才继续递归 即压入栈
1572 self.printlist(head.next)
1573 self.l.append(head.val)#没有next的时候将该节点值加入列表self.l中，然后return self.l,然后调用上一步的printlist函数
1574 print(self.l)
1575 return self.l
1576
1577 def ReverseList(self, pHead):
1578 # write code here
1579
1580 node = pHead.next
1581 pHead.next = None
1582 while node != None:
1583 nextnode = node.next
1584 node.next = pHead
1585 pHead = node
1586 node = nextnode
1587 return pHead
1588 # l1=ListNode(1)
1589 # l2=ListNode(2)
1590 # l3=ListNode(3)
1591 # l1.next=l2
1592 # l2.next=l3
1593 # nodes=l1.ReverseList(l1)
1594 # while nodes.next!=None:
1595 # print(nodes.val)
1596 # nodes=nodes.next
1597 # print(nodes.val)
1598 # l1.printlist(l1)
1599
1600
1601 #将字符串逆序
1602 def fun():
1603 str1='12345'
1604 #str[begin:end:step]
1605 # str2=str1[::-1]#字符串逆序
1606 str2=str1[0:3]#字符串截取操作
1607 print(str2)
1608 # fun()
1609 #旋转数组的最小数字
1610 def minNumberInRotateArray2(rotateArray):
1611 # write code here
1612 if len(rotateArray) == 0:
1613 return 0
1614 left = 0
1615 right = len(rotateArray) - 1
1616 mid = int((left + right) / 2)
1617 while right - left > 1:
1618 if rotateArray[left] <= rotateArray[mid]:##注意一定要加上=，否则遇到相同的值指针不动
1619 left = mid
1620 elif rotateArray[left] >= rotateArray[mid]:##注意一定要加上=，否则遇到相同的值指针不动
1621 right = mid
1622 mid=int((left + right) / 2)#注意 left和right都更新后不要忘记更新mid
1623 return rotateArray[right]
1624 # print(minNumberInRotateArray2([3,4,5,1,2]))
1625 #判断给定数字1的个数
1626 #输入一个整数。判断该数共有几个1 本代码在python不可行
1627 def NumberOf1(n):
1628 # write code here
1629 count = 0
1630 while n != 0:
1631 count += 1
1632 n = n & (n - 1)
1633 return count
1634 # print(NumberOf1(-3))
1635 #二进制中1的个数 本代码在python貌似不可行
1636 def numberof1(n):
1637 flag=1
1638 count=0
1639 while flag!=0:
1640 print(flag)
1641 if n&(flag):
1642 count+=1
1643 flag=flag<<1
1644 print(count)
1645 # numberof1(4)
1646 #https://blog.csdn.net/qq_34872215/article/details/88936030
1647 #将数字转化成整型二进制数
1648 def numberof1_2(n):
1649 if n>=0:
1650 return bin(n).count('1')
1651 else:
1652 return bin(n & 0xffffffff).count('1')
1653 #直接对n处理判断而不通过转换
1654 def numberof1_3(n):
1655 count=0
1656 while n & 0xffffffff!=0:#但是需要与0xfffffff做与运算
1657 count+=1
1658 n=n & (n-1)
1659 return count
1660 # print(numberof1_3(-3))
1661 #合并两个有序链表
1662 def Merge(pHead1, pHead2):
1663 dummy = ListNode(0)
1664 pHead = dummy
1665 while pHead1 and pHead2:
1666 if pHead1.val >= pHead2.val:
1667 dummy.next = pHead2
1668 pHead2 = pHead2.next
1669 else:
1670 dummy.next = pHead1
1671 pHead1 = pHead1.next
1672 dummy = dummy.next
1673
1674 if pHead1:
1675 dummy.next = pHead1
1676 if pHead2:
1677 dummy.next = pHead2
1678 return pHead.next
1679 #树的子结构
1680 def HasSubtree(self, pRoot1, pRoot2):
1681 # write code here
1682 result = False # 初始状态为false，因为要判断两树是否有一个空树
1683 if pRoot1 != None and pRoot2 != None:
1684 if pRoot1.val == pRoot2.val: # 若根节点值相等则继续判断左右子节点
1685 result = self.Dosesubtree(pRoot1, pRoot2)
1686 if not result: # 若B不是从根节点开始与A匹配，则重新从A的左节点开始匹配，一直递归直到没有左节点再去遍历右节点
1687 result = self.HasSubtree(pRoot1.left, pRoot2) # 注意这里是递归HasSubtree函数，不能只判断Dosesubtree函数
1688 if not result:
1689 result = self.HasSubtree(pRoot1.right, pRoot2)
1690 return result
1691
1692 def Dosesubtree(self, proot1, proot2):
1693 if proot2 == None:
1694 return True
1695 if proot1 == None:
1696 return False
1697 if proot1.val != proot2.val:
1698 return False
1699 return self.Dosesubtree(proot1.left, proot2.left) and self.Dosesubtree(proot1.right, proot2.right)
1700
1701 #二叉树的镜像
1702 # 返回镜像树的根节点
1703 def Mirror(self, root):
1704 # write code here
1705 if root==None:#需要先判断是否为none否则报错显示nonetype has no left
1706 return root
1707 #交换左右节点
1708 left=root.left
1709 root.left=root.right
1710 root.right=left
1711 #递归走向左右节点（递归不需要写while循环，每次调用该函数）
1712 if root!= None:
1713 self.Mirror(root.left)
1714 #print(self.nodeconcat(current))
1715 self.Mirror(root.right)
1716 return root
1717 #
1718 # l=[1,2,3,4]
1719 # a='1234'
1720 # #[::-1]不会改变原对象内容，是生成一个新的基于原对象的逆序列对象
1721 # a2=a[::-1]
1722 # l2=l[::-1]
1723 # print(a2)
1724 # 包含min函数的栈
1725 class Solution5:
1726 def __init__(self):
1727 self.stack = []
1728 self.assist = [] # 存储每次加入一个元素时‘
1729 # 当前（注意这个地方，就是说目前stack内的所有元素中最小值，之后若有pop操作，同时弹出辅助栈的栈顶元素，依然保持辅助栈栈顶为当前最小值）’
1730 # 栈内所有元素的最小值，构成辅助栈
1731
1732 def push(self, node):
1733 # write code here
1734 mini = self.min()
1735 if node < mini or mini is None: # min中没有元素时第一次min函数返回的是None
1736 self.assist.append(node)
1737 else:
1738 self.assist.append(mini)
1739 self.stack.append(node)
1740
1741 def pop(self):
1742 # write code here
1743 if self.stack and self.assist:
1744 self.assist.pop() # 每次往栈内压入一个元素时都会往辅助栈压入当前最小值，在弹出栈顶元素时，辅助栈也该弹出栈顶元素，
1745 return self.stack.pop() # 否则辅助栈的栈顶依然是原栈未弹出栈顶元素的元素中的最小值
1746
1747 def top(self):
1748 # write code here
1749 if self.stack:
1750 return self.stack[-1]
1751
1752 def min(self):
1753 # write code here
1754 if self.assist:
1755 return self.assist[-1]
1756
1757 #栈的压入弹出序列
1758 def IsPopOrder(self, pushV, popV):
1759 # write code here
1760 res = []
1761 for p in pushV:
1762 res.append(p) # 依次将压入栈的数字加入辅助列表
1763 while res: # 如果栈不为空，
1764 if popV[0] == res[-1]: # 且栈顶元素等于弹出序列
1765 popV.pop(0)
1766 res.pop()
1767 else: # 栈顶元素不等于弹出序列
1768 break
1769 if len(res) == 0: # 最后辅助列表元素个数为0表示全部弹出，序列正确
1770 return True
1771 else:
1772 return False
1773
1774 def IsPopOrder2(pushV, popV):
1775 # write code here
1776 res = []
1777 for u in pushV:
1778 res.append(u)
1779 while popV and popV[0] == res[-1]:#注意比较的对象
1780 res.pop()
1781 popV.pop(0)
1782 if not popV:
1783 return True
1784 else:
1785 return False
1786 # print(IsPopOrder2([1,2,3,4,5],[4,5,3,2,1]))
1787 #从上往下打印二叉树
1788 def PrintFromTopToBottom(self, root):
1789 # write code here
1790 if root: # 注意要判断该树是否为空
1791 res = [root]
1792 numlist = [root.val]
1793 while res:
1794 newres = [] # 每次存储此次要遍历的该层所有节点
1795 for r in res:
1796 if r.left:
1797 newres.append(r.left)
1798 numlist.append(r.left.val)
1799 if r.right:
1800 newres.append(r.right)
1801 numlist.append(r.right.val)
1802 res = newres
1803 return numlist
1804 else:
1805 return []
1806 #二叉搜索树的后序遍历序列
1807 def VerifySquenceOfBST(self, sequence):
1808 # write code here
1809 if sequence==None or len(sequence) ==0:#用==判断
1810 return False
1811 else:
1812 # 二叉搜索树的后序遍历最后一个元素为根节点，剩余元素左子树在左右子树在右
1813 root = sequence[-1]#length-1
1814 length = len(sequence)
1815 for i in range(length):
1816 if sequence[i] > root: # 在序列中找到第一个大于根节点的值，i为相应位置,则将原序列分成左右子树
1817 break
1818 for j in range(i, length): # 遍历上一步得到的右子树的节点
1819 if sequence[j] < root: # 如果其中出现小于根节点的元素，则说明不符合条件
1820 return False
1821 left = True # 初始化为True，下面递归时如果出现不符合条件的会返回false
1822 if i > 0:
1823 left = self.VerifySquenceOfBST(sequence[0:i]) # 判断此时得到的左子树，为从第一个元素到第i-1(列表的最后一个元素取不到)个元素
1824 right = True
1825 if i < length - 1:
1826 right = self.VerifySquenceOfBST(sequence[i:-1]) # 判断此时得到的右子树，从第i个到最后一个
1827 return left and right # 最后返回的结果为左子树和右子树其中有一个为false则返回false
1828
1829 #复杂链表的复制
1830
1831 class Solution6:
1832 def Clone(self, pHead):
1833 # write code here
1834 self.getnewnode(pHead)
1835 self.getrandomnode(pHead)
1836 node = self.finallist(pHead)
1837 return node
1838
1839 # 对原来每个节点A依次新建新节点A'，并接在A后面
1840 def getnewnode(self, pHead):
1841 pnode = pHead
1842 pclone = pHead
1843 while pnode != None:
1844 pclone.label = pnode.label
1845 pclone.next = pnode.next
1846 pclone.random = None # 注意为节点赋值时不要落下random
1847 pclone = pnode.next # 这个地方跟书上是反着的
1848 pnode = pclone.next
1849
1850 # 为A'赋random指向的值（根据A的random）
1851 def getrandomnode(self, pHead):
1852 pnode = pHead
1853 while pnode != None:
1854 if pnode.random != None: # 注意不要落下这个判断
1855 pnode.next.random = pnode.random.next
1856 pnode = pnode.next.next
1857
1858 # 将新得到的A'为头的连边提取出来
1859 def finallist(self, pHead):
1860 pcloneHead = pHead.next
1861 pclone = pcloneHead
1862 while pclone.next != None:
1863 pnext = pclone.next.next
1864 pclone.next = pnext
1865 pclone = pnext
1866 return pcloneHead
1867 #下面的代码返回空 题目提示输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空），但是没懂？
1868 class RandomListNode:
1869 def __init__(self, x):
1870 self.label = x
1871 self.next = None
1872 self.random = None
1873 class Solution7:
1874 # 返回 RandomListNode
1875 def Clone(self, pHead): # 将链表中每个节点复制一份，并放在原来的位置
1876 # write code here
1877 head = pHead
1878 while head:
1879 node = RandomListNode(head.label)
1880 nextnode = head.next
1881 head.next = node
1882 node.next = nextnode
1883 node.random = None#为random赋值
1884 head = nextnode
1885 # while pHead:
1886 # print(pHead.label)
1887 # pHead=pHead.next
1888 return self.getlist(pHead)
1889
1890 def getlist(self, pHead): # 分别为各新节点赋指针值，以及更新原节点的指针
1891 head = pHead
1892 count = 0
1893 num = 0
1894 root = RandomListNode(0)
1895 while head:
1896 num += 1
1897 if count == 1:
1898 #注意更新赋值操作
1899 nextnode=head.next
1900 node.next = nextnode
1901 head.next = nextnode.next
1902 head.random = node.random
1903 count = 0
1904 if num == 2:
1905 root = head
1906 else:
1907 node = head
1908 count= 1
1909 head = head.next
1910 while root:
1911 print(root.label)
1912 root=root.next
1913 return root
1914 # node0 = RandomListNode(0)
1915 # node1= RandomListNode(1)
1916 # node2 = RandomListNode(2)
1917 # node0.next=node1
1918 # node1.next=node2
1919 # node0.random=node2
1920 # s=Solution7()
1921 # final=(s.Clone(node0))
1922 # while final:
1923 # print(final.label)
1924 # final=final.next
1925
1926 #将列表元素转为双向链表
1927 def Convert(root):
1928 if not root:
1929 return None
1930 if not root.left and not root.right:
1931 return root
1932 left=Convert(root.left)
1933 p=left
1934 while left and p.right:
1935 p=p.right
1936 if left:
1937 p.right=root
1938 root.left=p
1939 #连续子数组的最大和
1940 def FindGreatestSumOfSubArray(array):
1941 # write code here
1942 max=array[0]#最大值设为数组第一个元素
1943 sum=0#和为0
1944 for i in array:
1945 if sum<0:#若求和结果小于0，sum更新为当前元素。进行下一个元素的判断，此时i更新为下一个元素，但是sum依然为负数，则进入第一个判断
1946 sum=i#更新为下一个元素i
1947 else:
1948 sum=sum+i
1949 if sum>max:
1950 max=sum
1951 return max
1952
1953 # FindGreatestSumOfSubArray([1,-2,3,10,-4,7,2,-5])
1954 # print(3//2)#//表整除
1955 #将数组排成最小的数
1956 def PrintMinNumber(numbers):
1957 # write code here
1958 if len(numbers) == 0:
1959 return ''
1960 for i in range(len(numbers)):
1961 for j in range(len(numbers)):
1962 a = int(str(numbers[i]) + str(numbers[j]))
1963 b = int(str(numbers[j]) + str(numbers[i]))
1964 if b > a:
1965 t = numbers[i]
1966 numbers[i] = numbers[j]
1967 numbers[j] = t
1968 final_num = ''
1969 for n in numbers:
1970 final_num = final_num + str(n)
1971 return int(final_num)
1972 # print(PrintMinNumber([3,5,1,4,2]))
1973 #比较字符串大小
1974 # a='123'<'321'#先比较第一个字母的Unicode值，如果相等， 就比较第二个，以此类推
1975 # print(a)
1976
1977 def FirstNotRepeatingChar(s):
1978 # write code here
1979 if s == []:
1980 return -1
1981 string = [0] * 130
1982 # 对字符串中每个字符进行循环，统计出现的次数
1983 for i in s:
1984 string[ord(i)] += 1 # 字符的ASCII码为下标，对应的数组值加1
1985 for j in s: # 还是对字符串中的字符循环
1986 if string[ord(j)] == 1:
1987 return s.index(j) # index表示字符串的位置
1988 # for j in range(len(string)):
1989 # if string[j]==1:
1990 # return s.index(chr(j))-1
1991 return -1 # 上面没有返回值，说明没有找到出现一次的字符，返回-1
1992
1993 #两个链表的第一个公共节点
1994 #把全部结点分别压入两个栈，利用栈的特性LIFO，然后同时pop出栈，一开始两边的元素肯定是相同的，当遇到不同的元素时，肯定已经遇到了最后一个节点，那就break
1995 def FindFirstCommonNode(self, pHead1, pHead2):
1996 # write code here
1997 # 两个链表第一个公共节点之后的节点都是重复的，
1998 # 所以从链尾开始查找，找到最后一个两个链表相同的节点
1999 if not pHead1 or not pHead2:
2000 return None
2001 stack1 = []
2002 stack2 = []
2003 while pHead1:
2004 stack1.append(pHead1)
2005 pHead1 = pHead1.next
2006 while pHead2:
2007 stack2.append(pHead2)
2008 pHead2 = pHead2.next
2009 first = None
2010 while stack1 and stack2:
2011 node1 = stack1.pop()
2012 node2 = stack2.pop()
2013 if node1 is node2:
2014 first = node1
2015 return first
2016
2017 #数字在排序数组中出现的次数
2018 def countnum(array,k):
2019 left=leftfind(array,k)
2020 right=rightfind(array,k)
2021 return right-left+1#注意要加1，因为左右分别指向的是第一个和最后一个k
2022 def leftfind(array,k):
2023 lef=0
2024 righ=len(array)-1
2025 while lef<=righ:
2026 mid=(lef+righ)//2
2027 if array[mid]<k:
2028 lef=mid+1
2029 else:#数组中数字等于k的时候右指针向左移动，则最终左指针lef指向第一个k值
2030 righ=mid-1
2031 print(lef)
2032 return lef
2033 def rightfind(array,k):
2034 lef=0
2035 righ=len(array)-1
2036 while lef<=righ:
2037 mid = (lef + righ) // 2
2038 if array[mid]<=k:#数组中数字等于k的时候左指针向右移动，则最终左指针lef指向最后一个k值+1
2039 lef=mid+1
2040 else:#left指向第一个大于k的值时，执行本代码会得到最后一个k值指向的地方
2041 righ=mid-1#
2042 print(righ)
2043 return righ
2044 # print(countnum([1,2,3,3,4],3))
2045 #二叉树的深度
2046 def TreeDepth(self, pRoot):
2047 # write code here
2048 #层次遍历得到树的深度：构建一个队列，先在队列中增加根结点。
2049 #之后对于随意一个结点来说。在其出队列的时候，訪问之。
2050 #同一时候假设左孩子和右孩子有不为空的。入队列。
2051 if pRoot is None:
2052 return 0
2053 nodequeue=[]
2054 nodequeue.append(pRoot)
2055 lenlayer=0
2056 while nodequeue:
2057 #由于要记录深度，所以每层加入节点的时候通过控制这层加入的节点个数来判断是否到了下一层
2058 lennode=len(nodequeue)
2059 for l in range (lennode):
2060 node=nodequeue.pop(0)#出队列的是列表的第一个元素
2061 if node.left:
2062 nodequeue.append(node.left)
2063 if node.right:
2064 nodequeue.append(node.right)
2065 lenlayer+=1
2066 return lenlayer
2067
2068
2069 def FindNumbersWithSum(array, tsum):
2070 # write code here
2071 if len(array) == 0:
2072 return []
2073 low = 0
2074 high = len(array) - 1
2075 res=[]
2076 while low <= high:
2077 if array[low] + array[high] == tsum:
2078 res.append([array[low], array[high]])
2079 elif array[low] + array[high] < tsum:
2080 low += 1
2081 else:
2082 high -= 1
2083 return res
2084 # print(FindNumbersWithSum([0,2,4,7,11,15], 15))
2085 def IsContinuous(numbers):
2086 # write code here
2087 numbers.sort()
2088 count = 0
2089 print(numbers)
2090 for i in range(len(numbers) - 1):
2091 count = count + (numbers[i + 1] - numbers[i] - 1)
2092 if numbers.count(0) == count:
2093 return True
2094 else:
2095 return False
2096 # print(IsContinuous([1,3,2,5,4]))
2097 # #删除列表中某个元素
2098 # numlist=[1,2,3,4,5]
2099 #方法一
2100 # # numlist.remove(2)#删掉列表中第一次出现的元素2,类似list.sort()函数，列表改变后不需重新赋值
2101 #方法二
2102 # del numlist[2]#通过索引删除元素，索引为2的元素为3 即删掉了元素3
2103 #方法三
2104 #numlist.pop(2)#通过索引删除元素，索引为2的元素为3 即删掉了元素3
2105 # print(numlist)
2106 #不用四则运算求两数加法 牛客网上提交超时啦？？？
2107 #1.异或来求和（不考虑进位）2.求两个数的与，左移一位得到进位的结果 3.求前面步骤的结果之和
2108 #但是注意，第三步求和会继续有进位，所以依然需要执行上面三步，直到没有进位
2109 def Add(num1, num2):
2110 # write code here
2111 while num1&num2!=0:
2112 num3 = num1 ^ num2
2113 num4 = (num1 & num2) << 1
2114 num1=num3
2115 num2=num4
2116 return num1^num2
2117 # print(Add(3,4))
2118 # print(ord('3')-ord('0'))#将字符'3'转为数字3 ord表示二进制表示
2119 #字符串正则表达式
2120 def zhengzepipei(s,pattern):
2121 if s==None and pattern==None:
2122 return True
2123 elif s!=None and pattern==None:
2124 return False
2125 elif s==None and pattern!=None:
2126 if len(pattern)>1 and pattern[1]=='*':
2127 return zhengzepipei(s,pattern[2:])#继续向后判断
2128 else:
2129 return False
2130 else:
2131 if s[0]==pattern[0]:#对应位置字符相同的情况与此时pattern为.的情况一致
2132 return zhengzepipei(s[1:],pattern[1:])
2133 elif len(pattern)>1 and pattern[1]=='*':
2134 return zhengzepipei(s,pattern[2:])
2135
2136 #表示数值的字符串
2137 def str2num(string):
2138 if string==None:
2139 return False
2140 hase=False
2141 hasdot=False
2142 hassigh=False
2143 length=len(string)
2144 for i in range(length):
2145 if string[i]=='e' or string[i]=='E':
2146 if hase:
2147 return False
2148 else:
2149 hase=True
2150 if i==length-1:
2151 return False
2152 elif string[i]=='.':
2153 if hase or hasdot:
2154 return False
2155 else:
2156 hasdot=True
2157 elif string[i]=='+' or string[i]=='-':
2158 if i!=0 and string[i-1]!='e' and string[i-1]!='E':# or hase==False 字符串开始是没有e的但是不能返回false
2159 return False
2160 elif string[i]<'0' or string[i]>'9':
2161 return False
2162 return True
2163
2164 # print(str2num('1a3.14'))
2165 #链表中环的入口结点
2166 def EntryNodeOfLoop(pHead):
2167 #初始化的时候就将两个指针分别初始化为走了一步和两步的指针
2168 if pHead == None or pHead.next == None: # 注意判断异常情况，链表为空或者链表中只有一个节点
2169 return None
2170 ##初始化的时候就将两个指针分别初始化为走了一步和两步的指针
2171 first = pHead.next
2172 second = pHead.next.next
2173 while first != second: # 若有环两者才能相遇
2174 if second == None: # 若有一个指针走到None，返回没有环
2175 return None
2176 else:
2177 first = first.next
2178 second = second.next.next
2179 # 相遇后，重新赋值一个指针
2180 first = pHead
2181 while first != second:
2182 first = first.next
2183 second = second.next
2184 return first
2185 class Listnode:
2186 def __init__(self,x):
2187 self.val=x
2188 self.next=None
2189 class solution8:
2190 #删除链表中重复的节点
2191 def deleteDuplication(self,pHead):
2192 node=ListNode(0)#新建一个节点，防止原链表的第一个节点就是重复的
2193 node.next=pHead
2194 pre=node
2195 while node.next:
2196 if node.next.val==node.val:
2197 while node.next.val==node.val:#一直往后判断
2198 node=node.next
2199 pre.next=node.next
2200
2201 node = node.next
2202 else:
2203 pre=node
2204 node=pre.next
2205 return pre.next
2206 # LN1=ListNode(1)
2207 # LN2=ListNode(1)
2208 # LN3=ListNode(1)
2209 # LN4=ListNode(1)
2210 # LN5=ListNode(2)
2211 # LN1.next=LN2
2212 # LN2.next=LN3
2213 # LN3.next=LN4
2214 # LN4.next=LN5
2215 # s=solution8()
2216 # final=s.deleteDuplication(LN1)
2217 # while final:
2218 # print(final.val)
2219 # final=final.next
2220 class TreeNode2:
2221 def __init__(self, x):
2222 self.val = x
2223 self.left = None
2224 self.right = None
2225 class Solution9:
2226 #按之字形顺序打印二叉树
2227 def Print_zhizi(self,pRoot):
2228 sigh = 0
2229 res = [pRoot]
2230 finalres = [[pRoot.val]]
2231 while res:
2232 newres = []
2233 newresval = []
2234 if sigh == 0:
2235 while res:
2236 r = res.pop()
2237 if r.right:
2238 newres.append(r.right)
2239 newresval.append(r.right.val)
2240 if r.left:
2241 newres.append(r.left)
2242 newresval.append(r.left.val)
2243
2244 finalres.append(newresval)
2245 res = newres
2246 sigh = 1
2247 else:
2248 while res:
2249 node = res.pop()
2250 if node.left:
2251 newres.append(node.left)
2252 newresval.append(node.left.val)
2253 if node.right:
2254 newres.append(node.right)
2255 newresval.append(node.right.val)
2256 finalres.append(newresval)
2257 res = newres
2258 sigh = 0
2259 return finalres
2260
2261 # node1=TreeNode2(1)
2262 # node2=TreeNode2(2)
2263 # node3=TreeNode2(3)
2264 # node4=TreeNode2(4)
2265 # node5=TreeNode2(5)
2266 # node7=TreeNode2(7)
2267 # node8=TreeNode2(8)
2268 # node9=TreeNode2(9)
2269 # node10=TreeNode2(10)
2270 # node1.left=node2
2271 # node1.right=node3
2272 # node2.left=node4
2273 # node2.right=node5
2274 # node3.left=node7
2275 # node3.right=node8
2276 # node8.left=node9
2277 # node8.right=node10
2278 # s=Solution9()
2279 # final=s.Print_zhizi(node1)
2280 # print(final)
2281
2282
2283 # a=[1,3]
2284 # a.append([2,4])#不能将append后的结果赋值，否则为None
2285 # print(a)
2286
2287 #列表扩充
2288 # a=[1,2]
2289 # b=[3,4]
2290 # a.extend(b)#不能将扩展后的列表重新赋值，否则会返回None
2291 # # a=a.extend(b)#返回None
2292 # print(a)
2293 # aList = [123, 'xyz', 'zara', 'abc', 123]
2294 # bList = [2009, 'manni']
2295 # aList.extend(bList)
2296 # print(aList)
2297
2298 #滑动窗口的最大值
2299 #方法一：复杂度 O(nk)
2300 def maxInWindows(num, size):
2301 length=len(num)
2302 if size>length:#若窗口比数组大
2303 return None
2304 res=[]
2305 for i in range(length-size+1):
2306 maxnum=max(num[i:(i+size)])
2307 res.append(maxnum)
2308 return res
2309 # print(maxInWindows([2,3,4,2,6,2,5,1],3))
2310 def maxInWindows2(num,size):
2311 res=[]
2312 wind=[num[0]]
2313 for i in range(1,size):
2314 if num[i]>wind[0]:
2315 wind.pop(0)
2316 wind.append(num[i])
2317 head = i
2318 else:
2319 wind.append(num[i])
2320 res.append(wind[0])
2321 # head = size - 1
2322 for i in range(size,len(num)):
2323 if num[i]<wind[0] and i-head<size:
2324 if len(wind)>=2:
2325 if wind[1]<num[i]:#若新来的数字较大，则更换，否则没有操作
2326 wind.pop()
2327 wind.append(num[i])
2328 else:#没有第二个元素，直接加入
2329 wind.append(num[i])
2330 elif num[i]>wind[0] and i-head<size:
2331 wind=[num[i]]
2332 head=i
2333 elif i-head>=size:#注意还有等于
2334 wind.pop(0)
2335 res.append(wind[0])
2336 print(res)
2337 # maxInWindows2([1,3,-1,-3,5,3,6,7],3)
2338 #从矩阵中找到k值（矩阵从左到右递增，从上到下递增）
2339 def findk(array,k):
2340 if array:
2341 row=len(array)-1
2342 col=len(array[0])-1
2343 i=row
2344 j=0
2345 while i>=0 and j<=col:
2346 if array[i][j]==k:
2347 return True
2348 elif array[i][j]<k:
2349 j+=1
2350 else:
2351 i-=1
2352 return False
2353
2354 # print(findk([[1,2,3],[4,6,7],[5,8,9]],7))
2355
2356 def find(a,b):
2357 num=a[0]
2358 final=0
2359 for i in range(1,len(a)):
2360 if a[i]<num:#a[i]若小于前一个数字
2361 final=num
2362 break
2363 num=a[i]#更新num
2364 bef=a[i-2]
2365 after=a[i]
2366 max = bef
2367 for j in range(len(b)):
2368 if b[j]>bef and b[j]<after:
2369 print(b[j])
2370 if b[j]>max:
2371 max=b[j]
2372 if max>bef:
2373 a[i-1]=max
2374 return a
2375 else:
2376 return False
2377 # print(find([1,4.5,3,4,5],[1,2,2.4,3,6]))
2378 # #多行输入
2379 # while True:
2380 # try:
2381 # a,b=map(int,input().split())#将输入的以空格分割的字符串 分割开，转为int
2382 # print(a+b)
2383 # except:
2384 # break
2385 #一直输入
2386 # import sys
2387 # for line in sys.stdin:
2388 # a = line.split()#输入通过空格分割
2389 # print(int(a[0]) + int(a[1]))
2390
2391 # def func():
2392 # inp=input().split()
2393 # lis1=inp.split('@')[0]
2394 # lis2=inp.split('@')[1]
2395 # l1=lis1.split(',')
2396 # l2=lis2.split(",")
2397 # dic=dict()
2398 # for i in l1:
2399 # dic[i.split(":")[0]]=int(i.split(":")[1])
2400 # for j in l2:
2401 # if j.split(':')[0] in dic:
2402 # dic[j.split(':')[0]]-=int(j.split(':')[1])
2403 # for p,q in dic.items():
2404 # if q!=0:
2405 # print("")
2406 #
2407 # def str_to_dir(str_):
2408 # str_list=str_.split(',')
2409 # str_dir={}
2410 # for item in str_list:
2411 # item_list=item.split(':')
2412 # str_dir[item_list[0]]=int(item_list[1])
2413 # return str_dir
2414 #
2415 # def dir_sub_and_print(first_dir,second_dir):
2416 # for key in second_dir:
2417 # first_dir[key]-=second_dir[key]
2418 # result_str=str()#####
2419 # for key in sorted(first_dir):
2420 # if first_dir[key]>0:
2421 # result_str+="{}:{},".format(key,first_dir[key])
2422 # result_str=result_str[:-1]
2423 # print(result_str)
2424 # input_str=input()
2425 # input_list=input_str.split('@')
2426 # dir_sub_and_print(str_to_dir(input_list[0]),str_to_dir(input_list[1]))
2427
2428
2429 # def str_to_dir(str_):
2430 # str_list=str_.split(',')
2431 # str_dir={}
2432 # for item in str_list:
2433 # item_list=item.split(':')
2434 # str_dir[item_list[0]]=int(item_list[1])
2435 # return str_dir
2436 # def dir_sub_and_print(first_dir,second_dir):
2437 # for key in second_dir:
2438 # first_dir[key]-=second_dir[key]
2439 # result_str=str()
2440 # for key in sorted(first_dir):
2441 # if first_dir[key]>0:
2442 # result_str+="{}:{},".format(key,first_dir[key])
2443 # result_str=result_str[:-1]
2444 # print(result_str)
2445 # input_str=input()
2446 # input_list=input_str.split('@')
2447 # dir_sub_and_print(str_to_dir(input_list[0]),str_to_dir(input_list[1]))
2448
2449 #从尾到头打印链表
2450 class lianbiao:
2451 def __init__(self,x):
2452 self.value=x
2453 self.next=None
2454 self.random=None
2455 def code03(node):
2456 lis=[]
2457 while node!=None:
2458 lis.append(node.value)
2459 node=node.next
2460 lis=lis[::-1]
2461 print(lis)
2462 lis=[]
2463 def code03_2(node):
2464
2465 if node:
2466 code03_2(node.next)
2467 lis.append(node.value)
2468 return lis
2469
2470 #输入一个链表，输出该链表中倒数第k个结点
2471 def code14(node,k):
2472 ind1=node
2473 ind2=node
2474 for i in range(k-1):
2475 if node.next:
2476 ind2=ind2.next
2477 else:
2478 return None
2479 print(ind1.value,ind2.value)
2480 while ind2.next:
2481 #为了保证ind2指向最后一个元素的时候不再往后移动.若ind2一直比ind1靠前k个指针，则它指向none的时候ind1可以指向道术第k个元素
2482 ind1=ind1.next
2483 ind2=ind2.next
2484 return ind1.value
2485 #反转链表
2486 def code15(node1):
2487 if node1==None:
2488 return
2489 if node1.next==None:
2490 return node1
2491 n=node1.next
2492 node1.next=None
2493 while n:
2494 n1=n
2495 n=n.next
2496 n1.next=node1
2497 node1=n1
2498 return node1
2499
2500 #比较清晰的解法：#从哪个节点开始反转则初始定位到哪个节点（反转链表主要是注意这点！！！！！！！！！！），
2501 # 后续用三个指针（注意三个指针复制、执行的顺序）通过循环反转。
2502 # else:
2503 # # 因为指针只能从一个节点指向下一个节点，所以从第二个节点开始反转
2504 # node = pHead.next#从哪个节点开始反转则初始定位到哪个节点
2505 # pHead.next = None # 注意加上这个，为头结点赋值next
2506 # while node != None:
2507 # nextnode = node.next # 先记录node节点的下一个节点
2508 # node.next = pHead # 依次反转
2509 # pHead = node
2510 # node = nextnode
2511 # return pHead
2512 #反转链表从m到n位置的节点
2513 def code15_2(pHead,m,n):
2514 node=pHead
2515 befnode=pHead
2516 thrbef=pHead
2517 for i in range(m):
2518 node=node.next#先定位node的位置！！！！！！！！！！
2519 for i in range(m-1):
2520 befnode=befnode.next
2521 bef=befnode
2522 if m>=2:#只有m>2才能计算node的前面第三个节点
2523 for i in range(m-2):
2524 thrbef=thrbef.next
2525 #不论m什么情况，都要进行反转，反转代码一定要写对
2526 for i in range(n-m):
2527 nextnode=node.next
2528 node.next=befnode
2529 befnode=node
2530 node=nextnode
2531 if m>=2:
2532 bef.next = node
2533 thrbef.next = befnode
2534 thrbef = pHead#注意！！！返回的是整体的头指针，上面只是把m到n的部分链表反转成功，而不是返回上面的thrbef
2535 else:
2536 if node!=None:#注意！！若m<2,且n指向的不是链表最后一个节点
2537 pHead.next=node
2538 thrbef=befnode
2539 else:#若m<2,且n指向的是链表最后一个节点
2540 pHead.next=None#注意！！！！！如果是全部反转，原来的头结点指向None
2541 thrbef=befnode
2542 return thrbef
2543 # p = lianbiao(1)
2544 # p.next = lianbiao(2)
2545 # node=code15_2(p,1,2)
2546 # while node:
2547 # print(node.value)
2548 # node=node.next
2549 #合并有序链表(循环版)
2550 def code16(node1,node2):
2551 if node1==None or node2==None:
2552 return
2553 else:
2554 if node1.value<node2.value:
2555 node3=node1
2556 node1 = node1.next
2557 else:
2558 node3=node2
2559 node2 = node2.next
2560 head=node3
2561 # print(node3.value)
2562 while node1 and node2:
2563 if node1.value<=node2.value:
2564 node3.next=node1
2565 node3=node3.next
2566 node1=node1.next
2567 # print(node3.value)
2568 else:
2569 node3.next = node2
2570 node3 = node3.next
2571 node2 = node2.next
2572 # print(node3.value)
2573
2574 if node1:
2575 while node1:
2576 node3.next=node1
2577 node1=node1.next
2578 elif node2:
2579 while node2:
2580 node3.next=node2
2581 node2=node2.next
2582 return head
2583
2584 #合并有序链表(递归版)
2585 def code16_2(pHead1,pHead2):
2586 if pHead1==None:
2587 return pHead2
2588 if pHead2==None:
2589 return pHead1
2590 res=None
2591 if pHead1.value<=pHead2.value:
2592 res=pHead1
2593 res.next=code16_2(pHead1.next,pHead2)
2594 elif pHead2.value>=pHead2.value:
2595 res=pHead2
2596 res.next=code16_2(pHead1,pHead2.next)
2597 return res
2598 #复杂链表的复制
2599
2600 def code25(pHead):
2601 ##刚开始想的是直接遍历一遍，每遇到一个节点就新建node，然后根据原本的节点去指向，但是发现此时并未新建其余节点，无法指向
2602 # node=pHead
2603 # while pHead:
2604 # newnode=lianbiao(pHead.value)
2605 # newnode.next=pHead.next
2606 # newnode.random=pHead.random
2607 # pHead=pHead.next
2608 # return node
2609
2610 #通过了的代码
2611 # dummy = pHead
2612 #
2613 # # first step, N' to N next
2614 # while dummy:
2615 # dummynext = dummy.next
2616 # copynode = lianbiao(dummy.value)
2617 # copynode.next = dummynext
2618 # dummy.next = copynode
2619 # dummy = dummynext
2620 #
2621 #
2622 # dummy = pHead
2623 #
2624 # # second step, random' to random'
2625 # while dummy:
2626 # dummyrandom = dummy.random
2627 # copynode = dummy.next
2628 # if dummyrandom:
2629 # copynode.random = dummyrandom.next
2630 # dummy = copynode.next
2631 #
2632 # # third step, split linked list
2633 # dummy = pHead
2634 # copyHead = pHead.next
2635 # while dummy:
2636 # copyNode = dummy.next
2637 # dummynext = copyNode.next
2638 # dummy.next = dummynext
2639 # if dummynext:
2640 # copyNode.next = dummynext.next
2641 # else:
2642 # copyNode.next = None
2643 # dummy = dummynext
2644 #
2645 # while pHead:
2646 # print(pHead.value)
2647 # pHead = pHead.next
2648 #我自己写的代码
2649 # 复制节点
2650 node = pHead
2651 while node:
2652 newnode = lianbiao(node.value)
2653 newnode.next = node.next
2654 node.next = newnode
2655 node = newnode.next
2656 # #为新复制的节点加上指向的random节点
2657 node=pHead
2658 num=1
2659 while node:
2660 if num%2==1:
2661 if node.random:
2662 rand=node.random.next
2663 else:
2664 rand=None
2665 node=node.next
2666 else:
2667 node.random=rand#.next表示要指向复制的节点
2668
2669 node=node.next
2670 num+=1
2671
2672 #切割开 这个题主要是要注意不能只管复制的链表，还要将原链表还原。
2673 #注意本代码的写法！！！！！
2674 dummy=pHead
2675 copyHead=pHead.next
2676 while dummy:
2677 #在循环内部新建一个复制的节点的头结点，则可以在循环内部更新
2678 copynode=dummy.next#每个循环都更新dummy即可在进入循环后更新copynode
2679 dummynext=copynode.next#此时不需要判断是否为空，因为即使是空也需要指向
2680 dummy.next=dummynext
2681 if dummynext:#此时需要判断他是否为空，如果不为空才能为复制的节点往后进行指向
2682 copynode.next=dummynext.next
2683 else:
2684 copynode.next=None#若为None，复制节点的指向也为None
2685 dummy=dummynext
2686 return dummy
2687 #之前的切割方法,报错返回空
2688 # head=pHead.next
2689 # newhead=pHead.next
2690 # while newhead:
2691 # # print(newhead.value)
2692 # if newhead.next:
2693 # newhead.next=newhead.next.next
2694 # newhead=newhead.next
2695 # else:
2696 # break
2697 # # # while head:
2698 # # # head.next=head.next.next
2699 # # # newhead.next=newhead.next.next
2700 # return head
2701
2702 # p = lianbiao(1)
2703 # p.next = lianbiao(2)
2704 # p.next.next = lianbiao(3)
2705 # p.next.next.next = lianbiao(4)
2706 # p.next.next.next.next = lianbiao(5)
2707 # h=code25(p)
2708 # while h:
2709 # print(h.value)
2710 # h=h.next
2711 #
2712
2713 #
2714 # node5=lianbiao(2)
2715 # node6=lianbiao(4)
2716 # node7=lianbiao(6)
2717 # # node8=lianbiao(9)
2718 # node5.next=node6
2719 # node6.next=node7
2720 # # node7.next=node8
2721 # res=code16_2(node1,node5)
2722 # # res=code15(node1)
2723 # while res:
2724 # print(res.value)
2725 # res=res.next
2726 # print(code14(node1,2))
2727 # l=code03_2(node1)
2728 # print(l)
2729
2730 #字符串排列
2731 def code27(s):
2732 #直接把一轮递归看作把字符串分割为两部分来处理
2733 if len(s)==1:#递归边界条件，只有一个元素时，返回s[0],即不需要排列
2734 return s[0]
2735 res=[]
2736 for i in range(len(s)):#对于s中的每个元素都可以作为开头元素，
2737 # 接下来对其余元素进行递归
2738 l=code27(s[:i]+s[i+1:])
2739 #递归结束后的操作：将递归的结果与本轮开头元素s[i]拼接
2740 for m in l:#遍历上一步排列好的结果集合
2741 res.append(s[i]+m)#s[i]+上一步的结果得到最终的结果集
2742 #得到本轮排序后的列表结果后，将结果return 便于下轮调用
2743 return res
2744 # def code27_3(word):
2745 # if len(word)==1:
2746 # return word[0]
2747 # else:
2748 # res=[]
2749 # for i in word:
2750 # l=code27_3(word[:i]+word[i+1:])
2751 # for m in l:
2752 # res.append(i+m)
2753 # return res
2754 def Permutation(ss):
2755 if not ss:return []
2756 words=list(ss)
2757 return list(sorted(set(code27(words))))
2758 # print(Permutation('abcd'))
2759 # #列表下标超出index不报错，而是返回空！！！！
2760 # s=['a','b','r']
2761 # print(s[3:])
2762 #两个链表的第一个公共结点
2763 def code36(pHead1, pHead2):
2764 #方法一：遍历pHead1对应的链表，吧所有节点都放入列表；再遍历pHead2若遇到列表中有的节点就返回。
2765 # nodelist=[]
2766 # while pHead1:
2767 # nodelist.append(pHead1)
2768 # pHead1=pHead1.next
2769 # while pHead2:
2770 # if pHead2 in nodelist:
2771 # return pHead2
2772 # pHead2=pHead2.next
2773 #return None#刚开始报错！以为这个return写到了while循环里面
2774 #方法二：先得到两个链表的长度差k，然后分别从头节点和走k步为初始节点 往后遍历，直到两者值相同 结束
2775 #注意新建节点指向两个链表的首节点，否则在统计链表长度的时候指针后移到最后，但是却没注意到
2776 p1=pHead1
2777 p2=pHead2
2778 num1=0
2779 num2=0
2780 while p1:
2781 num1+=1
2782 p1=p1.next
2783 while p2:
2784 num2+=1
2785 p2=p2.next
2786 if num1 > num2:
2787 head1 =pHead1
2788 head2=pHead2
2789 else:
2790 head1=pHead2
2791 head2=pHead1
2792
2793 for i in range(abs(num2-num1)):
2794 head1=head1.next
2795 while head1:
2796 if head2==head1:
2797 return head2
2798 else:
2799 head1=head1.next
2800 head2=head2.next
2801 return None
2802 #方法三：将两个链表分别遍历，并分别存储在两个列表中，再对两个列表同时pop元素，在弹出的两个元素不一样的时候就是到了分叉口
2803 #链表中环的入口
2804 def code55(pHead):
2805 #这个题主要是想清楚，找环的入口，设置两个指针怎么走才能让两个指针正好在环入口相遇？从距离角度出发，若知道
2806 #从A点出发到环入口的距离==链表头到环入口的距离 则两个指针分别从A点和链表头出发，一定相遇
2807 if pHead == None or pHead.next == None: # 注意判断异常情况，链表为空或者链表中只有一个节点
2808 return None
2809 # 为什么这么初始化？？？？不可以分别初始化为第一个和第二个节点？因为初始实际上两个指针都是从pHead头结点出发
2810 # 分别走一步和两步就是下面的初始化结果。但是如果初始化为我上面讲的那种，则与题目规律不符，最后无法计算
2811 # 得到环入口
2812 p1 = pHead.next # 初始化慢节点指向第2个节点
2813 p2 = pHead.next.next # 初始化快节点指向第3个节点
2814 while p1 != p2: # 条件为while p1时如果有环，会一直循环，所以条件不能是这个
2815 if p2 == None: # p2先到空，则无环，而不是判断p1,因为p1在前面，先判断p2更合适
2816 return None
2817 p1 = p1.next
2818 p2 = p2.next.next
2819 # 退出循环表示有环，且p1和p2都到了两者相遇地方
2820 p1 = pHead
2821 while p1 != p2:
2822 p1 = p1.next
2823 p2 = p2.next
2824 return p1
2825 #删除该链表中重复的结点
2826 def code56(pHead):
2827 #循环判断
2828 if pHead==None:
2829 return
2830 p1=pHead
2831 while p1:
2832 bef = p1
2833 if p1.next==p1:
2834 while p1.next==p1:
2835 p1=p1.next
2836 p1.next=bef
2837 p1=p1.next
2838 return pHead
2839 # node1=lianbiao(1)
2840 # node2=lianbiao(3)
2841 # node3=lianbiao(3)
2842 # node4=lianbiao(5)
2843 # node5=lianbiao(7)
2844 # node1.next=node2
2845 # node2.next=node3
2846 # node3.next=node4
2847 # node4.next=node5
2848 # final=code56(node1)
2849 # while final:
2850 # print(final.value)
2851 # final=final.next
2852
2853 #斐波那契数列
2854 def code007(n):
2855 if n<=1:
2856 return n
2857 return code007(n-1)+code007(n-2)
2858 # print(code007(3))
2859 def code010(number):
2860 # write code here
2861 # 该问题最终简化后依然是斐波那契数列f(8)=f(7)+f(6)
2862 if number==0:
2863 return 0
2864 elif number==1:
2865 return 1
2866 elif number==2:
2867 return 2
2868 else:
2869 f = [0] * (number+1)
2870 f[0]=0
2871 f[1]=1
2872 f[2]=2
2873 for i in range(3, number + 1):
2874 f[i] = f[i - 1] + f[i - 2]
2875 return f[number]
2876 # print(code010(3))
2877 #旋转数组的最小数字（二分查找） 剑指offer书上记录了思路
2878 def code006(rotateArray):
2879 left=0
2880 right=len(rotateArray)-1
2881 mid=left
2882 while rotateArray[left]>=rotateArray[right]:
2883 mid = int((left + right) / 2)
2884 if right-left==1:
2885 mid=right#为了与特殊情况保持一致，将right赋值给mid 返回mid
2886 break
2887 else:
2888 #如果遇到left,mid,right指向的值都相同的情况，无法判断最小值应该在前面的非递减序列中还是后面的，只能遍历查找
2889 if rotateArray[mid]==rotateArray[left] and rotateArray[mid]==rotateArray[right]:
2890 return bianli()#该函数遍历[left,right]区间内的所有元素，得到最小值
2891 #由于是非递减序列，所以可能有相等值
2892 if rotateArray[mid] >= rotateArray[left]:
2893 left = mid
2894 elif rotateArray[mid] <= rotateArray[right]:
2895 right = mid
2896
2897 return rotateArray[mid]
2898 # print(code006([6501,6828,6963,7036,7422,7674,8146,8468,8704,8717,9170,9359,9719,9895,9896,9913,9962,154,293,334,492,1323,1479,1539,1727,1870,1943,2383,2392,2996,3282,3812,3903,4465,4605,4665,4772,4828,5142,5437,5448,5668,5706,5725,6300,6335]))
2899 # print(code006([5,4,3,2,1]))
2900 #数字在排序数组中出现的次数
2901 def code37(data,k):
2902 left=0
2903 right=len(data)-1
2904 while left<=right:
2905 mid=int((left+right)/2)
2906 if data[mid]==k:
2907 leftmid=mid
2908 rightmid=mid
2909
2910 while leftmid-1>=0 and data[leftmid-1]==k:
2911 leftmid=leftmid-1
2912
2913 while rightmid+1<=len(data)-1 and data[rightmid+1]==k:
2914 rightmid=rightmid+1
2915 return rightmid - leftmid+1
2916 elif data[mid]<k:
2917 left=mid+1
2918 elif data[mid]>k:
2919 right=mid-1
2920 return 0
2921
2922 # print(code37([1,1,2,3,4,4,4],4))#特殊情况1：没有要找的元素 2.[3,3,3]找3 3.([1,1,2,3,4,4,4],4)
2923 #030-连续子数组的最大和
2924 def code30(array):
2925 sum=0
2926 finalsum=sum
2927 for i in range(len(array)):
2928 if sum>=0:
2929 sum=sum+array[i]
2930 # 注意！！！每次求和时，虽然没有求和为小于0的结果，但是可能会比上一步的求和结果小，所以要每步更新
2931 else:#若加上下一个元素小于0，则上一步得到的sum记录下来，作为finalsum
2932 sum=array[i]
2933 if finalsum<sum:
2934 finalsum=sum
2935 #！！！之前每次更新finalsum都是在遇到求和小于0的情况更新的，若最后没有遇到小于0的也要比较一下
2936 return finalsum
2937 #找到规律后 写出公式（动态规划法）
2938 def code30_2(array):
2939 f=[0]*len(array)
2940 f[0]=array[0]
2941 for i in range(1,len(array)):
2942 if f[i-1]<0:
2943 f[i]=array[i]
2944 else:
2945 f[i]=f[i-1]+array[i]
2946 return f[len(array)-1]
2947 # print(code30_2([-2,-8,-1,-5,-9]))
2948 def code30_3(array):
2949 maxsum=array[0]
2950 sum=0
2951 for i in range(len(array)):
2952 #sum的更新方式如下：
2953 if sum<0:#判断如果当前求和结果小于0，则sum更新为array[i]
2954 sum=array[i]
2955 else:#否则 更新sum继续往后加
2956 sum=sum+array[i]
2957 #不论sum的更新方式是什么，都要用下面方式更新最大值
2958 if maxsum<sum:
2959 maxsum=sum
2960 # print(code30([-2,-8,-1,-5,-9]))#特殊用例[-2,-8,-1,-5,-9]
2961 #正则表达式匹配
2962 def code52(s, pattern):
2963 #先写结束递归的条件
2964 if len(s)!=0 and len(pattern)==0:
2965 return False
2966 if len(s)==0 and len(pattern)==0:
2967 return True
2968 if len(s)==0 and len(pattern)>0:
2969 if len(pattern)>1 and pattern[1]=='*':
2970 return code52(s,pattern[2:])
2971 else:
2972 return False
2973 else:
2974 #下面是递归内容
2975 #首先判断此时的第二个字符为*的情况如何处理
2976 if len(pattern)>1 and pattern[1]=='*':#不需要判断len(s)>1，一旦长度不大于1，s[1:]为空，不报错
2977 if s[0]!=pattern[0] and pattern[0]!='.':#注意此时还要判断pattern[0]是不是'.'
2978 return code52(s,pattern[2:])
2979 else:#不满足上述情况的都通过下面的函数操作
2980 return code52(s[1:],pattern[2:]) or code52(s,pattern[2:]) or code52(s[1:],pattern)
2981 #然后判断第二个字符不是* 的情况
2982 else:
2983 # 由于后面可能含有*，所以先判断有*的情况，这部分放在else块
2984 if s[0]==pattern[0] or pattern[0]=='.':
2985 # if len(s)>1 and len(pattern)>1:#！！！！！！不需要判断长度是否大于1，因为即使不大于1，也不会报错
2986 return code52(s[1:],pattern[1:])
2987 # else:
2988 # return True
2989 else:
2990 return False
2991
2992 # print(code52("a",".*"))
2993 #数组中逆序对数
2994 #直接用归并排序的代码，只是需要统计逆序对个数；另外函数的返回也不一样，之前返回的是数组，现在返回的是统计的个数
2995 def InversePairs2(data):
2996 # write code here
2997 temp = data[:]
2998 s = 0
2999 end = len(data) - 1
3000 count = merge_sort2(data, temp, s, end)
3001 return count
3002
3003 def merge_sort2(data, temp, s, end):
3004 # temp = [None for i in range(len(data))]##注意这里不定义
3005 rever=0
3006 if s < end:#没有=，否则会一直递归，因为有=号的时候mid会一直不变
3007 mid = int((s + end) / 2)
3008 #把所有返回的统计的逆序对数的结果加上去
3009 rever+=merge_sort2(data, temp, s, mid)
3010 rever+=merge_sort2(data, temp, mid + 1, end)
3011 rever += merge2(data, temp, s, mid, end)
3012 return rever#注意返回的是逆序对数
3013
3014 def merge2(data, temp, s, mid, end):
3015 t = s#注意t的开始位置是s而不是0，这样j-t得到的结果才是逆序对个数
3016 i = s
3017 j = mid + 1
3018 rever = 0
3019 while i <= mid and j <= end:
3020 if data[i] <= data[j]:
3021 temp[t] = data[i]
3022 i += 1
3023 else:
3024 rever += (j - t) # 由于此时两个小数组已经是排好序的，所以一旦调换位置，从t到j都是逆序的
3025 temp[t] = data[j]
3026 j += 1
3027 t += 1
3028 while i <= mid:#注意不要落下等于号！！！1
3029 temp[t] = data[i]
3030 i += 1
3031 t += 1
3032 while j <= end:#注意！！！！
3033 temp[t] = data[j]
3034 j += 1
3035 t += 1
3036 #注意t赋的初值(归并排序的初值t=0)，以及for循环的起止条件
3037 t =s
3038 for i in range(s, end + 1):
3039 data[i] = temp[t]
3040 t += 1
3041 return rever
3042
3043 # print(InversePairs2([1,2,0]))
3044
3045 def quiksort(data, low, high):
3046 if low < high:
3047 key = choose(data, low, high)
3048 quiksort(data, low, key)
3049 quiksort(data, key + 1, high)
3050 return data
3051
3052 def choose(data, low, high):
3053 keyvalue = data[low]
3054 while low < high:
3055 while low < high and data[high] >=keyvalue:
3056 high -= 1 # 注意要初始化一个存储计算结果的变量，不能直接对base进行叠乘，因为直接叠乘会改变base的大小
3057 temp = data[low]
3058 data[low] = data[high]
3059 data[high] = temp
3060 while low < high and data[low] <= keyvalue:
3061 low += 1
3062 temp = data[low]
3063 data[low] = data[high]
3064 data[high] = temp
3065 return low
3066
3067 # data=[2,3,1,4,6,4,3,20]
3068 # print(quiksort(data,0,len(data)-1))
3069
3070 '''
3071 #360；两道编程题
3072
3073 #一：求面积
3074 import sys
3075 def area(mat):
3076 n=len(mat)
3077 m=len(mat[0])
3078 result=0
3079 for i in range(n):
3080 for j in range(m):
3081 if mat[i][j]:
3082 result+=2
3083 for p,q in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
3084 if 0<=p<n and 0<=q<m:
3085 value=mat[p][q]
3086 else:
3087 value=0
3088 result+=max(mat[i][j]-value,0)
3089 return result
3090 if __name__=='__main__':
3091 line=sys.stdin.readline().strip().split(' ')
3092 data=list(map(int,line))
3093 n,m=data[0],data[1]
3094 mat=[]
3095 for i in range(n):
3096 line=list(map(int,sys.stdin.readline().strip().split(' ')))
3097 mat.append(line)
3098 result=area(mat)
3099 print(result)
3100 #二题，过了18%
3101 import sys
3102 def func(n1,n2,m,n):
3103 dp=[[0 for p in range(n)] for q in range(n)]#--
3104 res=[]
3105 temp=set()
3106 for i in range(n):
3107 for j in range(n):
3108 dp[i][j]=(n1[i]+n2[j])%m
3109 for i in range(n):
3110 maxnum=0
3111 t=0
3112 for j in range(n):
3113 if j not in temp and dp[i][j]>maxnum:
3114 maxnum=dp[i][j]
3115 t=j
3116 temp.add(t)
3117 res.append(maxnum)
3118 res.sort()
3119 res=res[::-1]
3120 return res
3121
3122 if __name__=='__main__':
3123 inpu=str(input()).split(' ')
3124 m,n=int(inpu[0]),int(inpu[1])
3125 a=list(map(int,sys.stdin.readline().strip().split()))
3126 b=list(map(int,sys.stdin.readline().strip().split()))
3127 result=func(a,b,m,n)
3128 result=' '.join(list(map(str,result)))
3129 print(result)
3130
3131 '''
3132
3133 #斐波那契数列
3134 #递归
3135 def fib1(n):
3136 if n<=1:
3137 return n
3138 else:
3139 return fib1(n-1)+fib1(n-2)
3140 #数组存储
3141 def fib2(n):
3142 f=[0]*(n+1)
3143 f[0]=0
3144 f[1]=1
3145 if n>1:
3146 for i in range(2,n+1):
3147 f[i]=f[i-1]+f[i-2]
3148 return f[n]
3149 #矩阵乘法
3150 def mul(a, b): # 首先定义二阶矩阵乘法运算
3151 c = [[0, 0], [0, 0]] # 定义一个空的二阶矩阵，存储结果
3152 for i in range(2): #row
3153 for j in range(2): # col
3154 for k in range(2): # 新二阶矩阵的值计算
3155 c[i][j] += a[i][k] * b[k][j]
3156 return c
3157 def F5(n):
3158 if n <= 1:
3159 return max(n, 0)
3160 res = [[1, 0], [0, 1]] # 单位矩阵，等价于1
3161 A = [[1, 1], [1, 0]] # A矩阵
3162 while n:
3163 if n & 1: res = mul(res, A) # 如果n是奇数，或者直到n=1停止条件
3164 A = mul(A, A) # 快速幂
3165 n >>= 1 # 整除2，向下取整
3166 return res[0][1]
3167 #矩阵相乘
3168 def multi(a,b):
3169 c=[[0 for i in range(len(a))] for j in range(len(b[0]))]
3170 for i in range(len(a)):
3171 for j in range(len(b[0])):
3172 for k in range(len(a[0])):
3173 c[i][j]+=a[i][k]*b[k][j]
3174 return c
3175
3176 # print(multi([[0,1],[0,1]],[[0,1],[0,1]]))
3177 #定义矩阵A的n次方
3178 def powerofmat(A,n):
3179 A=[[1,1],[1,0]]
3180 if n==0:
3181 return 1
3182 elif n==1:
3183 return A
3184 else:
3185 if n%2==0:
3186 return multi(powerofmat(A,n//2),powerofmat(A,n//2))
3187 else:
3188 return multi(multi(powerofmat(A,n//2),powerofmat(A,n//2)),A)
3189
3190
3191 #最长公共子序列
3192 #解析 https://blog.csdn.net/someone_and_anyone/article/details/81044153
3193 # 代码 https://blog.csdn.net/weixin_42018258/article/details/80670067
3194 def max_sub_sequence(a,b):
3195 cols=len(a)+1
3196 rows=len(b)+1
3197 c=[[['',0] for i in range(cols)] for j in range(rows)]
3198 for i in range(1,cols):
3199 c[0][i][0]=a[i-1]#因为c的第i个元素对应a的第i-1个元素 同理b
3200 for j in range(1,rows):
3201 c[j][0][0]=b[j-1]
3202 #填表
3203 for i in range(1,rows):
3204 for j in range(1,cols):
3205 if b[i-1]==a[j-1]:#c的第i个元素对应a的第i-1个元素
3206 c[i][j]=['==',c[i-1][j-1][1]+1]#
3207 else:
3208 if c[i-1][j][1]>c[i][j-1][1]:
3209 c[i][j]=['|',c[i-1][j][1]]
3210 else:
3211 c[i][j]=['-',c[i][j-1][1]]
3212 #倒推子序列
3213 i=rows-1#注意！！！！此时用到的i,j大小
3214 j=cols-1
3215 lis=[]
3216 while i >0 and j>0:
3217 if c[i][j][0]=='==':
3218 lis.append(c[i][0][0])
3219 i-=1
3220 j-=1
3221 elif c[i][j][0]=='|':
3222 i-=1
3223 else:
3224 j-=1
3225 lis=lis[::-1]
3226 print(''.join(lis))
3227
3228 # max_sub_sequence(['A','B','C','B','D','A','B'],['B','B','C','A','B','A'])
3229 '''
3230 if __name__=="__main__":
3231 inp=input()
3232 lis=inp.split(" ")
3233 strlist=[]
3234 for i in lis:
3235 if i !="":
3236 strlist.append(i)
3237 strlist=strlist[::-1]
3238 print(" ".join(strlist))
3239
3240 import sys
3241 def res(data):
3242 if not data:
3243 return None
3244 res=data[::-1]
3245 res=" ".join(res)
3246 return res
3247 if __name__=='__main__':
3248 line=input()
3249 line=' '.join(line.split())
3250 data=line.split(' ')
3251 res1=res(data)
3252 print(res1)
3253
3254 '''
3255 '''
3256 #LeetCode抢劫银行
3257 import sys
3258 def money_max(number,lists):
3259 temp={}
3260 if number==1:
3261 return lists[0]
3262 if number==2:
3263 return lists.max()
3264 else:
3265 temp[0]=lists[0]
3266 temp[1]=max(lists[0],lists[1])
3267 count=1
3268 for i in range(2,number):
3269 if temp[i-2]+lists[i]>temp[i-1]:
3270 count+=1
3271 temp[i]=max(temp[i-1],temp[i-2]+lists[i])
3272 res=[temp[number-1],count]
3273 return res
3274 if __name__=='__main__':
3275 number=int(input())
3276 lists=sys.stdin.readline().strip().split('')
3277 lists=[int(s) for s in lists]
3278 res=money_max(number,lists)
3279 # for i in res:
3280 # print(i,end=' ')
3281 print(res[0])
3282 print(res[1])
3283 '''
3284 '''
3285 #快手
3286 #第一题 最长非重复子串
3287 def maxlen(string):
3288 if not string:
3289 return 0
3290 length = len(string)
3291 flag=0
3292 s=set()
3293 max_len=0
3294 cur=0
3295 for i in range(length):
3296 cur+=1
3297 while string[i] in s:
3298 s.remove(string[flag])
3299 flag+=1
3300 cur-=1
3301 max_len=max(max_len,cur)
3302 s.add(string[i])
3303 return max_len
3304 if __name__=='__main__':
3305 string=input().strip()
3306 result=maxlen(string)
3307 print(result)
3308 #第二题 求解方程
3309 def fangcheng(input):
3310 variable = 'X'
3311 res=input.replace("=","-(")+")"
3312 result = eval(res, {variable: 1j})
3313 return int(-result.real/result.imag)
3314
3315 if __name__=='__main__':
3316 line=str(input())
3317 print(fangcheng(line))
3318
3319 #第三题
3320 if __name__=='__main__':
3321 n = int(input().strip())
3322 m = int(input().strip())
3323 inp = []
3324 for _ in range(m):
3325 inp.append(input())
3326 v = []
3327 p = []
3328 cnt = 0
3329 for i, x in enumerate(inp):
3330 if x[0] == 'V':
3331 v.append((x, i))
3332 else: # P
3333 if cnt == 0:
3334 cnt += 1
3335 v.append((x, i))
3336 continue
3337 p.append((x, i))
3338 f = 0
3339 for i in range(len(v)):
3340 if v[i][0][0] == 'P':
3341 f = i
3342 res = v[0:f+1]
3343 v = v[f+1:]
3344 idx = 0
3345 i = 0
3346 while i < len(v):
3347 begin = i
3348 for j in range(n-1):
3349 if i < len(v):
3350 res.append(v[i])
3351 i += 1
3352 if i-begin>=n-1 and p[idx][1] < res[-1][1]:
3353 res.append(p[idx])
3354 idx += 1
3355
3356 print(len(res))
3357 for s in res:
3358 print(s[0])
3359 '''
3360 '''
3361 #字节跳动笔试：四道编程
3362
3363 #第一题
3364 import sys
3365 def comp(input,lis,num,dp):
3366 for i in range(input):
3367 if i!=num and dp[i] and lis[num][i]>=3:
3368 dp[i]=False
3369 comp(input,lis,i,dp)
3370 if __name__=='__main__':
3371 input=int(sys.stdin.readline().strip())
3372 lis=[]
3373 for i in range(input):
3374 lis.append(list(map(int,sys.stdin.readline().strip().split(" "))))
3375 dp=[True]*input
3376 flag = 0
3377 for i in range(input):
3378 if dp[i]:
3379 dp[i] = False
3380 flag+=1
3381 comp(input,lis,i,dp)
3382 print(flag)
3383
3384 #第二题 圆上面取n个点，连线，不相交，共几条线
3385 if __name__=='__main__':
3386 arr=[0]*32768
3387 arr[0]=arr[1]=1
3388 arr[2]=2
3389 n=int(input())
3390 n=int(n/2)
3391 for i in range(3,n+1):
3392 for j in range(i):
3393 arr[i]+=arr[j]*arr[i-j-1]
3394 arr[i]%=1000000007
3395 print(arr[n])
3396
3397 #第三题 选择向上、下、左右移动后的矩阵结果
3398 import sys
3399 def up():
3400 for i in range(4):
3401 for j in range(3):
3402 for k in range(j+1,4):
3403 if lis[k][i]!=0:
3404 if lis[j][i]==0:
3405 lis[j][i]=lis[k][i]
3406 lis[k][i] = 0
3407 elif lis[j][i]==lis[k][i]:
3408 lis[j][i]=2*lis[j][i]
3409 lis[k][i]=0
3410 break
3411 else:
3412 break
3413 def down():
3414 for i in range(4):
3415 for j in range(3,0,-1):
3416 for k in range(j-1,-1,-1):
3417 if lis[k][i]!=0:
3418 if lis[j][i]==0:
3419 lis[j][i]=lis[k][i]
3420 lis[k][i]=0
3421 elif lis[j][i]==lis[k][i]:
3422 lis[j][i]=2*lis[j][i]
3423 lis[k][i]=0
3424 break
3425 else:
3426 break
3427 def left():
3428 for i in range(4):
3429 for j in range(3):
3430 for k in range(j+1,4):
3431 if lis[i][k]!=0:
3432 if lis[i][j]==0:
3433 lis[i][j]=lis[i][k]
3434 lis[i][k]=0
3435 elif lis[i][j]==lis[i][k]:
3436 lis[i][j]=2*lis[i][j]
3437 lis[i][k]=0
3438 break
3439 else:
3440 break
3441 def right():
3442 for i in range(4):
3443 for j in range(3,0,-1):
3444 for k in range(j-1,-1,-1):
3445 if lis[i][k]!=0:
3446 if lis[i][j]==0:
3447 lis[i][j]=lis[i][k]
3448 lis[i][k]=0
3449
3450 elif lis[i][j] == lis[i][k]:
3451 lis[i][j] = 2 * lis[i][j]
3452 lis[i][k] = 0
3453 break
3454 else:
3455 break
3456
3457
3458 key=int(input())
3459 lis = []
3460 for i in range(4):
3461 lis.append(list(map(int, sys.stdin.readline().strip().split(" "))))
3462 if key==1:
3463 up()
3464 elif key==2:
3465 down()
3466 elif key==3:
3467 left()
3468 elif key==4:
3469 right()
3470 for i in lis:
3471 print(str(i[0])+' '+str(i[1])+' '+str(i[2])+' '+str(i[3]))
3472 '''
3473 #浦发8.26机试题
3474 #判断输入的数组是不是升序数组或者降序数组
3475 #思路:
3476 #升序： 对给定的数组排序，判断排序后的数组与原数组是否相同，相同则返回y
3477 # 降序同理
3478 def sortjudge():
3479 a=[1, 2, 3, 3, 4]
3480 b=sorted(a)
3481 print(b)
3482 if a==b:
3483 print('y')
3484 else:
3485 print('n')
3486 #输入一个字符串数组，判断某个字符串在这个数组中有几个
3487 def countstr():
3488 arr=['abc','Aaa','aaa']
3489 # print(arr[1].upper()) upper可以将字符串中所有字符转为大写，lower转为小写
3490 item='aaa'
3491 count=0
3492 for i in arr:
3493 if item==i:
3494 count+=1
3495 print(count)
3496 # countstr()
3497 '''
3498 #循环 读入多组数据
3499 import sys
3500 try:
3501 while True:
3502 line=sys.stdin.readline().strip()#strip()去掉最后的换行符
3503 if not line:#输入空格时循环结束
3504 break
3505 print(line)
3506 except:
3507 pass
3508 '''
3509 # #字符串查找操作
3510 # s='The past is gone and static'
3511 # print(s.find('past'))
3512
3513 # 一大段字符串，单词以空格隔开，统计每一个单词的词频（哈希）
3514 def countfreq(string):
3515 dic={}
3516 for s in string:
3517 if s not in dic:#直接判断元素是否在字典中即可
3518 dic[s]=1
3519 else:
3520 dic[s]+=1
3521 print(dic)
3522 for key,v in dic.items():
3523 print(v)#输出字典的value
3524 for i in dic:
3525 print(i)#输出字典的key
3526 # countfreq(['ss','ss','e'])
3527
3528
3529 #滴滴
3530 #第一题算式转移
3531 '''
3532 import re
3533
3534 if __name__=='__main__':
3535 n=int(input())
3536 compute=input()
3537 comp=['+','-','*','/']
3538
3539 strip_chars = '+-*/' # .?？;+_:-@%="
3540 ss = compute.translate(str.maketrans(dict.fromkeys(strip_chars, '*')))
3541 # res=re.split("+-*/",compute)
3542 res=ss.split('*')
3543 print(res)
3544 # print(compute)
3545 dic=[]
3546 for c in compute:
3547 if c in comp:
3548 dic.append(c)
3549 print(dic)
3550 finalstring=''
3551 i=0
3552 while i<len(dic)-1:
3553 if dic[i]==dic[i-1]:
3554 sortnum=[]
3555 while dic[i]==dic[i-1]:
3556 sortnum.append(res[i])
3557 i+=1
3558 sortnum=sorted(sortnum)
3559 print(sortnum)
3560 for s in sortnum:
3561 finalstring=finalstring+s+dic[i-1]
3562 else:
3563
3564 finalstring=finalstring+res[i]+dic[i]
3565 i += 1
3566 finalstring=finalstring+res[-1]
3567 print(finalstring)
3568 '''
3569
3570 #冒泡排序
3571 def maopao(arr):
3572 size=len(arr)
3573 for i in range(size):#从第i个元素开始，后面的元素依次与这个元素比较大小，若后面的元素较大，则互换位置
3574 for j in range(i+1,size):
3575 if arr[j]<arr[i]:
3576 temp=arr[i]
3577 arr[i]=arr[j]
3578 arr[j]=temp
3579 print(arr)
3580 # maopao([1,3,2,9,3,5])
3581 #选择排序：如果从小到大排序，则从最小的元素开始找到，依次递增。每次找到的都是剩余元素中最小的元素
3582 #对尚未完成排序的所有元素，从头到尾比一遍，记录下最小的那个元素的下标，也就是
3583 #该元素的位置。再把该元素交换到当前遍历的最前面。其效率之处在于，每一轮中比较了很多次，但只
3584 #交换一次。
3585
3586 def xuanze(arr):
3587 for i in range(len(arr)):
3588 minid=i#记录最小值对应的id
3589 for j in range(i+1,len(arr)):
3590 if arr[j]<arr[minid]:
3591 minid=j
3592 temp=arr[i]
3593 arr[i]=arr[minid]
3594 arr[minid]=temp
3595 print(arr)
3596 # xuanze([1,3,2,9,3,5])
3597 #直接插入排序
3598 def zhijieinsert(arr):
3599 for i in range(1,len(arr)):
3600 temp=arr[i]
3601 j=i-1
3602 while j>=0 and arr[j]>temp:
3603 arr[j+1]=arr[j]
3604 j-=1
3605 arr[j+1]=temp
3606 #浦发银行机试
3607 #1.已知1,2,3,4 四个数字，计算任意3个数字组成的不重复的数字个数，分别是什么
3608 #2.输入一个字符串，输出该字符串中x第二次出现的位置（位置从1开始计数）
3609 #3.k的范围为[2,9],输入一个数字c，若能被k整除，则输出能整除的k有哪些（空格分割）。若没有一个k能整除c,则输出’none',输入-1时结束
3610 #1题
3611 def allsort(s):
3612 if len(s)==1:
3613 return s[0]
3614 else:
3615 res=[]
3616 for i in range(len(s)):
3617 l=allsort(s[:i]+s[i+1:])
3618 for m in l:
3619 res.append(s[i]+m)
3620 return res
3621 #另外输入是字符型，而不是数字，否则在函数体中迭代会报错，因为传入是数字无法迭代
3622 #不记得这个地方我写了几种情况，一定不要少写一种啊啊啊啊啊啊啊
3623 # res1=allsort(['1','2','3'])
3624 # res2=allsort(['1','2','4'])
3625 # res3=allsort(['3','2','4'])
3626 # res4=allsort(['3','1','4'])
3627 # final1=res1+res2+res3
3628 # print(len(res1)+len(res2)+len(res3)+len(res4))
3629 def allsort_2():
3630 res=['1','2','3','4']
3631 ressult=[]
3632 sum=0
3633 for i in range(len(res)):
3634 for j in range(len(res)):
3635 for k in range(len(res)):
3636 if res[i]!=res[j] and res[i]!=res[k] and res[j]!=res[k]:
3637 ressult.append(res[i]+res[j]+res[k])
3638 sum+=1
3639 final2=ressult
3640 print(sum)
3641 return final2
3642 #2题
3643 def countx():
3644 line=input()
3645 ind=0
3646 count=0
3647 for i in line:
3648 ind+=1
3649 if i=='x':
3650 count+=1
3651 #注意这里是count==2的时候输出下标，我昨天做的时候貌似忘记判断了啊啊啊啊啊~~
3652 if count==2:
3653 print(ind)
3654
3655 #循环结束依然没有统计到第二个x，则输出0.需要判断！！！！！！！！！！
3656 if ind==len(line):
3657 print(0)
3658 # countx()
3659 #3题
3660 def judge():
3661 while True:
3662 c=int(input())
3663 if c==-1:
3664 break
3665 else:
3666 res=[]
3667 for i in range(2,9+1):
3668 if c%i==0:
3669 res.append(i)
3670 if len(res)==0:
3671 print('none')
3672 else:
3673 print(res)
3674 # judge()
3675 #股票最大利润
3676 def maxprice(arr):
3677 max=0
3678 # maxp=0
3679 for i in range(len(arr)):
3680 for j in range(i+1,len(arr)):
3681 if arr[j]-arr[i]>max:
3682 max=arr[j]-arr[i]
3683 # maxp=j#记录此时卖出价格
3684
3685 print(max)
3686 # maxprice([9, 11, 8, 5, 7, 12, 16, 14])
3687 #找出数组中重复的数字(给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1的范围内。
3688 #数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字
3689 #方法一
3690 def findmulti(arr):
3691 n=len(arr)
3692 count=[0]*n#由于数字在0-n-1范围内，用count的下标表示给定的数字
3693 ind=0
3694 res=[]
3695 for a in arr:
3696 #只要遇到不在给定范围内的数字，则返回-1
3697 if a<0 or a>n-1:
3698 return -1
3699 ind+=1
3700 count[a]+=1
3701 if count[a]==2:
3702 res.append(a)
3703 if len(res)>0:
3704 return res[0]
3705 #遍历结束且没找到重复的数字
3706 if len(res)==0 and ind==n:
3707 return -1
3708 #方法二
3709 #不开辟新数组，直接在原数组上判断各下标对应的值是否与下标一致 没有看懂
3710 #https://www.acwing.com/solution/acwing/content/707/
3711
3712 #不修改数组找出重复的数字 空间复杂度为o(1)
3713 #给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1
3714 #请找出数组中任意一个重复的数，但不能修改输入的数组。
3715 def findmulti_not(arr):
3716 #https://www.acwing.com/solution/acwing/content/693/
3717 #思想：抽屉思想：n+1个苹果放n个抽屉，则一定有一个抽屉要放两个苹果
3718 #二分法： 将1~n的数字依次划分为两个部分，每部分统计数字个数，再多个数多的那部分范围继续二分，再次统计，直到找到重复的那个数字
3719 #二分主要是改动查找的边界
3720 #数值范围是从1~len(arr)-1
3721
3722 #对n+1个数字中的1~n进行二分查找，初始化如下：
3723 left = 1
3724 right = len(arr) - 1
3725 #循环条件：
3726 while left < right:
3727 mid = left+(right-left) // 2#取中位数，为了防止溢出，一般不用(right+left)//2计算
3728 #统计给定数组中在[left,mid]和[mid+1,right]之间的数字各有多少
3729 count = 0
3730 for i in range(len(arr)):
3731 if arr[i] >= left and arr[i] <= mid: # 统计arr中有多少个数字在[left,mid]之间
3732 count += 1
3733 #哪个区间数字更多，说明重复的那个数字在这个区间，left和right边界更新
3734 if count > (right - left + 1 - count):
3735 right = mid
3736 else:
3737 left = mid + 1
3738 return left
3739
3740 # print(findmulti_not([2, 3, 5, 4, 3, 2, 6, 7]))
3741
3742 '''
3743 #顺丰第二题最长特殊子序列 63%
3744 import sys
3745 def count(nums,number):
3746 if len(nums) != number:
3747 return 0
3748 if number == 1:
3749 return nums
3750 if nums==[]:
3751 return 0
3752 N = len(nums)
3753 Dp = [1]*N
3754 for i in range(N-1):
3755 for j in range(0,i+1):
3756 if nums[i+1]>=nums[j]:
3757 Dp[i+1] = max(Dp[i+1],Dp[j]+1)
3758 return max(Dp)
3759 if __name__ == '__main__':
3760 number = int(input())
3761 nums = [int(x) for x in input().split()]
3762 res = lengthOfLIS(nums,number)
3763 print(res)
3764 '''
3765 import sys
3766 #二维数组中的查找
3767 def numfind(arr,t):
3768 i=len(arr)-1
3769 j=0
3770 while i>=0 and j<len(arr[0]):
3771 if arr[i][j]==t:
3772 return 'true'
3773 elif arr[i][j]<t:
3774 j+=1
3775 else:
3776 i-=1
3777 return 'false'
3778 # array=list(map(int,sys.stdin.readline().strip()))
3779 # arr=[[1,2,8,9], [2,4,9,12], [4,7,10,13],[6,8,11,15]]
3780 # print(numfind(arr,5))
3781 #acwing.com练习
3782 #从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
3783 def finddouble(s):
3784 #特殊情况
3785 if s=='':
3786 return 0
3787 res=[]
3788 for i in range(len(s)):#从第一个字符开始遍历判断后面的子串是否有重复字符
3789 midd=[s[i]]
3790 for j in range(i+1,len(s)):#判断第i个字符后面的字符是否与前面的字符有重复
3791 if s[j] in midd:#有重复的break
3792 break
3793 else:
3794 midd.append(s[j])
3795 res.append(''.join(midd))#字符列表转为字符串
3796 #判断最大长度
3797 maxlen=0
3798 for r in res:
3799 if len(r)>maxlen:
3800 maxlen=len(r)
3801 print(maxlen)
3802 # finddouble("abcabc")
3803 # def finddouble_2(s):
3804 # size=len(s)
3805 # f=[1]*size
3806 # res=[s[0]]
3807 # for i in range(1,size):
3808 # if s[i] not in res:
3809 # f[i]=f[i-1]+1
3810 # elif s[i] in res:
3811 # d=i-res.index(s[i])
3812 # if d<f[res[i]]:
3813 # f[i]=d
3814 # else:
3815 # f[i]=
3816
3817 #把字符串中的空格替换成%20
3818 def replace(s):
3819 count=0
3820 for i in s:
3821 if i==' ':
3822 count+=1
3823 news=list(' '*(len(s)+2*count))#新字符串
3824 j=len(news)-1
3825 for i in range(len(s)-1,-1,-1):
3826 if s[i]==' ':
3827 news[j]='0'
3828 news[j-1]='2'
3829 news[j-2]='%'
3830 j=j-3
3831 else:
3832 news[j]=s[i]
3833 j-=1
3834 print(''.join(news))
3835 # replace('jk ')
3836 '''
3837 #新浪微博笔试题 群里LeetCode类型题
3838 def func(A):
3839 A=list(map(int,A.strip().split(',')))
3840 res=flag=0
3841 for i in sorted(A):
3842 res+=max(flag-i,0)
3843 flag=max(flag+1,i+1)
3844 return res
3845 if __name__=="__main__":
3846 inp=input()
3847 res=func(inp)
3848 print(res)
3849 '''
3850 #全排列
3851 #若字符中有重复的，则需要去重set
3852 def func(s):
3853 if len(s)==1:
3854 return s[0]
3855 else:
3856 res=[]
3857 for i in range(len(s)):
3858 l=func(s[:i]+s[i+1:])
3859 for m in l:
3860 res.append(s[i]+m)
3861 return res
3862
3863
3864 #输出字符串中第一次出现的字符所在位置，如果不存在，返回-1
3865 #只需要一个数组即可实现
3866 def firstappear(s):
3867 #a~z对应的ASCII妈是97-122 A~Z对应65-90
3868 #由于只会出现字母，而字母对应的ASCII吗最大为122 所以初始化一个长度为130的数组 ascci吗作为数组下标进行统计，则只需要一个数组即可
3869 arr=[0]*130
3870 for i in s:
3871 arr[ord(i)]+=1#chr()将ASCII吗转为字符
3872 for i in s:
3873 if arr[ord(i)]==1:
3874 return i
3875 return -1
3876 #需要一个字典 比上面的耗费空间更大
3877 def firstappear_2(s):
3878 dic={}
3879 for i in s:
3880 if i not in dic:
3881 dic[i]=1
3882 else:
3883 dic[i]+=1
3884 print(dic)
3885 for i in s:
3886 if dic[i]==1:
3887 return s.index(i)
3888 return -1
3889 #左旋转字符串
3890 def rotatestring(s,n):
3891 s1=s[n:]
3892 s2=s1+s[:n]
3893 print(s2)
3894 # rotatestring('abcXYZdef',3)
3895
3896 #翻转单词顺序列
3897 def reversewords(s):
3898 s=s[::-1]
3899 news=s.split()
3900 res=[]
3901 for i in news:
3902 res.append(i[::-1])
3903 return ' '.join(res)
3904 # print(reversewords('student. a am I'))
3905 #acwing 87 把字符串转换成整数
3906 #a.replace(' ', '')#将字符串中 的所有空格去掉
3907 import math
3908 def compute(str):#注意这个函数只是计算不包含正负号的结果，所以不会有负数，就不能在这里判断是否小于最小的负数等结果！
3909 num=0
3910 for i in str:
3911 num=num*10+(ord(i)-ord('0'))
3912 return num
3913
3914 def strtoint(str):
3915 if str == '':
3916 return 0
3917 num = list('0123456789')
3918 str = str.replace(' ', '')
3919 flagfuhao = 0
3920 for i in range(len(str)):
3921 if i == 0:
3922 if str[i] == '+':
3923 flagfuhao = 1
3924 elif str[i] == '-':
3925 flagfuhao = 2
3926 elif str[i] not in num:
3927 return 0
3928 else:
3929 if str[i] not in num:
3930 str = str[:i]#遇到非数字字符修改字符串，而不是return！！！
3931 break#注意！！遇到非数字字符则退出循环
3932 if flagfuhao == 0:
3933 final = compute(str)
3934 elif flagfuhao == 1:#注意flagfuaho是0和1的情况不一样！！！！！！
3935 final = compute(str[1:])
3936 else:
3937 if flagfuhao == 2:
3938 final = (-1) * compute(str[1:])
3939 if final > (pow(2, 31) - 1):
3940 final = (pow(2, 31) - 1)
3941 elif final < -(pow(2, 31)):
3942 final = (-pow(2, 31))
3943 return final
3944 # print(strtoint("-0000002147483648"))
3945 #实现只有0、1、2三种元素的原地排序，且空间复杂度为o(1) 如输入[0, 1, 2, 0, 1, 2]输出：[0, 0, 2, 2, 1, 1]
3946 def yuandisort(list):
3947 #三个指针分别指向：p1指向从左边数的第一个非0元素；p2指向从右边数的第一个非2元素；p1从右往左在中间遍历
3948 #p1若指向的是1则向左走，若指向0，则与p1指向的数字交换；若指向2则与p2指向的数字交换
3949 p0=0
3950 p2=len(list)-1
3951 for i in range(len(list)):
3952 if list[i]==0:
3953 p0+=1
3954 else:
3955 break
3956 for j in range(len(list)-1,-1,-1):
3957 if list[j]==2:
3958 p2-=1
3959 else:
3960 break
3961 p1=p2-1
3962 while p2-p0!=1:
3963 if list[p1]==1:
3964 p1-=1
3965 elif list[p1]==0:
3966 temp=list[p1]
3967 list[p1]=list[p0]
3968 list[p0]=temp
3969 p0+=1
3970 elif list[p1]==2:
3971 temp=list[p1]
3972 list[p1]=list[p2]
3973 list[p2]=temp
3974 p2-=1
3975 print(list)
3976
3977 # yuandisort([0, 1, 2, 0, 1, 2])
3978 '''携程
3979 #同一目的地划分为一组，顺序不可变 求划分组数最多的方法
3980 #输入aabbcddc 输出：aa bb cddc分为三组（考虑abcdabcd这种特殊情况）
3981
3982 strcar = input()
3983 res=[]
3984 length = len(strcar)
3985 i=0
3986 while(i!=length):
3987 start_index = i
3988 end_index = strcar.rfind(strcar[start_index])
3989 j = start_index
3990 while(j < end_index):
3991 end_index = max(end_index, strcar.rfind(strcar[j]))
3992 j+=1
3993
3994 i = end_index+1
3995 res.append(str(end_index - start_index+1))
3996 print(','.join(res))
3997 '''
3998 #跟谁学笔试题
3999 #给定一个大于2的偶数，寻找两个素数使他们的和等于该偶数
4000 def findoushu(num):
4001 for i in range(1,num//2+1):
4002 for j in range(num//2,num):
4003 if i%2!=0 and j%2!=0 and i+j==num:
4004 print(i,j)
4005 # findoushu(8)
4006 #N元钱全部兑换成20,10,5,1块的零钞，求各面值的钞票分别多少张，使得取现后的钞票总张数数量最少，假设N为正整数
4007 def changemoney(mon):
4008 if mon<=0:
4009 return
4010 else:
4011 mon_20=mon_10=mon_5=mon_1=0
4012 if mon//20>0:
4013 mon_20=mon//20
4014 mon=mon%20
4015 if mon//10>0:#顺序依次通过剩余钱数计算对应钱的张数 所以不能用elif
4016 mon_10=mon//10
4017 mon=mon%10
4018 if mon//5>0:
4019 mon_5=mon//5
4020 mon=mon%5
4021 mon_1=mon
4022 print(mon_20,mon_10,mon_5,mon_1)
4023 # changemoney(38)
4024 #删除给定字符串中的连续重复字符，如AABBBCCDDAA=>ABCDA
4025 def dup_delete(s):
4026 firststr=s[0]
4027 firstind=0
4028 i=1
4029 while i<len(s):
4030 while i<len(s) and s[i]==s[firstind]:
4031 i+=1
4032 if i<len(s):
4033 firstind=i
4034 firststr=firststr+s[firstind]
4035 i+=1
4036 print(firststr)
4037 # dup_delete('AABBBCCDDAA')
4038 def dup_delete_1(s):
4039 res=''
4040 i=0
4041 while i<len(s):
4042 res+=s[i]
4043 #注意判断下面这个条件，因为如果最后一个元素与前面的元素不重复，会继续进入下面的循环，而下面的循环要计算s[i+1]超出下标
4044 if i==len(s)-1:
4045 break
4046 while s[i]==s[i+1]:
4047 i+=1
4048 if i==len(s)-1:
4049 break
4050 i+=1
4051 return res
4052 # print(dup_delete_1('AABBBCCDDA'))
4053 #从一个长宽均为2*N+1的方阵中心出发，每一步随机选择上下左右四个方向移动，平均需移动几步才能走出方阵？写一个运行10万次的仿真程序估算期望
4054 def workinmatrix(N):
4055 sum=0
4056 row=N
4057 col=N
4058 count=0
4059 num=0
4060 for _ in range(100000):
4061 if row<0 or row>(2*N) or col<0 or row>(2*N):
4062 col=N
4063 row=N
4064 sum+=count#步数
4065 count=0#重新置为0
4066 num+=1#本轮走出方阵，则走出方阵的次数加1
4067 else:
4068 n=random.randint(1,4)#生成一个[1,4]的整数 1:上 2：下 3：左 4：右
4069 if n==1:
4070 row-=1
4071 elif n==2:
4072 row+=1
4073 elif n==3:
4074 col-=1
4075 else:
4076 col+=1
4077 count+=1
4078 print(sum/num)
4079
4080 # workinmatrix(5)
4081 #用链表实现栈
4082 #如果把链表尾看作栈顶的话入栈操作可以直接将新节点通过.next链接；但是出栈操作需要遍历到栈尾，时间复杂度较高
4083 #如果把链表头看作栈顶，入栈的时候每次更新链表的head（关键是如何更新），出栈直接弹出head即可
4084
4085
4086 #循环实现pow(x,n)即x的n次方
4087 def pow(x,n):
4088 if n<0:
4089 x=1/x
4090 n=-n
4091 pow_com=1
4092 while n:
4093 if n & 1:
4094 pow_com*=x
4095 x*=x
4096 n=n>>1#一定要更新n
4097 return pow_com
4098 # print(pow(2,3))
4099
4100 #递归实现pow(x,n)即x的n次方
4101 def pow_1(x,n):
4102 if not n:
4103 return 1
4104 if n==1:
4105 return x
4106 if n<0:
4107 return pow_1(1/x,-n)
4108 if n&1:
4109 return pow_1(x*x,n//2)*x
4110 else:
4111 return pow_1(x*x,n//2)
4112 # print(pow_1(2,3))
4113 class ListNode2:
4114 def __init__(self, x):
4115 self.val = x
4116 self.next = None
4117 class Solution10:
4118 # 返回从尾部到头部的列表值序列，例如[1,2,3]
4119 def __init__(self):
4120 self.l=[]
4121 def printListFromTailToHead(self, listNode):
4122 head = listNode
4123 if head:
4124 if head.next:
4125 self.printListFromTailToHead(head.next)
4126 self.l.append(head.val)
4127
4128 return self.l
4129 # s=Solution10()
4130 # n1=ListNode2(1)
4131 # n1.next=n2=ListNode2(2)
4132 # n2.next=n3=ListNode2(3)
4133 # n3.next=None
4134 # print(s.printListFromTailToHead(n1))
4135 # # node=n1
4136 # while node:
4137 # print(node.val)
4138 # node=node.next
4139
4140 #斐波那契数列
4141 #用存储空间实现递归
4142 def fib(n,memo):
4143 if n<=1:
4144 return n
4145 else:
4146 if not memo[n]:#若memo[n]==0,说明之前没有计算memo[n],此时需要新计算。否则不需计算
4147 memo[n]=fib(n-1,memo)+fib(n-2,memo)
4148 return memo[n]
4149 # print(fib(3,[0]*(3+1)))
4150
4151 #华为机试题
4152 #第一题 @分隔字符串 统计分割后@前面的字符还有多少
4153 def count_string(s):
4154 ch=s.find('@')#找到@所在位置 若里面没有@字符，输出-1
4155 print(ch)
4156 if s[-1]=='@':
4157 print(s[:-1])
4158 else:
4159 dic1={}
4160 dic2={}
4161 i=0
4162 while i<ch:
4163 dic1[s[i]]=ord(s[i+2])-ord('0')#字符不能直接相减，需要转换成ASCII码才能转换
4164 i+=4
4165 i=ch+1
4166 while i<len(s):
4167 dic2[s[i]]=ord(s[i+2])-ord('0')
4168 i+=4
4169 for key,item in dic1.items():
4170 for k,it in dic2.items():
4171 if key==k:
4172 dic1[key]=item-it
4173 ss=[]
4174 for key,item in dic1.items():
4175 if item!=0:
4176 ss.append(key+':'+str(item))
4177 print(','.join(ss))
4178 #第三题 求表达式值
4179 def compute_str():
4180 s=input()
4181 s=s.replace('!','not')
4182 s=int(eval(s))#eval函数可以实现将str转为list、dict、tuple；也可以将字符串表达式进行计算
4183 print(s)
4184 #上面是直接调用函数，下面是对该功能的实现
4185 def com(n1,n2,op):
4186 if op=='!':
4187 return int(not(n1))
4188 elif op=='&':
4189 return n1 and n2
4190 else:
4191 return n1 or n2
4192 def extra(nums,sighs,op):
4193 if sighs[-1]=='!':
4194 n1=nums.pop()
4195 op=sighs.pop()
4196 n2=0
4197 res=com(n1,n2,sighs[-1])
4198 else:
4199 op=sighs.pop()
4200 n1=nums.pop()
4201 n2=nums.pop()
4202 res=com(n1,n2,sighs[-1])
4203 nums.append(res)
4204 def compute_str_2(string):
4205
4206 nums=[]
4207 sighs=[]
4208 paras={'!':3,'&':2,'|':1}
4209 for i in string:
4210 if i=='1' or i=='0':
4211 nums.append(i)
4212 elif i=='(':
4213 sighs.append(i)
4214 elif i==')':
4215 while sighs[-1]!='(':
4216 extra(nums,sighs,i)
4217 sighs.pop()
4218 elif sighs and paras[i]<paras[sighs[-1]]:#若栈非空且新符号优先级小于栈顶元素优先级，则计算表达式
4219 extra(nums,sighs,i)
4220 else:
4221 sighs.append(i)
4222 while sighs:#栈非空
4223 extra(nums,sighs,sighs.pop())
4224 return nums[0]#即数字栈中的第一个元素也就是最后一个元素就是最终要求的结果
4225 '''
4226 # 华为机试第三题 逆波兰式
4227 #郝少阳写的测例均通过
4228 测试用例：
4229 !(1&0)&0|0 0
4230 1|(1&0) 1
4231 1&0|0&1 0
4232 !0&1|0 1
4233 ((!0&1))|0 1
4234 #代码
4235 prior = {
4236 '!': 3,
4237 '&': 2,
4238 '|': 1,
4239 '(': 0,
4240 }
4241
4242 def caculate(n1, n2, op):
4243 n1 = int(n1)
4244 n2 = int(n2)
4245 if op == '!':
4246 return int(not n1)
4247 elif op == '|':
4248 return int(n1 or n2)
4249 elif op == '&':
4250 return int(n1 and n2)
4251
4252 def extra(nums, sign):
4253 if sign[-1] == '!':
4254 op = sign.pop()
4255 n1 = nums.pop()
4256 n2 = 0
4257 res = caculate(n1, n2, op)
4258 else:
4259 op = sign.pop()
4260 n2 = nums.pop()
4261 n1 = nums.pop()
4262 res = caculate(n1, n2, op)
4263 nums.append(res)
4264
4265 exp = input()
4266 nums = []
4267 sign = []
4268 for c in exp:
4269 if c == '0' or c == '1':
4270 nums.append(c)
4271 elif c == '(':
4272 sign.append(c)
4273 elif c == ')':
4274 while sign[-1] != '(':
4275 extra(nums, sign)
4276 sign.pop()
4277
4278 else:
4279 while len(sign) != 0 and prior[c] < prior[sign[-1]]:
4280 extra(nums, sign)
4281 sign.append(c)
4282
4283 while len(sign) > 0:
4284 extra(nums, sign)
4285 print(nums[0])
4286
4287 '''
4288 #爱奇艺第一题
4289 def func_aiqiyi():#对1~4排列
4290 n = int(input())
4291 a = input().split(" ")
4292
4293 dp = [1]*(len(a)+1)
4294 for c in a:
4295 if c=='0':
4296 dp = dp[:-1]
4297 for i in range(1,len(dp)):
4298 dp[i]+=dp[i-1]
4299 else:
4300 dp = dp[1:]
4301 for i in range(len(dp)-1)[::-1]:
4302 dp[i]+=dp[i+1]
4303 print(dp[0]%(10**9+7))
4304 # count_string('s:2,a:3@s:1')
4305 # print(func(['1','2','13']))
4306 def PrintMinNumber_1(numbers):
4307 # write code here
4308 for i in range(len(numbers) - 1):
4309 for j in range(1, len(numbers)):
4310 a = str(numbers[i]) + str(numbers[j])
4311 b = str(numbers[j]) + str(numbers[i])
4312 if b > a:
4313 temp = numbers[i]
4314 numbers[i] = numbers[j]
4315 numbers[j] = temp
4316 final = ''
4317 for i in numbers:
4318 final += str(i)
4319 return final
4320
4321 # print(PrintMinNumber_1([3,5,1,4,2]))
4322 #冒泡排序
4323 def sort_maopao(nums):
4324 for i in range(len(nums)-1):
4325 for j in range(i+1,len(nums)):#注意第二个循环的控制条件，从i+1开始，到最后一个元素结束
4326 if nums[i]>nums[j]:
4327 temp=nums[i]
4328 nums[i]=nums[j]
4329 nums[j]=temp
4330 print(nums)
4331 return nums
4332 # print(sort_maopao([3,5,1,4,2]))
4333 def func_zj(**p):
4334 return sum(p.values())
4335 # print(func_zj(x=5,y=15,z=20))
4336 # a=['name','age']
4337 # b=['zhangsan',18]
4338 # print(dict(zip(a,b)))
4339
4340 # mylist=[2,3,4,1,7,6,8]
4341 # index=0
4342 # while mylist[index]<7:
4343 # mylist[index]+=mylist[index+1]
4344 # index+=1
4345 # print(mylist)
4346
4347 def findvalue(list,value):
4348 for index,v in enumerate(list):
4349 if v==value:
4350 return index
4351 return False
4352 # list=range(1,100)
4353 # res=findvalue(list,1)
4354 # if res!=False:# is not False
4355 # print('find it and its is %d',res)
4356 # else:
4357 # print('not')
4358
4359 #大数加法
4360 def sum_bigdata(s1,s2):
4361 #思路：将两个数字的每位分别存储到列表（初始化第一位为0，便于加法进位）中，每位各自相加，再对每位分别循环除10取余进位
4362 L1=[0]
4363 L2=[0]
4364 #两个数字哪个位数更多则在少的那个数字前面存放几个0
4365 if(len(s1)>len(s2)):
4366 for i in range(len(s1)-len(s2)):
4367 L2.append(0)
4368 for i in range(0, len(s2)):
4369 L2.append(int(s2[i]))
4370 print(L2)
4371 for i in range(0, len(s1)):
4372 L1.append(int(s1[i]))
4373 print(L1)
4374 else:
4375 for i in range(len(s2)-len(s1)):
4376 L1.append(0)
4377 for i in range(0, len(s1)):
4378 L1.append(int(s1[i]))
4379 for i in range(0, len(s2)):
4380 L2.append(int(s2[i]))
4381 #各位分别相加
4382 for i in range(len(L1)):
4383 L1[i]=L1[i]+L2[i]
4384 # 进位
4385 A=B=len(L1)-1#从最后一位开始往前
4386
4387 while A>0:
4388 if((L1[A])/10)>=1: # or if((L1[A]//10)>0)
4389 L1[A]=L1[A]%10
4390 L1[A-1]=L1[A-1]+1
4391 A-=1
4392 print(L1)
4393 #输出
4394 if L1[0]==0:#若列表第一位为0，则从第二个开始输出
4395 for i in range(1,B+1):
4396 print(L1[i],end='')#在for循环中，每次输出都是换行的。加入end，使用end=“”中的内容代替换行，分隔每次循环输出内容
4397 elif L1[0]!=0:#若列表第一位不为0，则从第一个开始输出
4398 for i in range(B+1):
4399 print(L1[i],end='')
4400 #大数乘法
4401 def list2str(li):
4402 while li[0]==0:
4403 del li[0]
4404 res=''
4405 for i in li:
4406 res+=str(i)
4407 return res
4408
4409 def multiply(stra,strb):
4410 aa=list(stra)
4411 bb=list(strb)
4412 lena=len(stra)
4413 lenb=len(strb)
4414 result=[0 for i in range(lena+lenb)]#总长度为(lena+lenb)
4415 for i in range(lena):
4416 for j in range(lenb):
4417 result[lena-i-1+lenb-j-1]+=int(aa[i])*int(bb[j])#但是在求和时只用了从倒数第2个位置往前的位置，进位时将进位的结果存入最后一个位置
4418 print(result) # [0, 0, 32, 16, 24, 32, 0]#各位分别与另一个数字各位相乘分别得到的结果
4419 #[0, 8, 36, 22, 32, 32, 0]
4420 #[12, 14, 45, 34, 32, 32, 0]
4421 for i in range(len(result)-1):
4422 if result[i]>=10:
4423 result[i+1]+=result[i]//10
4424 result[i]=result[i]%10
4425 return list2str(result[::-1])
4426
4427 # b='4324'
4428 # a='823'
4429 # res=multiply(a,b)
4430 # print('multi',res)
4431 # print('ok',int(a)*int(b))
4432
4433 '''
4434 # #58同城题目
4435 # def pre(num):
4436 # dic={10:"'",11:"!",12:"@",13:"#",14:"$",15:"%",16:"^",17:"&",18:"*",19:"(",20:")",21:"{",22:"}",23:"\",24:"<",25:">",26:"?"}
4437 # if num<27:
4438 # if num<10:
4439 # # print(str(num))
4440 # return str(num)
4441 # else:
4442 # return dic[num]
4443 # num = int(input())
4444 # res=[]
4445 # while num!=0:
4446 # mid=num%27
4447 # print(mid)
4448 # res.append(pre(mid))
4449 # num=num//27
4450 # print(''.join(res[::-1]))
4451
4452
4453
4454 # info=input().split(',')
4455 # num=int(info[0])
4456 # ss=[int(i) for i in info[1:]]
4457 # ss.sort(reverse=True)
4458 # if int(len(ss)*num/100)==len(ss)*num/100:
4459 # print(','.join([str(i) for i in ss[:len(ss)*num/100]]))
4460 # else:
4461 # print(','.join([str(i) for i in ss[:int(len(ss)*num/100+1)]]))
4462
4463 # info=input().split('@')
4464 # [name,field]=[info[0],info[1]]
4465 # ms='MASK'*int((len(name)+4-1)/4)
4466 # ms=ms[:len(name)]
4467 # res=['']*len(name)*2
4468 # res[::2]=name
4469 # res[1::2]=ms
4470 # print((''.join(res))[::-1]+"@"+field)
4471
4472 # info=input().split('@')
4473 # [name,field]=[info[0],info[1]]
4474 # ms='MASK'*int((len(name)+4-1)/4)
4475 # ms=ms[:len(name)]
4476 # resu=(''.join([i+j for i,j in zip(name,ms)]))[:-1]+'@'+field
4477 # print(resu)
4478 '''
4479 # [n,m]=input().split()
4480 # n,m=int(n),int(m)
4481 # count=0
4482 # for i in range(m):
4483 # l,r=input().split()
4484 # count+=int(r)+1-int(l)
4485 # print(count)
4486 '''
4487 #第一题:乘积的最小和
4488 line=input().split()
4489 n,m=int(line[0]),int(line[1])
4490 cont=input().split()
4491 cont=[int(i) for i in cont]
4492 cont=sorted(cont)
4493 if len(cont)<2:
4494 print(0)
4495 else:
4496 if m==1:
4497 print(cont[0]*cont[1])
4498 else:
4499 sum=0
4500 count=0
4501 for i in range(n//2):
4502 count+=1
4503 sum=sum+(cont[i]*cont[n-1-i])
4504 if count==m:
4505 break
4506 print(sum)
4507
4508 '''
4509 #第三题字典
4510 # [N,M,K]=[int(i) for i in input().split()]
4511 # s=['a']
4512 # n,m=1,0
4513 # flag=[]
4514 # for k in range(2,K+1):
4515 # if n<N:
4516 # s.append('a')
4517 # n+=1
4518 # elif m<M:
4519 # if s[len(s) - 1] == 'a':
4520 # flag.append(len(s)-1)
4521 # s.append('b')
4522 # m+=1
4523 # else:
4524 # s=s[:flag.pop()]+['b']
4525 # if s[len(s)-2]=='a':
4526 # flag.append(len(s)-2)
4527 # n=s.count('a')
4528 # m=s.count('b')
4529 #
4530 # print(''.join(s))
4531
4532 #第二题：种树
4533 # [n,m]=[int(i) for i in input().split()]
4534 # road=[0]*10000
4535 # for i in range(m):
4536 # [l,r]=[int(j) for j in input().split()]
4537 # for i in range(l,r+1):
4538 # road[i]=1
4539 # print(sum(road))
4540
4541
4542 #度小满笔试
4543 #1.隔山打牛
4544 n=int(input())
4545 line=input().split()
4546
4547 blood=[0]
4548 for l in line:
4549 blood.append(int(l))
4550 if n==1:
4551 print(blood[1])
4552 else:
4553 if n%2!=0:
4554 end=(n-1)//2
4555 else:
4556 end=n//2
4557 res=[]
4558 result=0
4559 for i in range(1,end+1):
4560 res.append(blood[i])
4561 if i*2<=n:
4562 res.append(blood[i*2])
4563 if i*2+1<=n:
4564 res.append(blood[i*2+1])
4565 result+=max(res)
4566 print(result)