OJ上机作业

002二进制转十进制

k=input()
k=int(k)
temp_str=''
while k>0:
    temp_str+=str(int(k%2))
    k=int(k/2)
print(temp_str[::-1])

003逢七就出

n=int(input())
circle=[i+1 for i in range(n)]
stack=[]
flag=0
while len(circle) is not 0:
    flag+=6
    flag=flag%len(circle)
    stack.append(circle.pop(flag))
for ii in stack:
    print(ii)

004归并排序

from math import floor

def merge(A,p,q,r):
    n1=q-p+1
    n2=r-q
    L=[i for i in range(n1+1)]
    R=[i for i in range(n2+1)]
    for i in range(n1):
        L[i]=A[p+i]
    for j in range(n2):
        R[j]=A[q+1+j]
    L[n1]=100000
    R[n2]=100000
    i=j=0
    for k in range(p,r+1):
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1

def merge_sort(A,p,r):
    if(p<r):
        q=floor((p+r)/2)
        merge_sort(A,p,q)
        merge_sort(A,q+1,r)
        merge(A,p,q,r)

k=input()
for i in range(int(k)):
    temp_str=input()
    temp_str=temp_str.split(" ")
    temp_list=[int(temp_str[i]) for i in range(len(temp_str))]
    merge_sort(temp_list,0,len(temp_list)-1)
    print(temp_list)

005快排

def partition(A,p,r):
    x=A[r]
    i=p-1
    for j in range(p,r):
        if A[j]<=x:
            i=i+1
            temp=A[i]
            A[i]=A[j]
            A[j]=temp
    temp=A[i+1]
    A[i+1]=A[r]
    A[r]=temp
    return i+1

def quick_sort(A,p,r):
    if p<r:
        q=partition(A,p,r)
        quick_sort(A,p,q-1)
        quick_sort(A,q+1,r)

k=input()
for i in range(int(k)):
    temp_str=input()
    temp_str=temp_str.split(" ")
    temp_list=[int(temp_str[i]) for i in range(len(temp_str))]
    quick_sort(temp_list,0,len(temp_list)-1)
    print(temp_list)

006递归应用—小青蛙跳台阶

global m
m=0
def jumper(n):
    global m
    if n>=1:
        jumper(n-1)
    if n>=2:
        jumper(n-2)
    if n==0:
        m+=1
k=int(input())
jumper(k)
print(m)

007递归实现——最大公约数

def gcd(m,n):
    if n==0:
        return m
    return gcd(n,m%n)

n=int(input())
for i in range(n):
    str1=input()
    temp=str1.split()
    temp=[int(i) for i in temp]
    m=max(temp)
    n=min(temp)
    print(gcd(m,n))

008栈的应用——括号匹配

stack=[]
k=input()
flag=1
for i in k:
    if i is '[' or i is '{' or i is '(':
        stack.append(i)
    elif i is ']' or i is '}' or i is ')':
        if len(stack)==0:
            flag=0
            break
        if stack[len(stack)-1] == '[' and i == ']':
            stack.pop(len(stack)-1)
        elif stack[len(stack)-1] == '{' and i == '}':
            stack.pop(len(stack)-1)
        elif stack[len(stack)-1] == '(' and i == ')':
            stack.pop(len(stack)-1)
        else:
            flag=0
            break
if len(stack)!=0:
    flag=0
if flag is 0:
    print('False')
else:
    print('True')

009二分查找问题

def binary_find(A,target):
    min_index=-1
    p=0 
    q=len(A)-1
    while q-p>0:
        if A[int((p+q)/2)]>target:
            q=(p+q)/2
        elif A[int((p+q)/2)]<target:
            p=(p+q)/2
        else:
            min_index=int((p+q)/2)
            while min_index>0 and A[min_index-1]==A[min_index]:
                min_index-=1
            break
    return min_index
   
n=int(input())
all_array=[]
for i in range(n):
    temp_str=input()
    temp_str=temp_str.split(',')
    A=[int(i) for i in temp_str]
    all_array.append(A)
for i in range(n):
    target=int(input())
    print(binary_find(all_array[i],target))

010建立哈希表并进行插入删除查找元素操作

class Node(object):
    def __init__(self,data,pnext=None):
        self.data=data
        self.next=pnext

class List_Node(object):
    def __init__(self):
        self.head=Node(-1)#头节点不放元素
        self.length=0
        
    def disp(self):
        node=self.head
        while node.next is not None:
            node=node.next
            print(node.data)
        
    def append(self,data):
        temp_Node=Node(data)
        node=self.head
        while node.next is not None:
            node=node.next
            if data == node.data:
                return
        node.next=temp_Node
        self.length+=1
            
    def delete(self,del_data):
        node=self.head
        pre_node=self.head
        while node.next is not None:
            node=node.next
            if del_data==node.data:
                pre_node.next=node.next
                self.length-=1
                return True
            pre_node=pre_node.next
        return False
    
    def find_data(self,i):
        node=self.head.next
        while node is not None:
            if node.data == i:
                return True
            node=node.next
        return False

m=int(input())
temp_str=input()
int_input=[int(i) for i in temp_str.split()]

hashT=[List_Node() for i in range(m)]
for i in int_input:
    index=i%m
    hashT[index].append(data=i)
      
n=int(input())
for i in range(n):
    num=int(input())
    index=num%m
    hashT[index].append(data=num)#插入
    
k=int(input())
for i in range(k):
    num=int(input())
    index=num%m
    if not hashT[index].delete(num):
        print('Delete Error')
          
j=int(input())
for i in range(j):
    num=int(input())
    index=num%m
    if hashT[index].find_data(num):
        print('True')
    else:
        print('False')

011递归应用——链表转置

def List_reverse(List,index):
    if index<len(List)-1:
        List_reverse(List,index+1)
    print(List[index])
          
length=input()
temp_str=input()
temp_str=temp_str.split(" ")
temp_list=[int(temp_str[i]) for i in range(len(temp_str))]
List_reverse(temp_list,0)

012递归应用——全排列

from math import factorial

def perm(List,flag,i,ans):
    if i==len(List):
        print(ans)
    else:
        for j in range(len(List)):
            if flag[j] is 0:
                ans[i]=List[j]
                flag[j]=1
                perm(List,flag,i+1,ans)
                flag[j]=0
                  
k=int(input())
List=[i+1 for i in range(k)]
flag=[0 for i in range(k)]
ans=[0 for i in range(k)]
perm(List,flag,0,ans)

014哈希应用—求同一条直线上的点的数量

max_num=0
class Node(object):
    def __init__(self,k,pnext=None):
        self.k=k
        self.num=1
        self.next=pnext

class List_Node(object):
    def __init__(self):
        self.head=Node(-1)#头节点不放元素
        self.length=0
        
    def disp(self):
        node=self.head
        while node.next is not None:
            node=node.next
            print(node.data)
        
    def append(self,k):
        global max_num
        temp_Node=Node(k)
        node=self.head
        while node.next is not None:
            node=node.next
            if k == node.k:
                node.num+=1
                max_num=max(node.num,max_num)
                return
        node.next=temp_Node
        self.length+=1
                  
hashT=[List_Node() for i in range(10)]

import math
num=int(input())
for i in range(num):
    temp=input()
    temp=[int(i) for i in temp.split()]
    temp_k=temp[0]/temp[1]
    hashT[math.floor(temp_k/10)].append(temp_k)
print(max_num)

015哈希应用——宝石计数

import math
class Node(object):
    def __init__(self,data,pnext=None):
        self.data=data
        self.next=pnext

class List_Node(object):
    def __init__(self):
        self.head=Node(-1)#头节点不放元素
        self.length=0
        
    def disp(self):
        node=self.head
        while node.next is not None:
            node=node.next
            print(node.data)
        
    def append(self,data):
        temp_Node=Node(data)
        node=self.head
        while node.next is not None:
            node=node.next
            if data == node.data:
                return
        node.next=temp_Node
        self.length+=1
        
    def find_data(self,i):
        node=self.head.next
        while node is not None:
            if node.data == i:
                return True
            node=node.next
        return False
                  
hashT=[List_Node() for i in range(10)]

temp_str=input()
cristal=[ord(i) for i in temp_str]
for i in cristal:
    hashT[i%10].append(i)
      
find_str=input()
find_cristal=[ord(i) for i in find_str]
num=0
for i in find_cristal:
    if hashT[i%10].find_data(i):
        num+=1 
          
print(num)

019构造二叉树并实现访问操作

class Node:
    def __init__(self,elem):
        self.elem=elem
        self.lchild=None
        self.rchild=None
class Tree:
    def __init__(self):
        self.root=None
    
    def add(self,data):
        if data=='#':
            data=None
        if self.root is None:
            self.root=Node(data)
            return
        queue=[]
        queue.append(self.root)
        while queue :
            cur_node=queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild=Node(data)
                return
            elif cur_node.rchild is None:
                cur_node.rchild=Node(data)
                return
            else:
                queue.append(cur_node.lchild)
                queue.append(cur_node.rchild)#广度优先
                
    def pre_order(self,node):
        if node==None:
            return
        print(node.elem)
        self.pre_order(node.lchild)
        self.pre_order(node.rchild)

if __name__=='__main__':
    
    temp_str=input()
    data_list=temp_str.split(' ')
    MyTree=Tree()
    if temp_str != '':
        for i in data_list:MyTree.add(i)
 
    N = int(input())
    for i in range(N):
        eval(input())

020二叉树的先序遍历

class Node:
    def __init__(self,elem):
        self.elem=elem
        self.lchild=None
        self.rchild=None
class Tree:
    def __init__(self):
        self.root=None
    
    def add(self,data):
        if data=='#':
            data=None
        if self.root is None:
            self.root=Node(data)
            return
        queue=[]
        queue.append(self.root)
        while queue :
            cur_node=queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild=Node(data)
                return
            elif cur_node.rchild is None:
                cur_node.rchild=Node(data)
                return
            else:
                queue.append(cur_node.lchild)
                queue.append(cur_node.rchild)#广度优先
                
    def pre_order(self):
        stack=[]
        if self.root.elem is not None:
            stack.append(self.root)
        while stack:
            cur_node=stack.pop()
            print(cur_node.elem)
            if cur_node.rchild is not None and cur_node.rchild.elem is not None:
                stack.append(cur_node.rchild)
            if cur_node.lchild is not None and cur_node.lchild.elem is not None:
                stack.append(cur_node.lchild)
                  
temp_str=input()
data_list=temp_str.split(' ')
MyTree=Tree()
for i in data_list:MyTree.add(i)
MyTree.pre_order()

021根据先序和中序遍历确定二叉树的后序遍历

class Node:
    def __init__(self,x):
        self.data=x
        self.left=None
        self.right=None
        
def lrd(x):
    if x is None:
        return
    if x.left:
        lrd(x.left)
    if x.right:
        lrd(x.right)
    print(x.data,end=' ')

def build_tree(pre_order, in_order):
    if len(pre_order) == 0:
        return
    elif len(in_order) == 1:
        return Node(in_order[0])
    
    root = pre_order[0]
    depth=in_order.index(root)
    
    if depth==0:
        in_order_1=[]
        in_order_2=in_order[1:]
    elif depth==len(pre_order)-1:
        in_order_1=in_order[0:(len(pre_order)-1)]
        in_order_2=[]
    else:
        in_order_1=in_order[0:depth]
        in_order_2=in_order[depth+1:]
    
    temp = Node(root)
    temp.left = build_tree(pre_order[1:depth+1], in_order_1)
    temp.right = build_tree(pre_order[depth+1:], in_order_2)
    return temp
    
first=input()
mid=input()
first=first.split()
mid=mid.split()

k=build_tree(first,mid)

lrd(k)

022根据二叉树的先序和中序遍历输出层序遍历

class TreeNode:
    def __init__(self,x):
        self.data=x
        self.left=None
        self.right=None
        
def bfs(x):
    if x is None:
        return
    queue=[]
    queue.append(x)
    while queue:
        node=queue.pop(0)
        print(node.data,end=' ')
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)

def build_tree(pre,mid,pre_s,pre_e,mid_s,mid_e):
    if pre_s>pre_e or mid_s>mid_e:
        return None
    root=pre[pre_s]
    head=TreeNode(root)
    mid_index=mid.index(root)
    left_length=mid_index-mid_s
    
    head.left=build_tree(pre,mid,pre_s+1,pre_s+left_length,mid_s,mid_index-1)
    head.right=build_tree(pre,mid,pre_s+left_length+1,pre_e,mid_index+1,mid_e)
    
    return head
    
first=input()
mid=input()
first=first.split(' ')
mid=mid.split(' ')
          
k=build_tree(first,mid,0,len(first)-1,0,len(first)-1)
bfs(k)

024同一二叉搜索树序列的判断

class Node:
    def __init__(self,data):
        self.elem=data
        self.left=None
        self.right=None
        
def append_node(num,node):
    if node.elem is None:
        node.elem=num
        return
    if num>node.elem:
        if node.right is not None:
            append_node(num,node.right)
            return
        else:
            node.right=Node(num)
    if num<node.elem:
        if node.left is not None:
            append_node(num,node.left)
            return
        else:
            node.left=Node(num)

def make_search_tree(A):
    if A is []:
        return Node(None)
    root=Node(A[0])
    for i in A[1:]:
        append_node(i,root)
    return root
flag=1
def compare(T,B):
    global flag
    if T is None and B is None:
        return
    if T is None and B is not None:
        flag=0
        return False
    if T is not None and B is None:
        flag=0
        return False
    if T.elem!=B.elem:
        flag=0
        return False
    compare(T.left,B.left)
    compare(T.right,B.right)
n=int(input())
sql=input()
A=[]
for i in sql:
    A.append(int(i))
one=make_search_tree(A)
for i in range(n):
    flag=1
    sql=input()
    B=[]
    for i in sql:
        B.append(int(i))
    root=make_search_tree(B)
    compare(one,root)
    if flag==0:
        print('NO')
    else:
        print('YES')

025验证二叉搜索树

class Node:
    def __init__(self,data):
        self.elem=data
        self.left=None
        self.right=None
class Tree:
    def __init__(self):
        self.root=None
        self.val=[]
    def init_tree(self,tree_list):
        if tree_list is []:
            return
        self.root=Node(tree_list.pop(0))
        queue=[]
        queue.append(self.root)
        while queue:
            node=queue.pop(0)
            if node.left is None and node.elem is not None and tree_list:
                if tree_list[0] == '#':
                    tree_list.pop(0)
                    node.left=Node(None)
                else:
                    node.left=Node(tree_list.pop(0))
                    queue.append(node.left)
            if node.right is None and node.elem is not None and tree_list:
                if tree_list[0] == '#':
                    tree_list.pop(0)
                    node.right=Node(None)
                else:
                    node.right=Node(tree_list.pop(0))
                    queue.append(node.right)
    def inorder(self,node):
        if node.left:
            self.inorder(node.left)
        if node and node.elem is not None:
            self.val.append(node.elem)
        if node.right:
            self.inorder(node.right)

    def is_st(self):
        self.inorder(self.root)
        if len(self.val)==1:
            return True
        for i in range(1,len(self.val)):
            if self.val[i]<self.val[i-1]:
                return False
        return True
temp_str=input()
str_list=temp_str.split()
input_list=[]
for i in str_list:
    if i is not '#':
        input_list.append(int(i))
    else:
        input_list.append(i)
search_tree=Tree()
search_tree.init_tree(input_list)
print(search_tree.is_st())

027二叉搜索树的插入、删除

class Node:
    def __init__(self,data):
        self.elem=data
        self.left=None
        self.right=None
        
def append_node(num,node):
    if node.elem is None:
        node.elem=num
        return
    if num>node.elem:
        if node.right is not None:
            append_node(num,node.right)
            return
        else:
            node.right=Node(num)
    if num<node.elem:
        if node.left is not None:
            append_node(num,node.left)
            return
        else:
            node.left=Node(num)

def make_search_tree(A):
    if A is []:
        return Node(None)
    root=Node(A[0])
    for i in A[1:]:
        append_node(i,root)
    return root

def pre_order(root):
    if root is None:
        return
    print(root.elem,end=' ')
    pre_order(root.left)
    pre_order(root.right)    

def delete_node(num,node,pre_node):
    if node is None or node.elem is None:
        return False
    if num>node.elem:
        return delete_node(num,node.right,node) 
    if num<node.elem:
        return delete_node(num,node.left,node)
    
    
    if pre_node.right is node:
        if node.left is None:
            pre_node.right=node.right
            del node
            return True
        if node.right is None:
            pre_node.right=node.left
            del node
            return True
    if pre_node.left is node:
        if node.left is None:
            pre_node.left=node.right
            del node
            return True
        if node.right is None:
            pre_node.left=node.left
            del node
            return True  
        
    pre=node.right
    if pre.left is None:
        node.elem=pre.elem
        node.right=pre.right
        del pre
    else:
        next_pre=pre.left
        while next_pre.left is not None:
            pre=pre.left
            next_pre=next_pre.left
        node.elem=next_pre.elem
        pre.left=next_pre.right
        del next_pre
    return True

def last_order(root):
    if root is None:
        return
    last_order(root.left)
    last_order(root.right) 
    print(root.elem,end=' ')

input_str=input()
A=[int(i) for i in input_str.split()]
root=make_search_tree(A)

N1=int(input())
for i in range(N1):
    data=int(input())
    append_node(data,root)
    pre_order(root)
    print()
N2=int(input())
for i in range(N2):
    data=int(input())
    if delete_node(data,root,None):
        last_order(root)
        print()
    else:
        print("Delete Error")

029构造Huffman树

class Node:
    def __init__(self,data):
        self.elem=data
        self.left=None
        self.right=None
        
def make_huffman_tree(A):
    child_tree=[Node(i) for i in A]
    while len(child_tree)>1:
        data1=child_tree.pop(0)
        data2=child_tree.pop(0)
        node=Node(data1.elem+data2.elem)
        node.left=data1
        node.right=data2
        child_tree.append(node)
        child_tree=sorted(child_tree,key=lambda root:root.elem)
    return child_tree[0]

sum_WPL=0
def cal_WPL(node,depth):
    global sum_WPL
    if node is not None and node.left is None and node.right is None:
        sum_WPL+=(node.elem*(depth-1))
    if node.left is not None:
        cal_WPL(node.left,depth+1)
    if node.right is not None:
        cal_WPL(node.right,depth+1)
          
k=input()
num=k.split()
num=[int(i) for i in num]
num=sorted(num)
cal_WPL(make_huffman_tree(num),1)
print(sum_WPL)

030构造AVL树

class TreeNode(object):
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
        self.height = 0
class AVLTree(object):
    def __init__(self):
        self.root = None
   
    def height(self, node):
        if node is None:
            return -1
        else:
            return node.height
    #在node节点的左孩子k1的左子树添加了新节点，左旋转
    def singleLeftRotate(self, node):
        k1 = node.left
        node.left = k1.right
        k1.right = node
        node.height = max(self.height(node.right), self.height(node.left)) + 1
        k1.height = max(self.height(k1.left), node.height) + 1
        return k1
    #在node节点的右孩子k1的右子树添加了新节点，右旋转
    def singleRightRotate(self, node):
        k1 = node.right
        node.right = k1.left
        k1.left = node
        node.height = max(self.height(node.right), self.height(node.left)) + 1
        k1.height = max(self.height(k1.right), node.height) + 1
        return k1
    #在node节点的左孩子的右子树添加了新节点，先左后右
    def doubleRightRotate(self, node):
        node.right = self.singleLeftRotate(node.right)
        return self.singleRightRotate(node)
    #在node节点的右孩子的左子树添加了新节点,先右后左
    def doubleLeftRotate(self, node):
        node.left = self.singleRightRotate(node.left)
        return self.singleLeftRotate(node)
    def insert(self, key):
        if not self.root:
            self.root = TreeNode(key)
        else:
            self.root = self._insert(key, self.root)
    def _insert(self, key, node):
        if node is None:
            node = TreeNode(key)
        elif key < node.data:
            node.left = self._insert(key, node.left)
            if (self.height(node.left) - self.height(node.right)) == 2:
                if key < node.left.data:
                    node = self.singleLeftRotate(node)
                else:
                    node = self.doubleLeftRotate(node)
        elif key > node.data:
            node.right = self._insert(key, node.right)
            if (self.height(node.right) - self.height(node.left)) == 2:
                if key > node.right.data:
                    node = self.singleRightRotate(node)
                else:
                    node = self.doubleRightRotate(node)
        node.height = max(self.height(node.right), self.height(node.left)) + 1
        return node
    def pre_order(self,node):
        if node is None:
            return
        print(node.data)
        self.pre_order(node.left)
        self.pre_order(node.right)

input_str=input()
A=[int(i) for i in input_str.split()]
avlt=AVLTree()
for i in A:
    avlt.insert(i)
avlt.pre_order(avlt.root)

031哈夫曼编码

class Node:
    def __init__(self,data):
        self.elem=data
        self.left=None
        self.right=None
        
def make_huffman_tree(A):
    child_tree=[Node(i) for i in A]
    while len(child_tree)>1:
        data1=child_tree.pop(0)
        data2=child_tree.pop(0)
        node=Node(('ZZ',data1.elem[1]+data2.elem[1]))
        node.left=data1
        node.right=data2
        child_tree.append(node)
        child_tree=sorted(child_tree,key=lambda root:(root.elem[1],root.elem[0])[:len(child_tree)],reverse=False)
    return child_tree[0]

road_dict={}
def cal_road(root,road):
    global road_dict
    if root.left is None and root.right is None:
        road_dict[root.elem[0]]=road
    else:
        cal_road(root.left,road+'0')
        cal_road(root.right,road+'1')
          
N=int(input())
input_str=input()
count={}
max_num=0
for i in input_str:
    count[i]=input_str.count(i)
A=sorted(count.items(),key=lambda x:(x[1],x[0])[:N],reverse=False)

cal_road(make_huffman_tree(A),'')
      
output_str=''
for i in input_str:
    output_str+=road_dict[i]
print(output_str)

032最小堆的插入和删除

def SiftUp(heap):
    k=heap[-1]
    j=int(len(heap)-1)
    i=int((j-1)/2)
    while j>0:
        if heap[i]>k:
            heap[j]=heap[i]
            j=i
            i=int((i-1)/2)
        else:
            break
    heap[j]=k
    return heap

def SiftDown(heap):
    k=heap[0]
    j=0
    i=2*j+1
    while i<len(heap):
        flag=i
        if i+1<len(heap):
            if heap[i+1]<heap[i]:
                flag=i+1
        if heap[flag]<k:
            heap[j]=heap[flag]
            j=flag
            i=2*j+1
        else:
            break
    heap[j]=k
    return heap

def insert(heap,num):
    heap.append(num)
    return SiftUp(heap)

def delete(heap):
    if len(heap)==1:
        return []
    heap[0]=heap[-1]
    heap=heap[:-1]
    return SiftDown(heap)

heap_str=input()
heap=heap_str.split()
heap=[int(i) for i in heap]
k=int(input())
for i in range(k):
    action=input()
    if action is 'I':
        num=int(input())
        heap=insert(heap,num)
    else:
        heap=delete(heap)
print(heap)

033 构造红黑树

class RBNode:
    def __init__(self,val,color="R"):
        self.val=val
        self.color=color
        self.left=None
        self.right=None
        self.parent=None

class RBTree:
    def __init__(self):
        self.root=None
        
    def LR(self, x):
        y = x.right
        if y is None:
            pass;
        else:
            beta = y.left
            x.right = beta
            if beta is not None:
                beta.parent = x
 
            p = x.parent
            y.parent = p
            if p is None:
                self.root = y
            elif x == p.left:
                p.left = y
            else:
                p.right = y
            y.left = x
            x.parent = y
        
    
    def RR(self, y):
        x = y.left
        if x is None:
            pass;
        else:
            beta = x.right
            y.left = beta
            if beta is not None:
                beta.parent = y
 
            p = y.parent
            x.parent = p
            if p is None:
                self.root = x
            elif y == p.left:
                p.left = x
            else:
                p.right = x
            x.right = y
            y.parent = x
                
    def insert(self,data):
        node=RBNode(data)
        x=self.root
        y=None
        while x is not None:
            y=x
            if node.val<x.val:
                x=x.left
            else:
                x=x.right
        node.parent=y
        
        if y is None:
            self.root=node
            self.fix_up(node)
            return
        
        if node.val<y.val:
            y.left=node
        else:
            y.right=node
        if y.color is "R":
            self.fix_up(node)
            
    def fix_up(self, z):
        if z.parent is None:
            z.color="B"
            self.root = z
            return
 
        if z.parent.color == "B":
            return
 
        p = z.parent
        g = p.parent  # g为x的grandpa
        if g is None:
            return
            #   return 这里不能return的。。。
        if g.right == p:
            y = g.left
        else:
            y = g.right
 
        if y == None:
            if z == p.right and p == p.parent.left:
                # 3-0-0:z为右儿子,且p为左儿子，则把p左旋
                # 转化为3-0-1或3-0-2的情况
                self.LR(p)
                p, z = z, p
                g = p.parent
            elif z == p.left and p == p.parent.right:
                self.RR(p)
                p, z = z, p
 
            g.color="R"
            p.color="B"
            if p == g.left:
                # 3-0-1:p为g的左儿子
                self.RR(g)
            else:
                # 3-0-2:p为g的右儿子
                self.LR(g)
 
            return
 
        # case 3-1:z有黑叔
        elif y.color == "B":
            if p.right == z and p.parent.left == p:
                # 3-1-0:z为右儿子,且p为左儿子,则左旋p
                # 转化为3-1-1或3-1-2
                self.LR(p)
                p, z = z, p
            elif p.left == z and p.parent.right == p:
                self.RR(p)
                p, z = z, p
 
            p = z.parent
            g = p.parent
 
            p.color="B"
            g.color="R"
            if p == g.left:
                # 3-1-1:p为g的左儿子，则右旋g
                self.RR(g)
            else:
                # 3-1-2:p为g的右儿子，则左旋g
                self.LR(g)
 
            return

        else:
            y.color="B"
            p.color="B"
            g.color="R"
            new_z = g
            self.fix_up(new_z)
            
    def pre_order(self,node):
        if node:
            print(node.val,end=' ')
            self.pre_order(node.left)
            self.pre_order(node.right)
            
    def pre_order_color(self,node):
        if node:
            c=1 if node.color=="B" else 0
            print(c,end=' ')
            self.pre_order_color(node.left)
            self.pre_order_color(node.right)
            
input_str=input()
A=[int(i) for i in input_str.split()]
Tree=RBTree()
for i in A:
    Tree.insert(i)
Tree.pre_order(Tree.root)
print()
Tree.pre_order_color(Tree.root)

034B树的构造

class Node:
    def __init__(self):
        self.data_list=[]
        self.ptr_list=[]
        self.parent=None
        
    def add_data(self,data):
        self.data_list.append(data)
    
    def add_child(self,node):
        self.ptr_list.append(node)
        node.parent=self
    
    def isLeaf(self):
        return len(self.ptr_list)==0

class BTree:
    def __init__(self,size):
        self.root=None
        self.size=size
        
    def _spilt(self,node):     
        middle = int(len(node.data_list)/2)
        top = node.data_list[middle]  
        right = Node()  
        for e in node.data_list[middle + 1:]:  
            right.add_data(e)  
              
        for n in node.ptr_list[middle + 1:]:  
            right.add_child(n)  
         
        node.data_list = node.data_list[:middle]  
        node.ptr_list = node.ptr_list[:middle + 1]  
         
        parent = node.parent  
         
        if parent:  
            parent.add_data(top)  
            parent.add_child(right)  
              
            if len(parent.data_list) > self.size:  
                self._spilt(parent)  
        else:  
            self.root = Node()  
            self.root.add_data(top)  
            self.root.add_child(node)  
            self.root.add_child(right)  
            
    def add(self,data):
        if self.root:
            current=self.root
            while not current.isLeaf():
                if len(current.data_list)>=self.size:
                    self._spilt(current)
                    current=current.parent.ptr_list[-1]
                else:
                    current=current.ptr_list[-1]
            if len(current.data_list)>=self.size:
                self._spilt(current)
                current=current.parent.ptr_list[-1]
            current.add_data(data)
        else:
            self.root=Node()
            self.root.add_data(data)
m_size=int(input())
num=int(input())
bt=BTree(m_size*2-1)
for i in range(num):
    bt.add(i+1)
k1=bt.root
while True:
    print(k1.data_list[0],end=' ')
    if k1.ptr_list == [] or k1.ptr_list[0].data_list[0]>k1.data_list[0]:
        break
    k1=k1.ptr_list[0]
print()
k2=bt.root
while True:
    print(k2.data_list[-1],end=' ')
    if k2.ptr_list == [] or k2.ptr_list[-1].data_list[-1]<k2.data_list[-1]:
        break
    k2=k2.ptr_list[-1]

035堆排序：数组中的第K个最大元素

def SiftDown(heap):
    k=heap[-1]
    j=int(len(heap)-1)
    i=int((j-1)/2)
    while j>0:
        if heap[i]<=k:
            heap[j]=heap[i]
            j=i
            i=int((i-1)/2)
        else:
            break
    heap[j]=k
    return heap

def SiftUp(heap):
    k=heap[0]
    j=0
    i=2*j+1
    while i<len(heap):
        flag=i
        if i+1<len(heap):
            if heap[i+1]>=heap[i]:
                flag=i+1
        if heap[flag]>=k:
            heap[j]=heap[flag]
            j=flag
            i=2*j+1
        else:
            break
    heap[j]=k
    return heap

def insert(heap,num):
    heap.append(num)
    return SiftDown(heap)

def delete(heap):
    top=heap[0]
    if len(heap)==1:
        return [],top
    heap[0]=heap[-1]
    heap=heap[:-1]
    return SiftUp(heap),top
input_str=input()
input_str=input_str.split(',')
input_int=[int(i) for i in input_str]
heap=[]
top_K=int(input())

for i in input_int:
    heap=insert(heap,i)

for i in range(top_K):
    heap,top=delete(heap)
print(top)

036 无限背包

N=int(input())
V=int(input())
C=list(map(int,input().split()))
W=list(map(int,input().split()))
import numpy as np
dp=np.zeros((N,V+1))

for i in range(N):#物品个数
    for ci in range(C[i],V+1):#背包大小
        dp[i][ci]=max(dp[i][ci-C[i]]+W[i],dp[i-1][ci])
print(int(dp[-1][-1]))

037 01背包

num_goods=int(input())
bag=int(input())

weight=input()
value=input()

value=[int(i) for i in value.split()]
weight=[int(i) for i in weight.split()]

dp=[0 for _ in range(bag+1)]
store=[[] for _ in range(bag+1)]
for i in range(len(value)):
    for j in range(bag,weight[i]-1,-1):
        dp[j]=max(dp[j-weight[i]]+value[i],dp[j])
        if dp[j-weight[i]]+value[i]>=dp[j]:
            store[j]=store[j-weight[i]]+[i+1]
print(dp[bag])
store[bag].sort()
for i in store[bag]:
    print(i,end=' ')

038任务分配问题

N=int(input())
G=[]
for i in range(N):
    G.append(list(map(int,input().split())))
from copy import copy
cost=10000
done=[0 for i in range(N)]
l=[]
from copy import copy
cost=10000
done=[0 for i in range(N)]
l=[]
def dfs(G,index,done1,cur_cost,min_list,N):
    global cost
    global l
    temp_done=copy(done1)
    if index==N:
        if cur_cost<cost:
            cost=cur_cost
            l=min_list
    for i in range(N):
        if temp_done[i] == 0:
            k=copy(temp_done)
            temp_list=copy(min_list)
            k[i]=1
            temp_list.append(i+1)
            dfs(G,index+1,k,cur_cost+G[index][i],temp_list,N)
dfs(G,0,done,0,[],N)
print(cost)
print(l)

039旅行商问题

from copy import copy
n=int(input())
mat=[[] for i in range(n)]
for i in range(n):
    str_list=input()
    str_list=[int(i) for i in str_list.split(',')]
    mat[i]=str_list
vis=[False for i in range(n)]
min_loss=10000
def visit(mat,vis,index,loss):
    global min_loss
    k=copy(vis)
    n=len(vis)
    if loss>=min_loss:
        return
    k[index]=True
    if all(k)==True:
        loss+=mat[index][0]
        min_loss=min(min_loss,loss)
    for i in range(n):
        if i!=index and k[i]==False:
            visit(mat,k,i,loss+mat[index][i])
visit(mat,vis,0,0)
print(min_loss)

041图的深度优先遍历

N=int(input())
k=int(input())
G=[[0 for i in range(N+1)] for i in range(N+1)]   
for i in range(k):
    temp=input()
    j=temp.split(',')
    G[int(j[0])][int(j[1])]=1
    G[int(j[1])][int(j[0])]=1
vis=[0 for i in range(N+1)]
def DFS(G,vis,V):
    if vis[V]==0:
        vis[V]=1
        print(V,end=' ')
    for i in range(1,N+1):
        if vis[i]!=1 and G[V][i]==1:
            DFS(G,vis,i)
DFS(G,vis,1)

042图的广度优先遍历

N=int(input())
M=int(input())
G=[[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    k=list(map(int,input().split(',')))
    G[k[0]][k[1]]=1
    G[k[1]][k[0]]=1
begin=int(input())
def bfs(G,N,begin):
    queue=[]
    vis=[0 for i in range(N+1)]
    vis[begin]=1
    queue.append(begin)
    save=[]
    while queue:
        v=queue.pop(0)
        save.append(v)
        for i in range(1,N+1):
            if G[i][v]==1 and vis[i]==0:
                queue.append(i)
                vis[i]=1
    return save
k=bfs(G,N,begin)
for i in k:
    print(i,end=' ')

043最短路径树

N=int(input())
G=[]
for i in range(N):
    G.append(list(map(int,input().split())))
def dijkstra(k,N,G):
    if G is None:
        return None
    inf=65535
    vis=[0 for i in range(N)]
    d=[inf for i in range(N)]
    d[k]=0
    U=[i for i in range(N)]
    for i in range(N):
        min_x=inf
        x=-1
        for j in range(N):
            if min_x>d[j] and vis[j]==0:
                min_x=d[j]
                x=j
        if x==-1:
            break
        vis[x]=1
        for v in range(N):
            if G[x][v]!=inf and vis[v]!=1:
                d[v]=min(d[v],d[x]+G[x][v])
    return d
print(dijkstra(0,N,G))

044最小生成树

k=int(input())
G=[]
for i in range(k):
    G.append(list(map(int,input().split())))
inf=65535
U=[]
V=[i+1 for i in range(k)]
U.append(1)
V.remove(1)
cost=0
def prim(U,V,G):
    global cost
    min_edge=inf
    min_v=-1
    for j in U:
        for k in V:
            if min_edge>G[j-1][k-1] and j!=k:
                min_edge=G[j-1][k-1]
                min_v=k
    V.remove(min_v)
    U.append(min_v)
    cost+=min_edge
    if V!=[]:
        prim(U,V,G)
prim(U,V,G)
print(cost)

046哈希应用-开放定址法

def str2num(temp_str):
    num=0
    base=10**(len(temp_str)-1)
    for i in temp_str:
        num+=int(i)*base
        base/=10
    return int(num)  
          
n=int(input())
temp_str=input()
temp_str=temp_str.split(' ')
num=[str2num(i) for i in temp_str]
hashT=[None for i in range(n)]
for i in num:
    iter_index=i%n
    while hashT[iter_index] is not None: iter_index=(iter_index+1)%n
    hashT[iter_index]=i
print(hashT)
    
find_str=input()
find_str=find_str.split(' ')
num_find=[str2num(i) for i in find_str]
for i in num_find:
    k=1
    if i == hashT[i%n]:
        print(k)
        continue
    index=((i%n)+1)%n
    end=i%n
    while hashT[i%n] is not None and index!=end :
        k+=1
        if i == hashT[index]:
            print(k)
            break
        index=(index+1)%n
    if index==end:
        print(-1)

050最小堆的构造

def SiftUp(heap,index):
    left=2*index+1
    right=2*index+2
    if left<len(heap):
        if right<len(heap):
            min_index=right
            if heap[right]>heap[left]:
                min_index=left 
            if heap[min_index]<heap[index]:
                heap[min_index],heap[index]=heap[index],heap[min_index]
                SiftUp(heap,min_index)
        else:
            if heap[left]<heap[index]:
                heap[left],heap[index]=heap[index],heap[left] 
                SiftUp(heap,left)

num_str=input()
num=num_str.split()
num=[int(i) for i in num]
heap=num
n=len(heap)-1
for i in range(int(n/2),-1,-1):
    SiftUp(heap,i)
print(heap)

051子集和问题（回溯法）

from copy import copy
k=False
def find_sub(l,cur,half,index):
    global k
    temp=copy(cur)
    if int(sum(temp))==half:
        k=True
    if l==[] or sum(temp)>half:
        return
    for i in range(index+1,len(l)+1): 
        temp=copy(cur)
        temp.append(l[i-1])
        find_sub(l,temp,half,i)
sum_list=input()
sum_list=sum_list.split()
sum_list=[int(i) for i in sum_list]
half=int(sum(sum_list)/2)
find_sub(sum_list,[],half,0)
print(k)

052牛牛找工作

N=int(input())
M=int(input())
Di=[]#难度
Pi=[]#报酬
for i in range(N):
    k=input()
    k=k.split()
    Di.append(int(k[0]))
    Pi.append(int(k[1]))
k2=input()
Ai=[int(i) for i in k2.split()]

for i in Ai:
    pay=-1
    for j in range(len(Di)):
        if i>=Di[j] and pay<=Pi[j]:
            pay=Pi[j]
    print(pay)