'''
二分查找(升序)
arr：传入的序列
data：需要查找的数据
'''

def binarySearch(arr,data):
    len_arr = len(arr)
    mid = len_arr // 2
    
    if len_arr >= 1:
        if arr[mid] > data:
            return binarySearch(arr[0:mid],data)
        elif arr[mid] < data:
            return binarySearch(arr[mid+1:],data)
        else:
            return True
    # 列表长度小于1，代表查询结束，没有找到需要的数据
    else:
        return False

l = [1,2,3,4,5]
print(binarySearch(l,2)) # True
print(binarySearch(l,9)) # False

l = [2,1,3,3,6,2,4,7,2]
# 方法一
from collections import Counter
print(Counter(l)) # 打印Counter({2: 3, 3: 2, 1: 1, 6: 1, 4: 1, 7: 1})

# 方法二
d = {}
for i in l:
    d[i] = l.count(i)
print(d)


# 方法三
s = set(l)
for i in s:
    print('%s有%s个' %(i,l.count(i)))

l = [33,218,7,96,45,11,4,99,63,28]

# 冒泡排序
def bubbling_sort(l):
    len_l = len(l)
    # 外层循环控制循环的次数
    for i in range(len_l - 1):
        # 内层循环控制遍历到哪一位
        for j in range(len_l - 1 - i):
            # 如果后一位比前一位小，则交换位置
            if l[j+1] < l[j]:
                l[j],l[j+1] = l[j+1],l[j]
    return l


# 快速排序
def fast_sort(l):
    # 如果列表的长度等于0或1表示排序结束，返回列表
    if len(l) < 2:
        return l
    else:
        # 选取基准值
        mid = l[len(l) // 2]
        # 先把基准值从列表中排序，不然会有重复
        l.remove(mid)
        left = [i for i in l if i < mid]
        right = [j for j in l if j > mid]
        return fast_sort(left) + [mid] + fast_sort(right)
        
        

print('冒泡排序的结果：%s' %bubbling_sort(l))
print('快速排序的结果：%s' %fast_sort(l))

a = '10010' # 18
b = '11000' # 24

a,b = int(a,2),int(b,2) # int()第二个参数表示传入的字符串进制数，默认十进制，返回结果十进制
print(bin(a+b)[2:]) # bin(a+b) 返回0b101010，所以要从第三位开始取

def symbol_sort(symbols):
    l1 = list()
    l2 = list()
    for s in symbols:
        if s == '+':
            l1.append(s)
        else:
            l2.append(s)
        
    l1.extend(l2)
    return l1
sym = '+--+++-'
print(symbol_sort(sym))

class ListNone():
    def __init__(self,val):
        self.val = val
        self.next = None
        
'''
主要逻辑步骤：
1.先把第一个节点后的数据保存赋值给一个变量
2.把第一个变量的next赋值为空，即从链表分裂掉第一个节点
3.把声明的指针指向分裂出来的节点
4.最后把链表的头部指针赋值给下一个节点，即指针往后移动一位
如此循环......
'''        
def reverseList(head):
    last = None
    while head:
        tmp = head.next
        head.next = last
        last = head
        head = tmp
    return last

l = ListNone(1)
l.next = ListNone(3)
l.next.next = ListNone(9)
l1 = reverseList(l)
print(l1.val,l1.next.val,l1.next.next.val) # 打印  9  3  1

'''
交叉链表逻辑：
若两个链表有一个公共结点，则该公共节点之后的所有结点都是重合的，及它们的最后一个结点必然重合（结构是Y字形）
利用这个特性，可以先获取两个列表的长度，然后长的列表比短的链表先走(len(长)-len(短))个长度，然后两个链表的指针同时往后走
直到找到公共节点，没有找到相交节点返回None
'''

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

# 获取链表长度
def get_length(head):
    length = 0 
    while head:
        length += 1
        head = head.next
    return length


# 获取公共节点
def get_cross_node(list_a,list_b):
    len_a = get_length(list_a)
    len_b = get_length(list_b)
    
     # 给两个链表各声明一个指针
    cur_a = list_a
    cur_b = list_b
    if len_a > len_b:
        for i in range(len_a - len_b):
            cur_a = list_a.next
    else:
        for i in range(len_b - len_a):
            cur_b = list_b.next
            
    
    flag = False
    while cur_a and cur_b:
        if cur_a.val == cur_b.val:
            print(cur_a.val)
            flag = True
            break
        else:
            cur_a,cur_b = cur_a.next,cur_b.next
    
    if not flag:
        print("链表没有交叉节点")
    
list_a = ListNode('a1',ListNode('a2',ListNode('c1',ListNode('c2',ListNode('c3')))))
list_b = ListNode('b1',ListNode('b2',ListNode('b3',ListNode('c1',ListNode('c2',ListNode('c3'))))))
get_cross_node(list_a,list_b)

'''
栈：先进后出
队列：先进先出


方法一：

逻辑：
进栈push：在一个空的队列中添加元素，然后把另一个非空队列中的元素弹出并追加到该队列后面，所以，总会有一个队列是空的，以此循环追加即可
删除栈顶元素pop: 进栈时已把元素重新排序，所以直接弹出栈顶元素即可




方法二：

使用列表的insert()方法，指定每次插入的元素都放在最前面
'''


# 方法一
class Stack1():
    
    def __init__(self):
        self.queue_a = []
        self.queue_b = []
    
    
    # 进栈
    def push(self,n):
        if len(self.queue_a) == 0:
            self.queue_a.append(n)
        elif len(self.queue_b) == 0:
            self.queue_b.append(n)
        
        # 把队列b中的元素追加到a的后面
        if len(self.queue_a) == 1 and len(self.queue_b) > 1:
            for i in range(len(self.queue_b)):
                self.queue_a.append(self.queue_b.pop(0))
        elif len(self.queue_b) == 1 and len(self.queue_a) >= 1:
            for i in range(len(self.queue_a)):
                self.queue_b.append(self.queue_a.pop(0))
                
    # 删除栈顶元素
    def pop(self):
        if self.queue_a:
            return self.queue_a.pop(0)
        elif self.queue_b:
            return self.queue_b.pop(0)
        else:
            return None
    
    # 查询当前栈内元素
    def get_stack(self):
        if self.queue_a:
            return self.queue_a
        elif self.queue_b:
            return self.queue_b
        else:
            return None
    
    # 查询栈顶元素:
    def peek(self):
        if self.queue_a:
            return self.queue_a[0]
        elif self.queue_b:
            return self.queue_b[0]
        else:
            return None

    # 查询当前栈长度
    def len_stack(self):
        if self.queue_a:
            return len(self.queue_a)
        elif self.queue_b:
            return len(self.queue_b)
        else:
            return None


        
# 方法二
class Stack2():
    def __init__(self):
        self.list_a = list()
        
    def push(self,num):
        self.list_a.insert(0,num)
    
    def get_stack(self):
        return self.list_a
    
    

s = Stack1()
s2 = Stack2()

for i in range(5):
    s.push(i)
    s2.push(i)
    
print(s.get_stack()) # [4,3,2,1,0]
print(s.pop())
print(s.get_stack())
print(s.pop())
print(s.get_stack())
print(s.pop())
print(s.get_stack())
print('*'*50)
print(s2.get_stack()) # [4,3,2,1,0]

def get_mid(l):
    l.sort()
    if len(l) == 0:
        return
    elif len(l) == 1:
        return l[0]
    else:
        if len(l) % 2 == 0:
            mid = (l[len(l) // 2] + l[len(l) // 2 - 1]) / 2
        else:
            mid = l[len(l) // 2]
            
        return mid
    
l = [2,15,7,3,100,10]
print(get_mid(l)) # 8.5

class Node():
    def __init__(self,n):
        self.val = n
        self.left = None
        self.right = None
        
'''
数据域：节点中存储数据元素的部分
指针域：节点中存储数据元素之间的链接信息，即链接到下一节点地址的部分
内嵌函数： 内部函数需要递归调用并不能实现全部功能，外层函数完成剩余功能，也可以分开写

'''
def kthSmallest(root,k):
        
#         l = list()
        def search_min(root):
            if not root:
                return []
            # 在内层函数申明列表是因为只需返回最后一次递归的结果，即[10, 12, 15, 16, 20, 21, 22, 23]
            # 若是申明在外部，则会把每一层递归的结果都追加的列表里 [10,10,12,10,10,12,15,10,10,12,15,16........]
            l = list()
            # 递归查询左树数据域
            l.extend(search_min(root.left))
            l.append(root.val)
            # 递归查询右树数据域
            l.extend(search_min(root.right))
            return l
        return search_min(root)[k-1]

n1 = Node(20)
n1.left = Node(15)
n1.right = Node(22)
n1.left.left = Node(12)
n1.left.right = Node(16)
n1.left.left.left = Node(10)
n1.right.left = Node(21)
n1.right.right = Node(23)


kthSmallest(n1,6) # 21

from concurrent.futures import ThreadPoolExecutor
import time

def ret_msg(msg):
    time.sleep(2)
    return msg

pool = ThreadPoolExecutor(max_workers=2) # 最多加入两个task

future1 = pool.submit(ret_msg,("hello")) # 加入task1
future2 = pool.submit(ret_msg,("world")) # 加入task2

print(future1.done()) # 查看task1任务是否完成 打印False
time.sleep(3)
print(future2.done()) # 打印True
print(future1.result()) # 查看task1结果
print(future2.result())