数据结构

高级数据结构搭建

1. Trie树

class TrieNode():
    def __init__(self):
        self.is_end = False
        self.child = [0]*26
        
class TrieTree():
    def __init__(self, root):
        self.root = root
        
    def insert(self, word):
        p = self.root
        for x in word:
            idx = ord(x)-ord('a')
            if p.child[idx] == 0:
                p.child[idx] = TrieNode()
            p = p.child[idx]
        p.is_end = True
        
    def search(self, word):
        p = self.root
        for x in word:
            idx = ord(x)-ord('a')
            if p.child[idx] == 0:
                return False
            p = p.child[idx]
        return p.is_end
    
    def startWith(self, word):
        p = self.root
        for x in word:
            idx = ord(x)-ord('a')
            if p.child[idx] == 0:
                return False
            p = p.child[idx]
        return True

def preOrderTrie(node, layer):
    for i in range(len(node.child)):
        if node.child[i] != 0:
            for j in range(layer):
                print('---', end='')
            if node.child[i].is_end:
                print(chr(i+ord('a'))+'<end>')
            else:
                print(chr(i+ord('a')))
            preOrderTrie(node.child[i], layer+1)

def getAllWordFromTrie(node, path, ans):
    for i in range(len(node.child)):
        if node.child[i] != 0:
            path += chr(i+ord('a'))
            if node.child[i].is_end:
                ans.append(path)
            getAllWordFromTrie(node.child[i], path, ans)
            path = path[:-1]

root = TrieNode()
n1 = TrieNode()
n2 = TrieNode()
n3 = TrieNode()
root.child[ord('a')-ord('a')] = n1
root.child[ord('b')-ord('a')] = n2
root.child[ord('e')-ord('a')] = n3
n2.is_end = True

n4 = TrieNode()
n5 = TrieNode()
n6 = TrieNode()
n1.child[ord('b')-ord('a')] = n4
n2.child[ord('c')-ord('a')] = n5
n3.child[ord('f')-ord('a')] = n6

n7 = TrieNode()
n8 = TrieNode()
n9 = TrieNode()
n10 = TrieNode()
n4.child[ord('c')-ord('a')] = n7
n4.child[ord('d')-ord('a')] = n8
n5.child[ord('d')-ord('a')] = n9
n6.child[ord('g')-ord('a')] = n10
n7.is_end = True
n8.is_end = True
n9.is_end = True
n10.is_end = True

n11 = TrieNode()
n7.child[ord('d')-ord('a')] = n11
n11.is_end = True

preOrderTrie(root, 0)
ans = []
getAllWordFromTrie(root, '', ans)
print(ans)
tree = TrieTree(root)
tree.insert('abdg')
print(tree.search('b'))
ans = []
getAllWordFromTrie(root, '', ans)
print(ans)

运行结果

a
---b
------c<end>
---------d<end>
------d<end>
b<end>
---c
------d<end>
e
---f
------g<end>
['abc', 'abcd', 'abd', 'b', 'bcd', 'efg']
True
['abc', 'abcd', 'abd', 'abdg', 'b', 'bcd', 'efg']

2. 并查集

class disJointSet():
    def __init__(self, n):
        self.idx = [i for i in range(n)]
        self.cnt = n
        self.size = [1]*n
        
    
    def find(self, p):
        while self.idx[p] != p:
            self.idx[p] = self.idx[self.idx[p]]
            p = self.idx[p]
        return p
    
    def union(self, p, q):
        pid = self.find(p)
        qid = self.find(q)
        if pid == qid:
            return 
        if self.size[pid] < self.size[qid]:
            self.idx[pid] = qid
            self.size[qid] += self.size[pid]
        else:
            self.idx[qid] = pid
            self.size[pid] += self.size[qid]
        self.cnt -= 1
        
d = disJointSet(8)
print(d.idx)
print('union(0,5)')
d.union(0,5)
print(d.idx)
print(d.find(0), d.find(5))
print('union(2,4)')
d.union(2,4)
print(d.idx)
print('union(0,4)')
d.union(0,4)
print(d.idx)
print(d.find(2), d.find(5))

运行结果

[0, 1, 2, 3, 4, 5, 6, 7]
union(0,5)
[0, 1, 2, 3, 4, 0, 6, 7]
0 0
union(2,4)
[0, 1, 2, 3, 2, 0, 6, 7]
union(0,4)
[0, 1, 0, 3, 2, 0, 6, 7]
0 0

3. 线段树

def buildSegmentTree(value, nums, pos, left, right):
    if right == left:
        value[pos] = nums[left]
        return 
    mid = (left + right) // 2
    buildSegmentTree(value, nums, 2*pos+1, left, mid)
    buildSegmentTree(value, nums, 2*pos+2, mid+1, right)
    value[pos] = value[2*pos+1] + value[2*pos+2]
    
def printSegmentTree(value, pos, left, right, layer):
    for i in range(layer):
        print('---', end='')
    print('[%d %d][%d]: %d' % (left, right, pos, value[pos]))
    if left == right:
        return 
    mid = (left + right) // 2
    printSegmentTree(value, 2*pos+1, left, mid, layer+1)
    printSegmentTree(value, 2*pos+2, mid+1, right, layer+1)

def sumRangeSegmentTree(value, pos, left, right, qleft, qright):
    if right < qleft or left > qright:
        return 0
    if left >= qleft and right <= qright:
        return value[pos]
    mid = (left + right) // 2
    return sumRangeSegmentTree(value, 2*pos+1, left, mid, qleft, qright) + \
        sumRangeSegmentTree(value, 2*pos+2, mid+1, right, qleft, qright)

def updataSegmentTree(value, pos, left, right, index, newValue):
    if left == index and left == right:
        value[pos] = newValue
        return 
    mid = (left + right) // 2
    if index <= mid:
        updataSegmentTree(value, 2*pos+1, left, mid, index, newValue)
    else:
        updataSegmentTree(value, 2*pos+2, mid+1, right, index, newValue)
    value[pos] = value[2*pos+1] + value[2*pos+2]
          
nums = [0,1,2,3,4,5]
value = [0]*(36)
buildSegmentTree(value, nums, 0, 0, len(nums)-1)
printSegmentTree(value, 0, 0, len(nums)-1, 0)
print(sumRangeSegmentTree(value, 0, 0, len(nums)-1, 2, 5))
updataSegmentTree(value, 0, 0, len(nums)-1, 2, 10)
printSegmentTree(value, 0, 0, len(nums)-1, 0)

运行结果

[0 5][0]: 15
---[0 2][1]: 3
------[0 1][3]: 1
---------[0 0][7]: 0
---------[1 1][8]: 1
------[2 2][4]: 2
---[3 5][2]: 12
------[3 4][5]: 7
---------[3 3][11]: 3
---------[4 4][12]: 4
------[5 5][6]: 5
14
[0 5][0]: 23
---[0 2][1]: 11
------[0 1][3]: 1
---------[0 0][7]: 0
---------[1 1][8]: 1
------[2 2][4]: 10
---[3 5][2]: 12
------[3 4][5]: 7
---------[3 3][11]: 3
---------[4 4][12]: 4
------[5 5][6]: 5

基础数据结构

二叉树遍历

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def print_tree(root):
    Q = [root]
    while Q:
        Q_temp = []
        while any(Q):
            node = Q.pop(0)
            if node:
                print(node.val, end=' ')
                Q_temp.append(node.left)
                Q_temp.append(node.right)
            else:
                print('NONE', end=' ')
                Q_temp.append(None)
                Q_temp.append(None)
        print()
        Q = Q_temp
        
def preOrder(root):
    p = root
    Q = []
    ans = []
    while p or Q:
        if p:
            Q.append(p)
            ans.append(p.val)
            p = p.left
        else:
            p = Q.pop()
            p = p.right
    return ans
            
def inOrder(root):
    p = root
    Q = []
    ans = []
    while p or Q:
        if p:
            Q.append(p)
            p = p.left
        else:
            p = Q.pop()
            ans.append(p.val)
            p = p.right
    return ans

def postOrder(root):
    p = root
    Q = []
    ans = []
    while p or Q:
        if p:
            Q.append(p)
            ans.append(p.val)
            p = p.right
        else:
            p = Q.pop()
            p = p.left
    return ans[::-1]

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
print_tree(root)
print(preOrder(root))
print(inOrder(root))
print(postOrder(root))

运行结果

4
2 6
1 3 5 7

[4, 2, 1, 3, 6, 5, 7]
[1, 2, 3, 4, 5, 6, 7]
[1, 3, 2, 5, 7, 6, 4]

链表

class Node():
    def __init__(self, val):
        self.val = val
        self.next = None

def build_list(num):
    for i, val in enumerate(num):
        if i == 0:
            head = Node(val)
            p = head
        else:
            p.next = Node(val)
            p = p.next
    return head

def print_list(head):
    while head:
        print(head.val, end=' ')
        head = head.next
    
def reverse_list(head):
    if not head:
        return head
    p = head.next
    head.next = None
    while p:
        temp = p.next
        p.next = head
        head = p
        p = temp
    return head

def quick_sort(head, tail=None):
    if not head or head==tail:
        return
    mid = head.val
    p1 = head
    p2 = head.next
    i = 0
    while p2 != tail:
        if p2.val < mid:
            p1 = p1.next
            p1.val, p2.val = p2.val, p1.val
        p2 = p2.next
    p1.val, head.val = head.val, p1.val
    quick_sort(head, tail=p1)
    quick_sort(p1.next, tail=None)
    return 

def find_kth_to_tail(head, k):
    if not head or k<=0:
        return None
    p1 = head
    p2 = head
    for i in range(k-1):
        if p1.next:
            p1 = p1.next
        else:
            return None
    while p1.next:
        p1 = p1.next
        p2 = p2.next
    return p2.val

def merge(head1, head2):
    if not head1:
        return head2
    if not head2:
        return head1
    nhead = None
    if head1.val <= head2.val:
        nhead = head1
        nhead.next = merge(head1.next, head2)
    else:
        nhead = head2
        nhead.next = merge(head1, head2.next)
    return nhead

head1 = build_list([1, 3, 4, 5, 9])
head2 = build_list([0, 2, 6, 7, 8])
head = merge(head1, head2)
print_list(head)

运行结果

0 1 2 3 4 5 6 7 8 9