分享本页
微信扫一扫浏览本页

在平坦的算法路上懵逼地曲折前进(二)

说来也怪,我写了许多文章都带了(一),但是好多都没有(二),今天我就寻思着更新一波——在平坦的算法路上懵逼地曲折前进(二)

一、链表

就像个火车

(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 calls11
len calls 11
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)

下一讲:并查集抽象数据类型、二叉树搜索

5

文章导览

评论

评论

2
微信二维码 扫一扫添加微信

我们注意到您的浏览器版本过低。本站需要在更现代的浏览器上才能充分展现,我们推荐您下载谷歌Chrome浏览器来浏览本站。

下载谷歌浏览器