CSP-python

¶Python语法

¶内置函数

sorted : 对于sorted而言,原来的列表不会改变,而list.sort会

In [1]: student_tuples = [
    ...: ...     ('john', 'A', 15),
    ...: ...     ('jane', 'B', 12),
    ...: ...     ('dave', 'B', 10),
    ...: ... ]

In [2]: sorted(student_tuples, key=lambda student: student[2])
Out[2]: [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

In [3]: sorted("This is a test string from Andrew".split(), \
    ...: key=str.lower)
Out[3]: ['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

In [4]: sorted(student_tuples, key=itemgetter(2))
    ...: [('dave', 'B', 10), ('jane', 'B', 12),
     ('john', 'A', 15)]
Out[4]: [('dave', 'B', 10), ('jane', 'B', 12),
 ('john', 'A', 15)]

In [5]: sorted(student_tuples, key=itemgetter(1,2))
    ...: [('john', 'A', 15), ('dave', 'B', 10),
     ('jane', 'B', 12)]#先对一排序,再对二排序
Out[5]: [('john', 'A', 15), ('dave', 'B', 10),
 ('jane', 'B', 12)]

ord 和 chr : 字符与其Ascii码的互相转化

In [1]: ord('a')
Out[1]: 97

In [2]: chr(97)
Out[2]: 'a'

eval : 可执行字符串命令

¶应用

对于列表a=[(1,2),(1,3),(2,3)]按照第一个元素从小到大排序,如果第一个元素则按照第二个元素从大到小排序

In [1]: a
Out[1]: [(0, 4), (0, 3), (1, 3), (2, 5), (2, 4)]

    ...: a=[(2,4),(2,5),(0,3),(1,3),(0,4)]
    ...: def mycmp(x,y):
    ...:     if x[0]<y[0]:
    ...:         return -1
    ...:     if x[0]>y[0]:
    ...:         return 1
    ...:     if x[0]==y[0]:
    ...:         if x[1]==y[1]:
    ...:             return 0
    ...:         elif x[1]<y[1]:
    ...:             return 1
    ...:         else:
    ...:             return -1
    ...: 
    ...: a.sort(key=cmp_to_key(mycmp))

In [2]: a
Out[2]: [(0, 4), (0, 3), (1, 3), (2, 5), (2, 4)]

¶数据结构

¶二叉树

¶形式最简单的二叉树

class Node: #树的节点类
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def display(tree): #中序遍历

    if tree is None: 
        return

    if tree.left is not None:
        display(tree.left)

    print(tree.data)

    if tree.right is not None:
        display(tree.right)

    return

def depth_of_tree(tree): #判断树的深度
    if tree is None:
        return 0
    else:
        depth_l_tree = depth_of_tree(tree.left)
        depth_r_tree = depth_of_tree(tree.right)
        if depth_l_tree > depth_r_tree:
            return 1 + depth_l_tree
        else:
            return 1 + depth_r_tree


def is_full_binary_tree(tree): # 判断是否为完全二叉树
    if tree is None:
        return True
    if (tree.left is None) and (tree.right is None):
        return True
    if (tree.left is not None) and (tree.right is not None):
        return (is_full_binary_tree(tree.left) and is_full_binary_tree(tree.right))
    else:
        return False

¶二叉搜索树

# 节点类
class Node:

    def __init__(self, label, parent):
        self.label = label
        self.left = None
        self.right = None
        self.parent = parent

    def getLabel(self):
        return self.label

    def setLabel(self, label):
        self.label = label

    def getLeft(self):
        return self.left

    def setLeft(self, left):
        self.left = left

    def getRight(self):
        return self.right

    def setRight(self, right):
        self.right = right

    def getParent(self):
        return self.parent

    def setParent(self, parent):
        self.parent = parent

# 二叉搜索树类
class BinarySearchTree:

    def __init__(self):
        self.root = None

    # 插入节点
    def insert(self, label):
        # 根据label创建新节点
        new_node = Node(label, None)
        # 如果树是空的
        if self.empty():
            self.root = new_node
        else:
            #如果树不是空的
            curr_node = self.root
            #通过迭代找到需要插入的位置
            while curr_node is not None:
                parent_node = curr_node
                if new_node.getLabel() < curr_node.getLabel():
                    curr_node = curr_node.getLeft()
                else:
                    curr_node = curr_node.getRight()
            #插入
            if new_node.getLabel() < parent_node.getLabel():
                parent_node.setLeft(new_node)
            else:
                parent_node.setRight(new_node)
            #设置父节点为该节点
            new_node.setParent(parent_node)
    # 查找是否存在该节点
    def getNode(self, label):
        curr_node = None
        #如果树是空的,直接返回None
        if(not self.empty()):
            #得到根
            curr_node = self.getRoot()
            # 迭代查找
            while curr_node is not None and curr_node.getLabel() is not label:
                if label < curr_node.getLabel():
                    curr_node = curr_node.getLeft()
                else:
                    curr_node = curr_node.getRight()
        return curr_node
    
    def delete(self, label):
        if (not self.empty()):
            #查找是否具有该节点
            node = self.getNode(label)
            #该节点存在
            if(node is not None):
                #没有子节点
                if(node.getLeft() is None and node.getRight() is None):
                    self.__reassignNodes(node, None)
                    node = None
                #只有右节点
                elif(node.getLeft() is None and node.getRight() is not None):
                    self.__reassignNodes(node, node.getRight())
                #只有左节点
                elif(node.getLeft() is not None and node.getRight() is None):
                    self.__reassignNodes(node, node.getLeft())
                #两个节点都有
                else:
                    #得到左节点的最大节点
                    tmpNode = self.getMax(node.getLeft())
                    #删除左节点的最大节点
                    self.delete(tmpNode.getLabel())
                    node.setLabel(tmpNode.getLabel())

    
    # 该函数获取树中的最大节点
    def getMax(self, root = None):
        if(root is not None):
            curr_node = root
        else:
            #We go deep on the right branch
            curr_node = self.getRoot()
        if(not self.empty()):
            while(curr_node.getRight() is not None):
                curr_node = curr_node.getRight()
        return curr_node
    # 该函数获取树中的最小节点
    def getMin(self, root = None):
        if(root is not None):
            curr_node = root
        else:
            #We go deep on the left branch
            curr_node = self.getRoot()
        if(not self.empty()):
            curr_node = self.getRoot()
            while(curr_node.getLeft() is not None):
                curr_node = curr_node.getLeft()
        return curr_node
    # 树是否为空
    def empty(self):
        if self.root is None:
            return True
        return False


    def __InOrderTraversal(self, curr_node):
        nodeList = []
        if curr_node is not None:
            nodeList.insert(0, curr_node)
            nodeList = nodeList + self.__InOrderTraversal(curr_node.getLeft())
            nodeList = nodeList + self.__InOrderTraversal(curr_node.getRight())
        return nodeList

    def getRoot(self):
        return self.root

    def __isRightChildren(self, node):
        if(node == node.getParent().getRight()):
            return True
        return False

    def __reassignNodes(self, node, newChildren):
        if(newChildren is not None):
            newChildren.setParent(node.getParent())
        if(node.getParent() is not None):
            #If it is the Right Children
            if(self.__isRightChildren(node)):
                node.getParent().setRight(newChildren)
            else:
                #Else it is the left children
                node.getParent().setLeft(newChildren)

    #This function traversal the tree. By default it returns an
    #In order traversal list. You can pass a function to traversal
    #The tree as needed by client code
    def traversalTree(self, traversalFunction = None, root = None):
        if(traversalFunction is None):
            #Returns a list of nodes in preOrder by default
            return self.__InOrderTraversal(self.root)
        else:
            #Returns a list of nodes in the order that the users wants to
            return traversalFunction(self.root)

    #Returns an string of all the nodes labels in the list
    #In Order Traversal
    def __str__(self):
        list = self.__InOrderTraversal(self.root)
        str = ""
        for x in list:
            str = str + " " + x.getLabel().__str__()
        return str

def InPreOrder(curr_node):
    nodeList = []
    if curr_node is not None:
        nodeList = nodeList + InPreOrder(curr_node.getLeft())
        nodeList.insert(0, curr_node.getLabel())
        nodeList = nodeList + InPreOrder(curr_node.getRight())
    return nodeList

def testBinarySearchTree():
    t = BinarySearchTree()
    t.insert(8)
    t.insert(3)
    t.insert(6)
    t.insert(1)
    t.insert(10)
    t.insert(14)
    t.insert(13)
    t.insert(4)
    t.insert(7)

    #Prints all the elements of the list in order traversal
    print(t.__str__())

    if(t.getNode(6) is not None):
        print("The label 6 exists")
    else:
        print("The label 6 doesn't exist")

    if(t.getNode(-1) is not None):
        print("The label -1 exists")
    else:
        print("The label -1 doesn't exist")

    if(not t.empty()):
        print(("Max Value: ", t.getMax().getLabel()))
        print(("Min Value: ", t.getMin().getLabel()))

    t.delete(13)
    t.delete(10)
    t.delete(8)
    t.delete(3)
    t.delete(6)
    t.delete(14)

    list = t.traversalTree(InPreOrder, t.root)
    for x in list:
        print(x)

¶线段树

import math

class SegmentTree:

    def __init__(self, A):
        self.N = len(A)
        self.st = [0] * (4 * self.N) # approximate the overall size of segment tree with array N
        self.build(1, 0, self.N - 1)

    def left(self, idx):
        return idx * 2

    def right(self, idx):
        return idx * 2 + 1

    def build(self, idx, l, r):
        if l == r:
            self.st[idx] = A[l]
        else:
            mid = (l + r) // 2
            self.build(self.left(idx), l, mid)
            self.build(self.right(idx), mid + 1, r)
            self.st[idx] = max(self.st[self.left(idx)] , self.st[self.right(idx)])

    def update(self, a, b, val):
        return self.update_recursive(1, 0, self.N - 1, a - 1, b - 1, val)

    def update_recursive(self, idx, l, r, a, b, val): # update(1, 1, N, a, b, v) for update val v to [a,b]
        if r < a or l > b:
            return True
        if l == r :
            self.st[idx] = val
            return True
        mid = (l+r)//2
        self.update_recursive(self.left(idx), l, mid, a, b, val)
        self.update_recursive(self.right(idx), mid+1, r, a, b, val)
        self.st[idx] = max(self.st[self.left(idx)] , self.st[self.right(idx)])
        return True

    def query(self, a, b):
        return self.query_recursive(1, 0, self.N - 1, a - 1, b - 1)

    def query_recursive(self, idx, l, r, a, b): #query(1, 1, N, a, b) for query max of [a,b]
        if r < a or l > b:
            return -math.inf
        if l >= a and r <= b:
            return self.st[idx]
        mid = (l+r)//2
        q1 = self.query_recursive(self.left(idx), l, mid, a, b)
        q2 = self.query_recursive(self.right(idx), mid + 1, r, a, b)
        return max(q1, q2)

    def showData(self):
        showList = []
        for i in range(1,N+1):
            showList += [self.query(i, i)]
        print(showList)


if __name__ == '__main__':
    A = [1,2,-4,7,3,-5,6,11,-20,9,14,15,5,2,-8]
    N = 15
    segt = SegmentTree(A)
    print(segt.query(4, 6))
    print(segt.query(7, 11))
    print(segt.query(7, 12))
    segt.update(1,3,111)
    print(segt.query(1, 15))
    segt.update(7,8,235)
    segt.showData()

¶图

n, m = map(int, input().split(" "))

# Initialising Dictionary of edges
g = {}
for i in range(n):
    g[i + 1] = []

"""
----------------------------------------------------------------------------
    Accepting edges of Unweighted Directed Graphs
----------------------------------------------------------------------------
"""
for _ in range(m):
    x, y = map(int, input().strip().split(" "))
    g[x].append(y)

"""
----------------------------------------------------------------------------
    Accepting edges of Unweighted Undirected Graphs
----------------------------------------------------------------------------
"""
for _ in range(m):
    x, y = map(int, input().strip().split(" "))
    g[x].append(y)
    g[y].append(x)

"""
----------------------------------------------------------------------------
    Accepting edges of Weighted Undirected Graphs
----------------------------------------------------------------------------
"""
for _ in range(m):
    x, y, r = map(int, input().strip().split(" "))
    g[x].append([y, r])
    g[y].append([x, r])

# 图的dfs遍历
def dfs(G, s):
    vis, S = set([s]), [s]
    print(s)
    while S:
        flag = 0
        for i in G[S[-1]]:
            if i not in vis:
                S.append(i)
                vis.add(i)
                flag = 1
                print(i)
                break
        if not flag:
            S.pop()
# 图的bfs遍历
from collections import deque


def bfs(G, s):
    vis, Q = set([s]), deque([s])
    print(s)
    while Q:
        u = Q.popleft()
        for v in G[u]:
            if v not in vis:
                vis.add(v)
                Q.append(v)
                print(v)
# 迪克斯特拉算法

def dijk(G, s):
    dist, known, path = {s: 0}, set(), {s: 0}
    while True:
        if len(known) == len(G) - 1:
            break
        mini = 100000
        for i in dist:
            if i not in known and dist[i] < mini:
                mini = dist[i]
                u = i
        known.add(u)
        for v in G[u]:
            if v[0] not in known:
                if dist[u] + v[1] < dist.get(v[0], 100000):
                    dist[v[0]] = dist[u] + v[1]
                    path[v[0]] = u
    for i in dist:
        if i != s:
            print(dist[i])

# 图的拓扑排序
from collections import deque


def topo(G, ind=None, Q=None):
    if Q is None:
        Q = [1]
    if ind is None:
        ind = [0] * (len(G) + 1)  # SInce oth Index is ignored
        for u in G:
            for v in G[u]:
                ind[v] += 1
        Q = deque()
        for i in G:
            if ind[i] == 0:
                Q.append(i)
    if len(Q) == 0:
        return
    v = Q.popleft()
    print(v)
    for w in G[v]:
        ind[w] -= 1
        if ind[w] == 0:
            Q.append(w)
    topo(G, ind, Q)

# kruskal
def krusk(E_and_n):
    (E, n) = E_and_n
    # 根据边的权值从大到小排序
    E.sort(reverse=True, key=lambda x: x[2])
    s = [set([i]) for i in range(1, n + 1)]
    while True:
        if len(s) == 1:
            break
        print(s)
        x = E.pop()
        for i in range(len(s)):
            if x[0] in s[i]:
                break
        for j in range(len(s)):
            if x[1] in s[j]:
                if i == j:
                    break
                s[j].update(s[i])
                s.pop(i)
                break

没什么时间来整理了,直接把代码放在一个压缩包里,到时候有用再看吧.

CSP-Python-ENV