Leetcode 科学刷题总结

面试技巧：

五毒神掌内功心法

第一遍：

第二遍：

第三遍：（24小时之后）

第四遍：（1周后）

第五遍：（面试前一周）

理解人的记忆规律，高频率高效复习

形成长期记忆的方法其实非常简单，即频繁且有效的重复刺激

算法题汇总

不同算法类型

题型汇总

1. 滑动窗口

# Sliding windows code template is most used in substring match or maximum/minimum problems.# It uses two-pointer as boundary of sliding window to traverse, and use a counter(dict) maintain current state,# and a count as condition checker, update it when trigger some key changes.## Time:  O(n)# Space: O(k) k = len(set(p))fromcollectionsimportCounter# s - target sequence, p - pattern or restrict sequencedefsliding_window_template_with_examples(s,p):# initialize the hash map here# counter is used to record current state, could use defaultdict in some situation, for example, no p restrictcounter=Counter(p)# two pointers, boundary of sliding windowstart,end=0,0# condition checker, update it when trigger some key changes, init value depend on your situationcount=0# result, return int(such as max or min) or list(such as all index)res=0# loop the source string from begin to endwhileend<len(s):counter[s[end]]+=1# update count based on some conditionifcounter[s[end]]>1:count+=1end+=1# count condition herewhilecount>0:'''            update res here if finding minimum            '''# increase start to make it invalid or valid againcounter[s[start]]-=1# update count based on some conditionifcounter[s[start]]>0:count-=1start+=1'''        update res here if finding maximum        '''res=max(res,end-start)returnres# refer to https://leetcode.com/problems/minimum-window-substring/discuss/26808/here-is-a-10-line-template-that-can-solve-most-substring-problems

2. 双指针

# two pointers scenario, famous applications such as binary search, quick sort and sliding window.'''Classification:1. old & new state: old, new = new, cur_result2. slow & fast runner: slow-> fast->->3. left & right boundary or index: left-> <-right4. p1 & p2 from two sequences: p1-> p2->5. start & end sliding window boundary: start-> end->'''# old & new state: old, new = new, cur_resultdefold_new_state(self,seq):# initialize stateold,new=default_val1,default_val2forelementinseq:'''        process current element with old state        '''old,new=new,self.process_logic(element,old)# slow & fast runner: slow-> fast->->defslow_fast_runner(self,seq):# initialize slow runnerslow=seq[0]# for index: slow = 0# fast-runner grows each iteration generallyforfastinrange(seq):# for index: range(len(seq))'''        slow-runner grows with some restrictions        '''ifself.slow_condition(slow):slow=slow.next# for index: slow += 1'''        process logic before or after pointers movement        '''self.process_logic(slow,fast)# left & right boundary or index: left-> <-rightdefleft_right_boundary(self,seq):left,right=0,len(seq)-1whileleft<right:'''        left index moves when satisfy the condition        '''ifself.left_condition(left):left+=1'''        right index move when satisfy the condition        '''ifself.right_condition(right):right-=1'''        process logic before or after pointers movement        '''self.process_logic(left,right)# p1 & p2 from two sequences: p1-> p2->defpointers_from_two_seq(self,seq1,seq2):# init pointersp1,p2=0,0# or seq1[0], seq2[0]# or other conditionwhilep1<len(seq1)andp2<len(seq2):'''        p1 index moves when satisfy the condition        '''ifself.p1_condition(p1):p1+=1# or p1 = next(seq1)'''        p2 index move when satisfy the condition        '''ifself.p2_condition(p2):p2+=1# or p2 = next(seq2)'''        process logic before or after pointers movement        '''self.process_logic(p1,p2)# start & end of sliding window: |start-> ... end->|# more details in sliding windows templates, here is just about two-pointers partdefstart_end_sliding_window(self,seq):start,end=0,0whileend<len(seq):# end grows in the outer loopend+=1# start grows with some restrictwhileself.start_condition(start):'''            process logic before pointers movement            '''self.process_logic1(start,end)# start grows in the inner loopstart+=1'''        or process logic after pointers movement        '''self.process_logic2(start,end)

3. 快慢指针/ 链表题目

# a Linked list is a linear collection of data elements, whose order is not given by their physical placement in memory.# Instead, each element points to the next.## when operation with linked list, we can choose to change list node or change node value.# change node value is more easy-understanding, and may need extra space to store.## Time:  O(1) to insert and delete, O(n) to random access# Space: O(n)# Definition for singly-linked list.classListNode:def__init__(self,x):self.val=xself.next=None# add dummy node to help flag the head, usually used in head may changed or merging None edge case.defdummy_node_assist(self,head):dummy=ListNode(0)cur=dummy.next=head# or cur = dummywhilecur:'''        process current node logic        '''self.process_logic(cur)returndummy.next# another solution is use self.next, more pythonicdefself_assist(self,head):pre,pre.next=self,headwhilepre.next:'''        process current node logic        '''self.process_logic(pre.next)returnself.next# add nodedefadd_node(pre_node,new_node):pre_node.next,new_node=new_node,pre_node.next# delete nodedefdelete_node(pre_node):pre_node.next=pre_node.next.next# reverse linked list iterativelydefreverse_iteratively(head:ListNode)->ListNode:prev,cur=None,headwhilecur:cur.next,cur,prev=prev,cur.next,curreturnprev# reverse linked list recursivelydefreverse_recursively(head:ListNode)->ListNode:defrecursive(cur,pre=None):ifnotcur:returnprepre,cur.next=cur.next,prereturnrecursive(pre,cur)returnrecursive(head)

4. 原地链表翻转

# a Linked list is a linear collection of data elements, whose order is not given by their physical placement in memory.# Instead, each element points to the next.## when operation with linked list, we can choose to change list node or change node value.# change node value is more easy-understanding, and may need extra space to store.## Time:  O(1) to insert and delete, O(n) to random access# Space: O(n)# reverse linked list iterativelydefreverse_iteratively(head:ListNode)->ListNode:prev,cur=None,headwhilecur:cur.next,cur,prev=prev,cur.next,curreturnprev# reverse linked list recursivelydefreverse_recursively(head:ListNode)->ListNode:defrecursive(cur,pre=None):ifnotcur:returnprepre,cur.next=cur.next,prereturnrecursive(pre,cur)returnrecursive(head)

5. 区间合并

todoMergeIntervalsalgorithmtemplate

6. 无序限定范围的数组元素查找O(N）

todo无序限定范围的数组元素查找O(N）algorithmtemplate

7. BFS

# Breadth-first search is traversing or searching tree or graph data structures, including graph-like solution space.# it explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.## Time:  O(V+E)     V: vertex, E: edges# Space: O(V)fromcollectionsimportdeque# iteration version, using dequedefbfs_iteratively_by_queue(self,start,target=None):queue,visited=deque([start]), {start}whilequeue:node=queue.popleft()visited.add(node)'''        process current node logic here        '''self.process_logic(node)# target is optionalifnode==target:'''            reach the goal and break out            '''self.process_target_logic(target)breakfornext_nodeinnode.get_successors():ifnext_nodenotinvisited:queue.append(next_node)# iteration version, using list, pythonic-style# conciser but more memory, mainly used when you want to collect the whole listdefbfs_iteratively_by_list(self,start,target=None):node_list,visited= [start], {start}# append while traversingfornodeinnode_list:visited.add(node)'''        process current node logic here        '''self.process_logic(node)# target is optionalifnode==target:'''            reach the goal and break out            '''self.process_target_logic(target)breakfornext_nodeinnode.get_successors():ifnext_nodenotinvisited:node_list+=node# basically the node_list is useful herereturnnode_list# recursion version, uncommondefbfs_recursively(self,queue:deque,visited:set,target=None):ifnotqueue:returnnode=queue.popleft()visited.add(node)'''    process current node logic here    '''self.process_logic(node)# target is optionalifnode==target:'''        reach the goal and break out        '''self.process_target_logic(target)returnfornext_nodeinnode.get_successors():ifnext_nodenotinvisited:queue.append(next_node)self.bfs_recursively(queue,visited)# bfs list comprehension in row of binary treedefbfs_row(self,root):row= [root]whilerow:'''        process current node logic here        '''# process logic separatelyrow= [childfornodeinrowforchildin (node.left,node.right)ifnode]

8. 树的DFS

# Deep-first search is traversing or searching tree or graph data structures, including graph-like solution space.# it starts at the root node and explores as far as possible along each branch before backtracking.## Time:  O(V+E)     V: vertex, E: edges# Space: O(V)# recursion versiondefdfs_recursively(self,node,visited:set):visited.add(node)'''    process current node logic here    '''self.process_logic(node)fornext_nodeinnode.get_successors():ifnext_nodenotinvisited:self.dfs_recursively(next_node,visited)# iteration version, uncommondefdfs_iteratively(self,root):stack,visited= [root],set()whilestack:node=stack.pop()visited.add(node)'''        process current node logic here        '''self.process_logic(node)fornext_nodeinnode.get_successors():ifnext_nodenotinvisited:stack.append(next_node)

9. DFS/递归/回溯法

# Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably#  constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate#  ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.## backtracking vs. dfs# traverse in solution space vs. traverse in data structure space, pruned of dfsdefbacktracking(self,data,candidate):# pruningifself.reject(data,candidate):return# reach the endifself.accept(data,candidate):returnself.output(data,candidate)# drill downforcur_candidateinself.all_extension(data,candidate):# or you can choose to prune here, recursion depth - 1ifnotself.should_to_be_pruned(cur_candidate):self.backtracking(data,cur_candidate)

11. 二分法与二分法变种

# binary search requires sorted iterator. Common variation is find left-most or right-most index.## Time:  O(log(n))# Space: O(1)# [lo, hi] versiondefbinary_search(arr,target):lo,hi=0,len(arr)-1whilelo<=hi:# no overflow problem in python, (lo + hi) // 2 is better.# mid = lo + (hi - lo) // 2mid= (lo+hi)//2'''        change to your comparison condition as you need        '''# find the targetifarr[mid]==target:breakelifarr[mid]<target:lo=mid+1else:hi=mid-1# [lo, hi) versiondefbinary_search2(arr,target):lo,hi=0,len(arr)whilelo<hi:mid= (lo+hi)//2# find the targetifarr[mid]==target:breakelifarr[mid]<target:lo=mid+1else:hi=mid# result in [0, hi]defbisect_left(arr,target,lo,hi):whilelo<hi:mid= (lo+hi)//2# left-most, so equal will be on the right sideifarr[mid]<target:lo=mid+1else:hi=mid'''        # bisect right code        if arr[mid] > target:            hi = mid        else:            lo = mid + 1        '''returnlo

12. 前K大的数模式HEAP

# heap, also called priority queue# heap common operations: heapify, top, heappush, heappop, heappushpop, heapreplace, _siftup/_siftdown,# nlargest/nsmallest, merge# heapq in Python, there is only min heap, if you want to a max heap, you should reverse the key or implement __lt__.## Time:  O(1) to find, O(log(n)) to push/pop/sift, O(nlog(n)) to heapify, O(n) to merge# Space: O(n)## from Queue import PriorityQueue is alternative way, which is a thread-safe classimportheapqdefheap_operations():heap= [4,2,1,3]# heapifyheapq.heapify(heap)# toptop=heap[0]# heappoptop=heapq.heappop(heap)# heappushheapq.heappush(heap,5)# heappushpop = push + popheapq.heappushpop(heap,0)# heapreplace = pop + pushheapq.heapreplace(heap,0)data= [10,5,18,2,37,3,8,7,19,1]heapq.heapify(data)old,new=8,22# increase the 8 to 22i=data.index(old)data[i]=new# _siftup, from root to leaf, when increaseheapq._siftup(data,i)old,new=10,4# decrease the 10 to 4i=data.index(old)data[i]=new# _siftdown, from leaf to root, when decreaseheapq._siftdown(data,0,i)# find n largest by queueheapq.nlargest(data,3)# find n smallest by queueheapq.nsmallest(data,3)# Merge multiple sorted inputs into a single sorted output# e.g. merge timestamped entries from multiple log filesheapq.merge([1,3,5,7], [0,2,4,8], [5,10,15,20], [], [25])

13. K路归并

todoK路归并algorithmtemplate

14. DP 动态规划

# simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner# dynamic programming = recursion + memorized# state definition, state transition equation, optimal substructure# direction: bottom-up or top-downdefdynamic_programming_template_with_example(word1,word2):m,n=len(word1),len(word2)# states definition: cur_min_edit_dist# states compressed to two states: old and newdp= [[0]* (m+1)for_inrange(2)]# initialize the initial edit distance, add one more state for init stateforiinrange(0,m+1):dp[0][i]=icur=1foriinrange(n):# initialize the init statedp[cur][0]=i+1forjinrange(m):# state transition equation# if char matched, this is the min dist.ifword1[j]==word2[i]:dp[cur][j+1]=dp[cur^1][j]# otherwise, 1 + minimum of edit/remove/add operationselse:dp[cur][j+1]=1+min(dp[cur^1][j],dp[cur^1][j+1],dp[cur][j])# switch between two statescur^=1# return the last state as resultreturndp[cur^1][-1]

15. 排序算法

# all kinds of sort algorithm, just some common versions to show its idea.# here I unify the api as xxx_sort(arr), changed in-place## currently include:# quick, merge, insert, bubble, selection, heap, shell, bucket, counting, radix, topological## constant space vs extra space (merge O(n), counting O(k), bucket O(n+k), radix O(n+k))## in place vs out place (merge, counting, bucket, radix)## stable vs unstable (selection, quick, heap, shell)## comparison based vs non-comparison based (radix, bucket, counting)## comparison of counting, bucket and radix sort: all use bucket idea# counting sort:  store the single key in bucket# bucket sort:    store a range in bucket# radix sort:     store each part of element in bucket# sort      average     best        worst       space   place       stable      comparison# bubble    O(n^2)      O(n)        O(n^2)      O(1)    in-place    stable      comparison# selection O(n^2)      O(n^2)      O(n^2)      O(1)    in-place    unstable    comparison# insert    O(n^2)      O(n)        O(n^2)      O(1)    in-place    stable      comparison# shell     O(nlogn)    O(nlogn^2)  O(nlogn^2)  O(1)    in-place    unstable    comparison# merge     O(nlogn)    O(nlogn)    O(nlogn)    O(n)    out-place   stable      comparison# quick     O(nlogn)    O(nlogn)    O(n^2)      O(logn) in-place    unstable    comparison# heap      O(nlogn)    O(nlogn)    O(nlogn)    O(1)    in-place    unstable    comparison# counting  O(n+k)      O(n+k)      O(n+k)      O(k)    out-place   stable      non-comparison# bucket    O(n+k)      O(n+k)      O(n^2)      O(n+k)  out-place   stable      non-comparison# radix     O(nk)       O(nk)       O(nk)       O(n+k)  out-place   stable      non-comparisonimportrandomimporttimefromcollectionsimportdequefromcollectionsimportdefaultdict'''quick sortavg: O(nlogn), best: O(nlogn), worst: O(n^2), space: O(logn), in-place, unstable, comparisonfastest in large-scale and out-of-order data, divide & conquer'''defquick_sort(arr):quick_sort_rec(arr,0,len(arr)-1)# hi is included, in range [lo, hi]defquick_sort_rec(arr,lo,hi):iflo<hi:pivot=partition(arr,lo,hi)quick_sort_rec(arr,lo,pivot-1)quick_sort_rec(arr,pivot+1,hi)defpartition(arr,lo,hi):# choose pivot by median-of-threex,idx=sorted(((arr[lo],lo), (arr[hi],hi), (arr[lo+hi>>1],lo+hi>>1)))[1]arr[lo],arr[idx]=arr[idx],arr[lo]whilelo<hi:whilelo<hiandarr[hi]>=x:hi-=1arr[lo]=arr[hi]whilelo<hiandarr[lo]<=x:lo+=1arr[hi]=arr[lo]arr[lo]=xreturnlo'''merge sortavg: O(nlogn), best: O(nlogn), worst: O(nlogn), space: O(n), out-place, stable, comparisondivide & conquer'''# the version with a fixed temp arraydefmerge_sort(arr):merge_sort_rec(arr,0,len(arr)-1, [0]*len(arr))defmerge_sort_rec(arr,first,last,temp):iffirst<last:mid= (first+last)//2merge_sort_rec(arr,first,mid,temp)merge_sort_rec(arr,mid+1,last,temp)merge(arr,first,mid,last,temp)defmerge(arr,first,mid,last,temp):i,j=first,mid+1m,n=mid,lastk=0whilei<=mandj<=n:ifarr[i]<=arr[j]:temp[k]=arr[i]i+=1else:temp[k]=arr[j]j+=1k+=1whilei<=m:temp[k]=arr[i]i+=1k+=1whilej<=n:temp[k]=arr[j]j+=1k+=1foriinrange(k):arr[first+i]=temp[i]defmerge_sort2(arr):res=merge_sort_rec2(arr)foriinrange(len(arr)):arr[i]=res[i]defmerge_sort_rec2(arr):iflen(arr)<=1:returnarrmid=len(arr)//2left=merge_sort_rec2(arr[:mid])right=merge_sort_rec2(arr[mid:])returnmerge1(left,right)defmerge1(left,right):res= []i=j=0whilei<len(left)andj<len(right):ifleft[i]<=right[j]:res.append(left[i])i+=1else:res.append(right[j])j+=1whilei<len(left):res.append(left[i])i+=1whilej<len(right):res.append(right[j])j+=1returnres# more pythonic but slowerdefmerge2(left,right):res= []whileleftandright:ifleft[0]<=right[0]:res.append(left.pop(0))else:res.append(right.pop(0))returnres+ (leftorright)# slowestdefmerge3(left,right):res= []whileleftandright:ifleft[-1]>right[-1]:res.insert(0,left.pop())else:res.insert(0,right.pop())return (leftorright)+res'''insert sortavg: O(n^2), best: O(n), worst: O(n^2), space: O(1), in-place, stable, comparisonfast in small-scale and almost sorted data'''definsert_sort(arr):foriinrange(1,len(arr)):x=arr[i]j=i-1whilej>=0andarr[j]>x:arr[j+1]=arr[j]j=j-1arr[j+1]=x'''bubble sortavg: O(n^2), best:O(n), worst: O(n^2), space:O(1), in-place, stable, comparisonoptimization:1. flag whether swap last round, if not, end sort2. flag the last swap place, [last_swap, j] has been sorted, just skip it.'''# bubble the max to right mostdefbubble_sort(arr):foriinrange(len(arr)-1):forjinrange(len(arr)-i-1):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]# optimizationdefbubble_sort2(arr):i=len(arr)-1whilei>0:last_swap=0forjinrange(i):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]last_swap=j# if last_swap=0, it means no swap in last round, end sort# [last_swap, i] has been sorted, start from last_swapi=last_swap'''selection sortavg: O(n^2), best: O(n^2), worst: O(n^2), space: O(1), in-place, unstable, comparisonmost stable in time cost, always O(n^2), and easy understanding, used in small scale data'''defselection_sort(arr):foriinrange(len(arr)):min_i=iforjinrange(i+1,len(arr)):ifarr[j]<arr[min_i]:min_i=jarr[i],arr[min_i]=arr[min_i],arr[i]'''heap sortavg: O(nlogn), best: O(nlogn), worst: O(nlogn), space: O(1), in-place, unstable, comparisonnot only a sort algorithm, this structure (priority queue) can do more thing.'''defheap_sort(arr):# build max heapforiinrange(len(arr)//2)[::-1]:heap_adjust(arr,i,len(arr))# adjust from last elementforiinrange(1,len(arr))[::-1]:# swap first with the last, make the right most is maximumarr[0],arr[i]=arr[i],arr[0]heap_adjust(arr,0,i)defheap_adjust(arr,i,n):cur=arr[i]while2*i+1<n:# get child index in heapchild=2*i+1# choose the larger childifchild<n-1andarr[child+1]>arr[child]:child+=1# if child is larger than parent, sift upifcur<arr[child]:arr[i],arr[child]=arr[child],curi=childelse:break'''shell sortavg: O(nlogn), best: O(nlogn^2), worst: O(nlogn^2), space: O(1), in-place, unstable, comparisonimprovement of insertion sort'''defshell_sort(arr):# Shell sort using Shell's (original) gap sequence: n/2, n/4, ..., 1.gap=len(arr)//2# loop over the gapswhilegap>0:# do the insertion sortforiinrange(gap,len(arr)):val=arr[i]j=iwhilej>=gapandarr[j-gap]>val:arr[j]=arr[j-gap]j-=gaparr[j]=valgap//=2'''counting sortavg: O(n+k), best:O(n+k), worst:O(n+k), space:O(k), out-place, stable, non-comparisonrelatively concentrated values'''defcounting_sort(arr):min_val,max_val=min(arr),max(arr)size=max_val-min_val+1counter= [0]*sizeforiinrange(len(arr)):counter[arr[i]-min_val]+=1idx=0fori,vinenumerate(counter):# use slice assignmentarr[idx:idx+v]= [i+min_val]*vidx+=v'''bucket sortavg: O(n+k), best:O(n+k), worst:O(n^2), space:O(n+k), out-place, stable, non-comparisonimprovement of counting sort, usually used with hash'''DEFAULT_BUCKET_SIZE=5defbucket_sort(arr,size=DEFAULT_BUCKET_SIZE):min_val,max_val=min(arr),max(arr)# initialize bucketscount= (max_val-min_val)//size+1buckets= [[]for_inrange(count)]# put values in bucketsforiinrange(len(arr)):buckets[(arr[i]-min_val)//size].append(arr[i])# sort buckets and place back into input arrayi=0forbucketinbuckets:insert_sort(bucket)# use slice assignmentarr[i:i+len(bucket)]=bucketi+=len(bucket)# with hashdefbucket_sort2(arr):# get hash codescode=hashing(arr)buckets= [[]for_inrange(code[1])]# distribute data into buckets: O(n)foriinarr:x=re_hashing(i,code)buckets[x].append(i)i=0# merge the buckets: O(n)forbucketinbuckets:insert_sort(bucket)arr[i:i+len(bucket)]=bucketi+=len(bucket)defhashing(arr):return [max(arr),int(len(arr)**0.5)]defre_hashing(i,code):returnint(i/code[0]* (code[1]-1))'''radix sortavg: O(nk), best:O(nk), worst:O(nk), space:O(n+k), out-place, stable, non-comparisonimprovement of counting sort'''defradix_sort(arr):radix=10max_length=Falseplacement=1whilenotmax_length:max_length=True# declare and initialize bucketsbuckets= [[]for_inrange(radix)]# split arr between listsforiinarr:temp=i//placementbuckets[temp%radix].append(i)ifmax_lengthandtemp>0:max_length=False# assign from bucket to arri=0forbucketinbuckets:insert_sort(bucket)# use slice assignmentarr[i:i+len(bucket)]=bucketi+=len(bucket)# move to next digitplacement*=radixreturnarr'''topological sortin a directed graph, a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v,u comes before v in the ordering.'''GRAY,BLACK=0,1deftopological_sort(graph):order,enter,state=deque(),set(graph), {}defdfs(node):state[node]=GRAYforkingraph.get(node, ()):sk=state.get(k,None)ifsk==GRAY:raiseValueError("cycle")ifsk==BLACK:continueenter.discard(k)dfs(k)order.appendleft(node)state[node]=BLACKwhileenter:dfs(enter.pop())returnorderif__name__=='__main__':defsort_test(sort_func):start=time.time()for_inrange(100):nums= [random.randrange(1,250)for_inrange(1000)]nums1=sorted(nums)sort_func(nums)ifnums1!=nums:print('incorrect', )end=time.time()print('{:15s} time: {}'.format(sort_func.__name__,end-start))sort_test(quick_sort)sort_test(merge_sort)sort_test(merge_sort2)sort_test(heap_sort)sort_test(shell_sort)sort_test(counting_sort)sort_test(bucket_sort)sort_test(bucket_sort2)sort_test(radix_sort)# put turtle algorithms to the tailsort_test(insert_sort)sort_test(bubble_sort)sort_test(bubble_sort2)sort_test(selection_sort)graph=defaultdict(list)graph['A'].append('B')graph['B'].append('D')graph['C'].append('A')print(topological_sort(graph))

16. 树和链表结合

# Classification: binary tree, complete binary tree, full binary tree, binary search tree, AVL tree(self-balancing)## Time:  O(n)# Space: O(h) h: height of treefromcollectionsimportdeque# Definition for a binary tree nodeclassTreeNode:def__init__(self,x):self.val=xself.left=Noneself.right=None'''traverse binary tree recursively'''# pre-order: root->left->rightdefpreorder_traversal_recursively(self,root:'TreeNode'):# recursion terminator here# you can check if none when add left and right child, it will decrease one recursion depth,# but you have to check whether root is None outside.ifnotroot:return'''    add current node logic here    '''self.process_logic(root)self.preorder_traversal_recursively(root.left)self.preorder_traversal_recursively(root.right)# in-order: left->root->rightdefinorder_traversal_recursively(self,root:'TreeNode'):ifnotroot:returnself.inorder_traversal_recursively(root.left)'''    add current node logic here    '''self.process_logic(root)self.inorder_traversal_recursively(root.right)# post-order: left->right->rootdefpostorder_traversal_recursively(self,root:'TreeNode'):ifnotroot:returnself.postorder_traversal_recursively(root.left)self.postorder_traversal_recursively(root.right)'''    add current node logic here    '''self.process_logic(root)# level-order# to traverse recursively, need help from extra data structure or dfs level by leveldeflevel_order_traversal_recursively(self,root:'TreeNode')->'List[List[int]]':res= []defdfs(root,level):ifnotroot:returniflen(res)<level+1:res.append([])'''        add current node logic here        '''self.process_logic(root)res[level].append(root.val)dfs(root.left,level+1)dfs(root.right,level+1)dfs(root,0)returnres'''traverse binary tree iteratively'''# There are too many version to traverse iteratively, just choose the one you like it.# pre-order: root->left->rightdefpreorder_traversal_iteratively(self,root:'TreeNode'):ifnotroot:return []stack= [root]whilestack:root=stack.pop()'''        add current node logic here        '''self.process_logic(root)# push right child first because of FILOifroot.right:stack.append(root.right)ifroot.left:stack.append(root.left)# in-order: left->root->rightdefinorder_traversal_iteratively(self,root:'TreeNode'):stack= []# keep stack empty and compare root too, compatible with edge case: root=Nonewhilestackorroot:# push itself and all left children into stack iterativelywhileroot:stack.append(root)root=root.leftroot=stack.pop()'''        add current node logic here        '''self.process_logic(root)# point to right childroot=root.right# here I choose to not use# post-order: left->right->rootdefpostorder_traversal_iteratively(self,root:'TreeNode'):ifnotroot:return []stack= [root]# used to record whether left or right child has been visitedlast=Nonewhilestack:root=stack[-1]# if current node has no left right child, or left child or right child has been visited, then process and pop itifnotroot.leftandnotroot.rightorlastand (root.left==lastorroot.right==last):'''            add current node logic here            '''self.process_logic(root)stack.pop()last=root# if not, push right and left child in stackelse:# push right first because of FILOifroot.right:stack.append(root.right)ifroot.left:stack.append(root.left)# post-order: left->right->root# use visit flagdefpostorder_traversal_iteratively2(self,root:'TreeNode'):ifnotroot:return []stack= [root]whilestack:root=stack[-1]# use visited attribute to judge whether it has been visitedifhasattr(root,'visited'):'''            add current node logic here            '''self.process_logic(root)stack.pop()delroot.visitedelse:ifroot.right:stack.append(root.right)ifroot.left:stack.append(root.left)root.visited=True# level-orderdeflevel_order_traversal_iteratively(self,root:'TreeNode'):ifnotroot:return []queue=deque([root])whilequeue:for_inrange(len(queue)):cur=queue.popleft()'''            add current node logic here            '''self.process_logic(cur)ifcur.left:queue.append(cur.left)ifcur.right:queue.append(cur.right)'''        add level logic here if you need        '''

17. 树的重新构建

相关算法模板同上树和链表结合

18. 位运算

# Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word.## common bit-wise operation## operations priority:# {}[]() -> ** -> ~ -> -x -> *,/,% -> +,- -> <<,>> -> & -> ^ -> | -> <>!= -> is -> in -> not x -> and -> ordefbit_wise_operations(a,b):# not~a# ora|b# anda&b# xora^b# shift operatorsa<<ba>>b# subtractiona&~b# set bit, assign to 1a|=1<<b# clear bit, assign to 0a&=~(1<<b)# test bitifa&1<<b:pass# extract last bita&-a# remove last bita& (a-1)# check is odd or evenifa&1:print('odd')# clear right n bita& (~0<<b)# clear left until to na& ((1<<b)-1)# reference# https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently

19. 字符串

# string is traditionally a sequence of characters, either as a literal constant or as some kind of variable.importstringdefstring_operations():s='abcab'# join','.join(s)# splits.split(',')# replaces.replace()# index & find, index return -1 if not founds.index('a')s.find('a')s.rfind('a')# counts.count('a')# start & end withs.startswith('a')s.endswith('b')# translateintab="aeiou"outtab="12345"trantab=str.maketrans(intab,outtab)s.translate(trantab)# strips.lstrip()s.rstrip()s.strip()# justs.ljust(10)s.rjust(10)s.center(10)s.zfill(10)# common stringstring.punctuationstring.whitespacestring.ascii_lowercasestring.hexdigitsstring.printable

20. stack

# stack common operation: push, pop, top# stack is used in pairs, maintain extreme value## FILO: First In, Last Out# Time:  O(1)# Space: O(n)# sequence stack based on listdefstack_operations():# initializationstack= []# size of stacksize=len(stack)# pushstack.append(1)# check is emptyifstack:# toptop=stack[-1]# popstack.pop()

21. array

# list is a collection which is ordered and changeable, with continuous space.## Time:  O(1) to index or write or append, O(n) to insert or remove# Space: O(n)deflist_operations():# initializationlist1= [3,1,2,4]list2=list(range(5))# [*X] equals to list(X)list2= [*range(5)]# appendlist1.append(5)list1+= [5]list1+=5,list1.extend([5,6])# insertlist1.insert(0)# indexlist1.index(3)# countlist1.count(3)# removelist1.remove(3)# sortlist1.sort(reverse=True)# reverselist1.reverse()

22. 二叉搜索树

# binary search requires sorted iterator. Common variation is find left-most or right-most index.## Time:  O(log(n))# Space: O(1)# [lo, hi] versiondefbinary_search(arr,target):lo,hi=0,len(arr)-1whilelo<=hi:# no overflow problem in python, (lo + hi) // 2 is better.# mid = lo + (hi - lo) // 2mid= (lo+hi)//2'''        change to your comparison condition as you need        '''# find the targetifarr[mid]==target:breakelifarr[mid]<target:lo=mid+1else:hi=mid-1# [lo, hi) versiondefbinary_search2(arr,target):lo,hi=0,len(arr)whilelo<hi:mid= (lo+hi)//2# find the targetifarr[mid]==target:breakelifarr[mid]<target:lo=mid+1else:hi=mid# result in [0, hi]defbisect_left(arr,target,lo,hi):whilelo<hi:mid= (lo+hi)//2# left-most, so equal will be on the right sideifarr[mid]<target:lo=mid+1else:hi=mid'''        # bisect right code        if arr[mid] > target:            hi = mid        else:            lo = mid + 1        '''returnlo

算法和数据结构(学习相关书籍推荐)

Donate