Python's list is a variable linear list.
len() is O(1) operation
Element access and assignment, tail join and tail deletion (including tail slice deletion) are all O(1) operations.
General position element addition, slice replacement, slice deletion, and table splicing (extend) are all O(n) operations.
The pop operation defaults to delete the end element of the table and return it to O(1), specifying the non-tail position as O(n) time complexity.
lst.clear() Clear all elements of the table lst O(1) operation. Two ways to achieve:
a. The element count value (table length) is set to 0. The implementation is simple and the operation efficiency is high, but the occupied storage cannot be truly released. If the table is very long, there will be no elements in the table after the operation is performed, but the original large block of memory will still be occupied.
b. Another storage area for an empty table is allocated, and the original storage area is directly discarded. If the table grows again, the storage area will be frequently replaced.
lst.reverse() Modify the table lst itself, the order of the elements is reversed O(n)
def reverse(self):
elems = self.elements
i, j =0,len(elems)-1while i < j：
elems[i], elems[j]= elems[j], elems[i]
i, j = i+1, j-1
sortsort, the average and worst-case time complexity of the best sorting algorithm is O(nlogn)
## Link table
### condition
1. The first element in the table can be found.
2. Starting from any element, you can find the next element.
### Single list
- definition
``` python
classLNode:
def __init__(self, elem, next_= None):
self.elem = elem
self.next = next_
Stack, also known as stack, is a linear table with limited operations. The limitation is that only insert and delete operations are allowed at one end of the table.
The section that allows insertion and deletion is called the top of the stack (top),The other end is called the bottom of the stack (bottom)
The bottom of the stack is fixed, and the top of the stack is floating.
When the number of elements in the stack is zero, it is calledEmpty stack. Insertion is generally calledPush into the stack (PUSH), Delete is calledUnstack (POP)。
Last In First Out (LIFO, Last In First Out),Last in, first out table.
The time complexity of stacking and unstacking are both O(1)
classStack(Object):
def __init__(self, limit=10):""" creates an empty stack
"""
self.stack =[] # Store elements
self.limit = limit # stack capacity limit
def push(self, data): """ adds the element data to the stack, also often called push or push
"""
# Determine whether the stack overflows
iflen(self.stack)>= self.limit:
raise IndexError('The maximum capacity of the stack is exceeded!')
self.stack.append(data)
def pop(self):""" deletes the last element pushed in the stack and returns it, often called popping.
"""
if self.stack:return self.stack.pop()else:
rasie IndexError('pop from an empty stack')
def top(self):""" Get the last (top) element pushed in the stack without deleting it.
"""
if self.stack:return self.stack[-1]
def is_empty(self): """ Determine whether the stack is empty, return True when it is empty, otherwise return False
"""
return not bool(self.stack)
def size(self):""" Get the number of elements in the stack
"""
returnlen(self.stack)
"""
Use a stack to check if the bracket string is balanced
A valid bracket string must satisfy:
The opening bracket must be closed with the same type of closing bracket.
The opening parenthesis must be closed in the correct order.
Note that an empty string can be considered a valid string.
Example: ((())):True((()):False(())): False
"""
import stack
st = stack.Stack()
input_str ="(()"for s in input_str:if st.top()== s:
st.pop()else:
st.push(s)
result = True if st.is_empty()else False
print(result)
Recommended Posts