说来也怪,我写了许多文章都带了(一),但是好多都没有(二),今天我就寻思着更新一波——在平坦的算法路上懵逼地曲折前进(二)
一、链表
就像个火车
(1)单向链表
class IntNode:
def __init__(self, i, n):
self.item = i
self.next = n
class SLList:
def __init__(self, x=None):
self.__sentinel = IntNode(1, None)
if x is None:
self.__first = None
self.__size = 0
else:
self.__sentinel.next = IntNode(x, None)
self.__size = 1
def add_first(self, x):
original_first = self.__sentinel.next
new_first = IntNode(x, original_first)
self.__sentinel.next = new_first
self.__size += 1
def add_last(self, x):
p = self.__sentinel
while p.next is not None:
p = p.next
p.next = IntNode(x, None)
self.__size += 1
def get_first(self):
return self.__sentinel.next.item
def size(self):
return self.__size
l = SLList()
l.add_last(2)
l.get_first()
(2)双向链表
class IntNode:
def __init__(self, i, n, p):
self.item = i
self.next = n
self.prev = p
class DLList:
def __init__(self, x=None):
self.__sentinel = IntNode(1, None, None)
self.__sentinel.next = self.__sentinel
self.__sentinel.prev = self.__sentinel
if x is None:
self.__size = 0
else:
new_node = IntNode(x, self.__sentinel, self.__sentinel)
self.__sentinel.next = new_node
self.__sentinel.prev = new_node
self.__size = 1
def add_first(self, x):
original_first = self.__sentinel.next
new_first = IntNode(x, original_first, self.__sentinel)
original_prev = new_first
self.__sentinel.next = new_first
self.__size += 1
def add_last(self, x):
p = self.__sentinel
while p.next is not None:
p = p.next
p.next = IntNode(x, None, p.next)
def get_first(self):
return self.__sentinel.next.item
def size(self):
return self.__size
l = DLList()
l.add_first(2)
l.add_last(4)
l.get_first()
(3)双守卫环形链表
class Node(object):
def __init__(self, i, n = None, p = None):
self.item = i
self.next = n
self.prev = p
class DLList():
def __init__(self, x=None):
self.__sentinel = Node(1, None, None)
self.__back_sentinel = Node(1, self.__sentinel, self.__sentinel)
self.__sentinel.next = self.__back_sentinel
self.__sentinel.prev = self.__back_sentinel
if x is not None:
original_node = self.__sentinel.next
new_node = Node(x, original_node, self.__back_sentinel)
self.__sentinel.next = new_node
self.__back_sentinel.prev = new_node
self.__size = 1
else:
self.__size = 0
def add_first(self, x):
original_first = self.__sentinel.next
new_first = Node(x , original_first, self.__sentinel)
original_first.prev = new_first
self.__sentinel.next = new_first
self.__size += 1
def get_first(self):
return self.__sentinel.next.item
def add_last(self, x):
original_last = self.__back_sentinel.prev
new_last = Node(x , original_last, self.__back_sentinel)
original_last.next = new_last
self.__back_sentinel.prev = new_last
self.__size += 1
def get_last(self):
return self.__back_sentinel.prev.item
def size(self):
return self.__size
l = DLList()
l.add_first(2)
l.add_first(3)
l.add_last(4)
二、抽象数据类型
(1)栈结构
- push(x) 将x放在栈的顶端
- pop() 将栈最上面的元素拿走并取出得到它的值
class Stack():
def __init__(self):
self.__data = []
def push(self, x):
self.__data.append(x)
def pop(self):
return self.__data.pop()
s = Stack()
s.push(1)
s.push(2)
s.pop()
(2)集合
class Set(object):
def __init__(self, data=[]):
self.__data = data
for item in data:
if item not in self.__data:
self.__data.append(item)
def add(self, x):
if x not in self._data:
self.__data.append(x)
def get_all(self):
return self.__data
三、渐近分析
- 对于一组已经排好序的array,寻找重复数字
def dup1(A):
for i in range(len(A)):
for j in range(i + 1, len(A)):
if A[i] == A[j]:
return True
return False
def dup2(A):
for i in range(len(A) - 1):
if A[i] == A[i + 1]:
return True
return False
operation | sym.count | count, N = 10000 |
range calls | 1 | 1 |
len calls | 1 | 1 |
i assignment | 1~N-1 | 1-9999 |
equals(==) | 1~N-1 | 1-9999 |
array accesses | 2~2N-2 | 1-19998 |
Simplification Summary
- 1. Only consider the worst case
- 2. Pick a representative operation(a.k.a. the cost model).
- 3. Ignore lower order terms.
- 4. Ignore multiplicative constants.
def add(self, x):
if x not in self._data:
self.__data.append(x)
operation | #call | worst case | best case |
not in | Θ(N) | Θ(N^2) | Θ(N) |
class Set(object):
def init(self, data=[]):
self.__data = data
for item in data:
if item not in self.__data:
self.__data.append(item)
operation | #call | worst case | best case |
not in | Θ(N) | Θ(N^2) | Θ(N) |
下一讲:并查集抽象数据类型、二叉树搜索
纬八路随笔
2020-04-28 20:59:33来拜访一下。
卷土
2020-05-01 15:24:36@纬八路随笔 感谢访问