[implement algorithm using Python] 02 native types and built-in functions

【 Use  Python  Implementation algorithm 】 Catalog

• 01  Linguistic characteristics

• 02  Native types and built-in functions

The topic of this issue is  Python  Some skills of the native types and built-in functions in algorithm implementation , First, from the most common  Python  Native type start .

int

int Type has two built-in methods bit_count And bit_length, Respectively used to obtain the binary expression of integers 1 The number and binary digits of , It is very practical in many scenarios .
n = 9
assert n.bit_count() == 2
assert n.bit_length() == 4


float

float Of as_integer_ratio Method can obtain the simplest fractional expression of floating point numbers .
f = 6.125
assert f.as_integer_ratio() == (49, 8)

utilize f-string You can easily get a string representation of a floating-point number with a specified number of decimal places .
assert f"{1/3:.4f}" == "0.3333"


list

list Of pop Method to receive an integer parameter  n,  Go back and delete the... In the list  n  Elements （O(n) Time complexity of , The efficiency is not high ）.
arr = [1, 2, 3]
assert arr.pop(1) == 2
assert arr == [1, 3]

Stack structure is often used in algorithm implementation ,Python  Of  list  The native type has all the functions of the stack , You can also simply package it , Define your own  Stack  type .
class Stack(list):
 push = list.append
 top = lambda l: l[-1]
 empty = lambda l: not l


tuple

tuple The frequency of using type in algorithm implementation is not very high , however list The type is not hashable （ Can't be a dictionary key ）, In this kind of scenario, you can list Convert to tuple After use .

dict

dict Of fromkeys Method can be used to initialize a dictionary with the same default value .
counter = dict.fromkeys("abc", 0)

for ch in "abccaaa":
 counter[ch] += 1

assert counter == {"a": 4, "b": 1, "c": 2}

initialization dict Another common method of using dictionary derivation is to use dictionary derivation .
counter = {ch: count for ch, count in [("a", 1), ("b", 2), ("c", 3)]}
assert counter == {"a": 1, "b": 2, "c": 3}


set

Python  Of set Type native supports the use of common operators for collection operations .
a, b = set([1, 2, 3]), set([2, 3, 4])
assert a & b == {2, 3} #  intersection
assert a | b == {1, 2, 3, 4} #  Combine
assert a - b == {1} #  Difference set
assert {2, 3} < a #  Subset judgment
assert a > {1} #  Super set judgment


str

There are a large number of algorithm problems related to strings and their processing ,Python  Of str Types have a large number of built-in methods for various purposes , It is mainly divided into three types .

Check the string type

str.isalnum #  Is it a letter or a number
str.isalpha #  Is it a letter
str.isascii #  Whether to belong to ASCII Character set
str.isdecimal #  Whether it is a decimal value digit
str.isdigit #  Is it a number , Support others Unicode Numbers , for example "①"
str.isidentifier #  Is it Python keyword
str.islower #  Lowercase or not
str.isnumeric #  Is it a number , Including some Unicode Numbers , for example "½"
str.isprintable #  Whether it is a printable character
str.isspace #  Whether it is a space
str.istitle #  Whether it is the title （ A capital letter followed by 0 And more small letters ）
str.isupper #  Is it a capital letter


Returns a new string based on the content

str.translate #  Use a mapping relationship to convert strings
assert "acbbc".translate(str.maketrans("abc", "xyz")) == "xzyyz"

str.replace #  Replace substring
str.upper #  Turn capitalization
str.lower #  Turn lowercase

str.zfill #  Left filling 0
assert "abc".zfill(5) == "00abc"

str.capitalize #  title case , Other letters are lowercase
assert "aBC cAA".capitalize() == "Abc caa"

str.titie #  Capitalize the first letter of each word , Other letters are lowercase
assert "aBC cAA".title() == "Abc Caa"

str.swapcase #  Capitalize to lowercase , Lowercase to uppercase
assert "aBC cAb".swapcase() == "Abc CaB"


Split into multiple substrings

str.split #  Splits the string using the specified separator
str.splitline #  Split string by newline

str.partition #  Splits the string into three segments using the specified delimiter
assert "A B C".partition(" ") == ("A", " ", "B C")

Besides, there are str.join Method , You can combine multiple strings into one with the specified delimiter .

complex

Python  Native provides plural types complex, And support common arithmetic operations .
c = complex(1, -1)
assert c.real == 1
assert c.imag == -1

assert complex(1, 1) * complex(1, -1) == 2



The theme of the second part of this issue is  Python  Built in functions for , The built-in functions are divided into object classes and containers according to their parameter types and return types （ iterator ） class .

Object class

The built-in functions of object classes mainly involve the processing of specific types of objects .

abs

Calculate the absolute value .

max, min

Return multiple values （ Or an iteratable object ） Maximum or minimum of .

chr, ord

Numbers and  ASCII  The conversion of characters .
chr(ord("a") + 1) == "b"


divmod

Simultaneously obtain quotient and remainder of integer division operation .
assert divmod(5, 2) == (2, 1)


hex

Gets the hexadecimal representation of an integer .
assert hex(255) == "0xff"


pow

Exponentiation .
assert pow(2, 3) == 8


round

Floating point rounding （ Round to the nearest pair ）.
assert round(1.2) == 1
assert round(1.6) == 2
assert round(1.5) == 2
assert round(2.5) == 2


Containers 、 Iterator class

Containers 、 The built-in functions of the iterator class are used to process and generate various container objects and iterator objects .

all

Returns when all elements are true True
assert all(x < 10 for x in [1, 2, 3])
assert not all(x < 10 for x in [1, 2, 3, 11])


any

Returns when any element is true True
assert any(x < 10 for x in [11, 9, 12])
assert not any(x < 10 for x in [11, 12, 13])


next

Get the next element of the iteratible object , It is often used to get the elements that meet the conditions ( To prevent the absence of qualified elements , It can be followed by an all inclusive value ).
assert next(x for x in range(1, 10) if x % 3 == 0) == 3
assert next(itertools.chain((x for x in [1, 2, 4, 7] if x % 3 == 0), iter([-1]))) == -1


enumerate

Traversal container , Returns a generator that iterates over the index and value （ Generally used in  for  In circulation ）.
assert dict(enumerate("abc")) == {0: "a", 1: "b", 2: "c"}

for index, ch in enumerate("abc"):
 pass


map

Apply the specified function to each value of the container , Return to a generator （ Not a list ）. List derivation is generally used instead of map function , More efficient .

filter

Test each value of the container with the specified function , Filter out the elements whose function value is true , Return to a generator （ Not a list ）.

range

Get the iteratable integer interval .

sum

Get the sum of all elements of the container or iteratable object

sorted

Sort the values of iteratable objects , Return a list , Sorting method can be specified , You can return to the reverse order list .
assert sorted(range(10), key=lambda x: x % 3) == [0, 3, 6, 9, 1, 4, 7, 2, 5, 8]
assert sorted([1, 3, 5, 2, 4], reverse=True) == [5, 4, 3, 2, 1]


zip

Pass in multiple iteratable objects , Combine the elements of the same index of each parameter in order into one tuple Object iteration generation .
assert list(zip(range(4), "abcd")) == [(0, "a"), (1, "b"), (2, "c"), (3, "d")]

have access to  zip  Method to transpose the matrix .
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
assert [list(row) for row in zip(*matrix)] == [[1, 4, 7], [2, 5, 8], [3, 6, 9]]


summary

Python  The native types and built-in functions of are very powerful , It is worth studying in depth .