Tally up the useful py library function | Python theme

This article is participating in Python Theme Month. See the link for details

preface

A lot of people have the impression that PY has a lot of three-party libraries and a lot of functions that can be called directly, so the code as a whole is very short.

This article takes stock of those good built-in library functions, the use of good will be very easy, with Leetcode to eat better.

collections

This module implements target-specific containers to provide alternatives to Python’s standard built-in containers dict, list, set, and tuple.

Counter

Handy Counter, capitalized, Counter. Normally, if we want to count a set of elements, we have to create a new empty object, and then loop through the elements, which should be at least five lines. Using Counter, it’s easy. Like this

>>> import collections
>>> c = collections.Counter([3.1.2.3.1.4.4.4])
>>> c
Counter({4: 3.3: 2.1: 2.2: 1})
>>> c[4] // Direct access4Number of occurrences3
Copy the code

Acceptable arguments to Counter can be iterable or mapping, for example:

>>> from collections import Counter
>>> c = Counter('gallahad') // Accepts a string of iterable types>>> c
Counter({'a': 3.'l': 2.'g': 1.'h': 1.'d': 1})

>>> c = Counter({'red': 4.'blue': 2} // accept a mappingCopy the code

When you access a key that doesn’t exist in Counter, it returns 0, perfectly reasonable.

The Counter object can use dictionary methods. There is also the most_common() method, which directly specifies the n elements that occur most frequently.

By the way, if n is greater than the entire count length,

>>> Counter('abracadabra').most_common(3)
[('a'.5), ('b'.2), ('r'.2)]
Copy the code

Subtract one counter from the other, resulting in a negative number and zero

Update (iterable or mapping), as opposed to add.

>>> c = Counter(a=4, b=2, c=0, d=-2)
>>> d = Counter(a=1, b=2, c=3, d=4)
>>> c.subtract(d)
>>> C //c count minus d, c goes Counter({'a': 3.'b': 0.'c': -3.'d': -6})
Copy the code

Is the most ridiculous, can also directly use mathematical operators, including + – | &.

c = Counter(a=3, b=1)
d = Counter(a=1, b=2)
c + d                       # stack
Counter({'a': 4.'b': 3})
c - d                       # subtraction
Counter({'a': 2})
c & d                       # and, take small
Counter({'a': 1.'b': 1})
c | d                       Values negative and 0 are filtered out above
Counter({'a': 3.'b': 2})
Copy the code

Leetcode combat: 1207. Unique occurrences

Give you an integer array arr, ask you to help count the occurrence of each number in the array.

Returns true if each occurrence is unique; Otherwise return false.

[C] Counter [D] Counter 2 rows are done.

class Solution:
    def uniqueOccurrences(self, arr: List[int]) - >bool:
        c=collections.Counter(arr)
        return len(c)==len(set(c.values()))
Copy the code

deque

Double-ended queues, adding and removing elements from both ends is O (1) faster than list, which has o(n) insertion and deletion in the header.

In addition to methods that can make a list, there are

Appendleft (x) // add x to left popleft()// Remove and return the first left element rotate(n=1) / /... We cycle n steps to the right. If n is negative, we loop to the left. If the deque is not empty, a circular step to the right is equivalent to d.append(d.pop ()), and a circular step to the left is equivalent to d.append(d.popleft()). .Copy the code

Maxlen defines the maximum length of the queue. You can specify the maximum length with parameters at initialization so that the queue forms a natural data structure that holds the most recently used records.

collections.deque([iterable[, maxlen]])

>>> from collections import deque
>>> d = deque([1.2.3].4) // Initialize>>> d
deque([1.2.3], maxlen=4)
>>> d.appendleft(4) // Left side join>>> d
deque([4.1.2.3], maxlen=4)
>>> d[0]
4
>>> d.append(5) // When the number of elements exceeds the maximum, the left element is automatically eliminated.>>> d
deque([1.2.3.5], maxlen=4)
>>> D.popleft () // Left side of the output element1
>>> d
deque([2.3.5], maxlen=4)
Copy the code

Leetcode 3. Longest string without repeating characters

Given a string s, find the length of the smallest string that does not contain repeating characters.

This problem is a classic sliding window problem.

You can use a double-ended queue deque to simulate a sliding window. When encountering a character that already exists in the queue, the element is excluded from the left side of the queue until it stops at the same character as the character, and the queue length is compared to Max. It’s intuitive and easy to understand, but it’s not the fastest.

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: queue = collections.deque() if not s:return 0 res = 1 for s1 in s: if s1 in queue: Res = Max (res,len(queue)) while True: if queue. Popleft () == s1: Append (s1) res = Max (res,len(queue)) return resCopy the code

Deque is very practical, there are 102 binary tree level traversal, 103 binary tree sawtooth level traversal, 127 words solitons, 144, LRU cache mechanism. That’s how the tuning function works.

defaultdict

Use the collections. Defaultdict ([default_factory [,…]])

Returns a dictionary-like object with a value of the specified type.

This is usually set to defaultdict(int) or defaultdict(list), which defaults to 0 and [].

>>> s = 'mississippi'
>>> d = defaultdict(int) // is equal to the specified default key value is0
>>> for k in s:
	d[k]+=1// save the process of determining that there is no key in d>>> d
defaultdict(<class 'int'>, {'m': 1.'i': 4.'s': 4.'p': 2})
Copy the code

OrderedDict

Ordered dictionaries. Prior to 3.5, regular dictionaries had unordered keys and were prone to problems during iteration.

After 3.6, however, OrderedDict is no longer needed because it is similar to js and Java maps

namedtuple

Namespaces, named tuples, give each location a meaning, provide readability and self-documentation. They can be used with any normal tuple and add the ability to get a value by name, as well as by index value.

>>> from collections import namedtuple
>>> Point = namedtuple('Point'['x'.'y'])
>>> p = Point(11.22)
>>> p
Point(x=11, y=22)
>>> p[0]+p[1]
33
>>> P.x +p.y // Two access modes are supported33
Copy the code

Well, it’s kind of like a struct in C.

itertools

Divine iterators, you name it.

accumulate

Pass in an iterable, an arithmetic operation, the default addition is the accumulator, and return an iterator.

>>> from itertools import accumulate
>>> accumulate([1.2.3.4] // return the iterator <itertools.accumulateobject at 0x000001DFD2BDFEC0>
>>> list(accumulate([1.2.3.4]) //list
[1.3.6.10]
>>> list(accumulate([1.3.2.4.6.5].max) // Current maximum value [1.3.3.4.6.6]
>>> import operator
>>> list(accumulate([1.3.2.4.6.5], operator.mul)) //1.3.6.24.144.720]
Copy the code

chain

As the name suggests, to connect multiple iterable things in an orderly fashion. I don’t have to write multiple loops.

>>> list(itertools.chain('abc'.'efg'.'hij'))'a'.'b'.'c'.'e'.'f'.'g'.'h'.'i'.'j']
Copy the code

combinations

The difference between a combination and a real combination is that elements with the same value are treated as different and therefore repeat.

itertools.combinations(iterable, r)

>>> list(itertools.combinations('ABCD'.2) // Returns a tuple [('A'.'B'), ('A'.'C'), ('A'.'D'), ('B'.'C'), ('B'.'D'), ('C'.'D')]
>>> list(itertools.combinations('dcba'.2// The occurrence order is related to the sequence order.'d'.'c'), ('d'.'b'), ('d'.'a'), ('c'.'b'), ('c'.'a'), ('b'.'a')]
>>> list(itertools.combinations(range(4),3[())0.1.2), (0.1.3), (0.2.3), (1.2.3)]
Copy the code

By the way, math.b () evaluates combinations,

>>> import math
>>> math.comb(10.2) // C(10.2) = =10*9/2= =45
45
Copy the code

permutations

All arranged. Use the itertools. ` ` permutations (iterable, r = None)

>>> from itertools import permutations
>>> list(permutations('DCBA'.2// The order is related to the sequence of arguments [('D'.'C'), ('D'.'B'), ('D'.'A'), ('C'.'D'), ('C'.'B'), ('C'.'A'), ('B'.'D'), ('B'.'C'), ('B'.'A'), ('A'.'D'), ('A'.'C'), ('A'.'B')]
>>> list(permutations(range(3// The second parameter defaults to the longest [(0.1.2), (0.2.1), (1.0.2), (1.2.0), (2.0.1), (2.1.0)]
Copy the code

Actual combat: Leetcode 46 full permutations, 39 combinations total.

In fact, direct tuning library lost the meaning of the brush itself, not recommended.

product

Returns cartesian coordinates.

itertools.product(*iterables, repeat=1)

>>> list(itertools.product('abc'.range(2[()))'a'.0), ('a'.1), ('b'.0), ('b'.1), ('c'.0), ('c'.1)]
Copy the code

A: What’s your leetcode for a phone number

Given a string containing only the numbers 2-9, return all the letter combinations it can represent. The answers can be returned in any order.

Solution: in fact, it is pinyin 9 built, according to the number can hit all letter possibilities. Combinatorial problems, recursion, backtracking.

Do this using itertools.product, not very readable, but very short.

class Solution:
    def letterCombinations(self, digits: str) - >List[str] :
        b = {"2":"abc"."3":"def"."4":"ghi"."5":"jkl"."6":"mno"."Seven":"pqrs"."8":"tuv"."9":"wxyz"}
        return [] if digits == "" else [ "".join(x) for x in itertools.product(*(b[d] for d in digits ))]
Copy the code

zip_longest

Create an iterator to collect elements from each iterable. If the length of the iterable is not aligned, the missing value is filled in according to fillValue. Iteration continues until the longest iterable is exhausted.

itertools.zip_longest(*iterables, fillvalue=None)

>>> list(itertools.zip_longest('ABCD'.'xy', fillvalue='0'// can be used to complete [()'A'.'x'), ('B'.'y'), ('C'.'0'), ('D'.'0')]
Copy the code

If zip_longest is the longest thief, I can’t find it. 415 String addition

Zip and *

The zip() aggregation comes from the elements in each iterable and returns an iterator.

The iterator stops iterating when the shortest of the input iterables is exhausted.

>>> list(zip('ABCD'.'xy'[())'A'.'x'), ('B'.'y')]
Copy the code

* Unpack iterables, as opposed to… The rest of the operators look alike.

>>> a, *b, c = range(5// Is it not an ES6 structure assignment>>> b
[1.2.3]
>>> list(zip(* (zip('ABCD'.'xy'))))// Press first, then solve, then press [('A'.'B'), ('x'.'y')]
Copy the code

Use * to unpack the zip object directly, with all the items as arguments

This thing is very useful, for example 14. Longest public prefix

Write a function to find the longest public prefix in an array of strings. No common prefix exists, return “”.

Input: STRS = ["flower"."flow"."flight"] output:"fl"
Copy the code

class Solution:
    def longestCommonPrefix(self, strs: List[str]) - >str:
        out_str = ' '
        for i in zip(* STRS):// Unpack the array and press all items as parametersif len(set(i)) == 1: / / equal to zero1All elements in I are the same, which is the common prefix out_str += I [0]
            else:
                break
        return out_str
Copy the code

Can also be used to rotate the matrix:

>>> matric = [	[1.2.3],
		[4.5.6],
		[7.8.9]]
>>> list(zip(*matric[::-1)) // clockwise [(7.4.1), 
(8.5.2), 
(9.6.3)]
>>> list(zip(*matric))[::-1] // counterclockwise [(3.6.9), 
(2.5.8), 
(1.4.7)]
Copy the code

heapq

Built-in heap of data structures

Call mode is a little strange, personally feel pretty strange.

import heapq
h = [3.1.2.6.5.4]
>>> Heapq.heapify (h)// Change l to heap in place and return nothing>>> h
[1.3.2.6.5.4]
>>> Heapq.heappop (h) // Take the top element of the heap and adjust it automatically1
>>> h
[2.3.4.6.5]
>>> heapq.heappush(h,1// Add elements and adjust>>> h
[1.3.2.6.5.4]
Copy the code

Leetcode.215. Find the KTH largest element in the array

Leetcode means offer40, the smallest k number

Analysis: to find the maximum or minimum number of K, we can use the method of heap construction to solve.

The smallest number of k requires a big top heap, and the largest number of K requires a small top heap.

class Solution:  //40Antithesis methoddef getLeastNumbers(self, arr: List[int], k: int) - >List[int] :
        if k == 0:
            return list()

        hp = [-x for x inHeapq.heapify (HP) [:k]] [:k] [:k]] [:k] [:k]]for i in range(k, len(arr)):
            if hp[0Heapq. Heappop (HP) heapQ. Heappush (HP, -arr[I]); ans = [-xfor x inHP] // get the maximum number of k, take the negative number to get the minimumreturnAns // source: LeetCodeCopy the code

conclusion

That’s what I learned in my life. Give it a thumbs up. Ball ball.