Shulou(Shulou.com)06/02 Report--

This article mainly explains the "what Python algorithm commonly used skills and built-in library", the article explains the content is simple and clear, easy to learn and understand, the following please follow the editor's ideas slowly in depth, together to study and learn "what Python algorithm commonly used skills and built-in library" bar!

1. Input and output:

1.1 the first row is given two values, n, m, separated by spaces, the first n determines the input of n lines, m determines how many numbers there are in each line, and m numbers are separated by spaces.

Solution: the input received by python's input function is a string by default, so we can solve the input problem perfectly by using string cutting, cast, and list generator. The code is as follows:

# receive two values, use NMagnem to receive two values in the list, respectively, NMagnem = [int (x) for x in input (). Split ()] # construct the list of the input list num_list = [] for i in range (n): # python can ignore the value of m Take all the values in and use len to determine the length tmp_list = [int (x) for x in input (). Split ()] num_list.append (tmp_list)

By the same token, if you are separated by a comma (,), the same value is passed in the split function.

1.2 output a line of digits

Since the print function of python uses line breaks as the Terminator by default, we need to modify it to the interval we need, as follows:

For i in range (10): print (I, end='')

End is a parameter in the print function that determines the end character of the output. Here, it is modified to a space to represent the output of a line of numbers, separated by spaces, and other characters can be modified by themselves.

two。 Empty list generation, string modification, list traversal

2.1 during the coding process, it is sometimes necessary to have an empty list with length and initial values, which is generated as follows:

# 1. Multiply to generate an one-dimensional list with an initial value of False, visited = [False] * 100 # 2. Using the list generator to generate a two-dimensional list with an initial value of 0 visited = [[0 for i in range (m)] for j in range (n)]

2.2 in python, a string cannot be modified in place. If a new string is generated for each modification, it will cost a lot of money if the string is modified many times and the string is appropriate. So it is common to change the string into a list, modify it and then turn it back.

String ='I love to eat chicken' # converts a string into a list string_list = list (string) #. Modify the list of strings # Code # reassemble the list of strings into the string # string =''.join (string_list)

2.3 there are many different ways to traverse the list in python, the most direct way is to iterate through the list directly, but because we often operate on the array based on the index and need to modify the value of the array, it is more recommended to use the second and third methods in the following code:

Num_list = [i for i in range (10)] # 1. Directly iterate over the list for item in num_list: # Code pass # 2. Iterate through index for i in range (len (num_list)): print (num_ list [I]) # 3. Iterate for index through the enumerate function. Value in enumerate (num_list): # index is the index of the current element, and value is the value print (index, value) of the current element.

3. The use of collections library

3.1 deque queue

Deque is the queue in python (FIFO first-in, first-out), and the queue will pop up faster than list in the first pop-up of the queue.

Especially when using BFS (depth first search), queues must be used. Some of the deque usage codes are as follows:

From collections import deque # initialize a queue with a maximum length of 3, d = deque ([1 mine2), maxlen=3) # because the maximum length of the initialization queue is 3 Adding more elements will squeeze the queue header element out of d.append (4) # initialize a queue of unlimited length d = deque () # add an element to the end of the queue d.append (1) d.append (2) d.append (3) # Pop the first element back to print (d.popleft ()) # pop the queue tail element and return the value print (d.pop ()) # Insert element d.appendleft (0) at the head of the line

3.2 Counter counter

Counter is a counter that counts a sequence and calculates the number of elements that appear in the sequence.

The following is the sample code:

There are three initial methods for import collections # 1. Pass in a sequence print (collections.Counter (['await,' baked, 'cached,' averse, 'baked,' b'])) # 2. Pass in a dictionary print (collections.Counter ({'axiavel2,' bounded VOL3, 'cantilever1})) # 3. Directly using = passing parameters print (collections.Counter (axi2, bao3, cym1)) # can also be constructed without parameters. Use the update function to update c = collections.Counter () print ('Initial:', c) # Initial: Counter () c.update ('abcdaab') print (' Sequence:', c) # Sequence: Counter ({'averse: 3,' baked: 2, 'cantilevered: 1,' dumped: 1}) c.update ({'avell1,' dazzl5}) print ('Dict:', c) # Dict: Counter ({' dudes: 6) ) # you can access the Counter object for letter in 'abcde': print ('% s:% d'% (letter) by accessing the dictionary C [letter]) # elements () method can return an iterator that contains all Counter data c = collections.Counter ('extremely') c [' z'] = 0 print (list (c.elements () # ['esigned,' eyed, 'masked,' lumped, 'rented,' tasked,'y' 'x'] # most_common () returns the first n most data c=collections.Counter ('aassdddffff') for letter, count in c.most_common (2): print ('% s:% d'% (letter, count)) # f: 4 # d: 3 # Counter objects can be added and subtracted Using the operators +, -, &, and | # + directly adds up the number of occurrences of the same character in the two dictionaries, and-gives the difference of the first Counter relative to the second. The intersection gives the elements in both counters, and the count is assigned to the smaller one, and the element that combines the two counters appears the most. C1 = collections.Counter (['averse,' baked, 'caged,' baked,'b']) c2 = collections.Counter ('alphabet') print (' C1 print, C1) print ('C2 print') C2) print ('\ nCombined counts:') print (C1 + c2) print ('\ nSubtraction:') print (C1-c2) print ('\ nIntersection (taking positive minimums):') print (C1 & c2) print ('\ nUnion (taking maximums):') print (C1 | c2) # the following is the output: C1: Counter ({'baked: 3,' asides: 2, 'cations: 1}) C2: Counter ({' astat2: 2, 'lumped: 1) ) Combined counts: Counter ({'averse: 4,' baked: 4, 'cession: 1,' lump: 1, 'pinch: 1,' hinge: 1, 'eBay: 1,' taper: 1}) Subtraction: Counter ({'baked: 2) ) Intersection (taking positive minimums): Counter ({'averse: 2,' baked: 1}) Union (taking maximums): Counter ({'baked: 3,' ajar: 2, 'cantilever: 1,' lump: 1, 'pinch: 1,' hinge: 1, 'eBay: 1,' taper: 1})

3.3Dictionary with default values for defaultdict--

In general, the dictionary dict created does not contain the default value, that is, if the dictionary does not contain the key of a, an error will be reported when calling dct {a}.

In algorithm design and data structure design, we hope that any given key can extract the value from the dictionary, even if it is only a default value, at this time we need to use defaultdict.

For example, when using a dictionary to represent the connected nodes of a node in the diagram, we want to use this node as a key, and then the connected nodes form a list as its value. At this time, we can use defaultdict (list) to create a dictionary with the default value of the list.

The default value of # list is empty list list_dict = collections.defaultdict (list) # int. The default value is 0 int_dict = collections.defaultdict (int) print (list_dict ['a']) print (int_dict ['a']) # output: [] # output: 0

3.4 Summary

These are the ones that are often used to write algorithms and data structures in collection, while others such as sort dictionaries and named tuples are rarely used.

4. Sort

4.1 sort the list

There are two ways to sort the list, one is to use the built-in sort function of the list, the sort function is modified directly in the list, no return value is returned, and you can customize the comparison key and comparison function through the parameter key.

The second is to use the sorted function of python, which has a high degree of freedom. You can set the comparison function and the key of the comparison, and return a new list.

If you need to customize the comparison function, you need to import the cmp_to_key function from the library functools, and convert the comparison function to key. The code is as follows:

Def custom_sort (XMagol y): if x > y: # return-1 indicates that return-1 if x needs to be ranked first.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.