1. 满二叉搜索树查找
   描述
   给定2^n-1个不同的整数(1<=n<=10,n为整教)，构建一棵平衡满二叉搜索树
   二叉搜索树的定义如下:
   1)节点的左子树只包含小于当前节点的数。
   2)节点的右子树只包含大于当前节点的数。
   3)所有左子树和右子树自身必须也是二叉搜索树。

import sys


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



def build(nums):
    if not nums : return None
    # 找到root
    rt_idx = len(nums) // 2  
    rt = Node(nums[rt_idx])
    rt.left = build(nums[:rt_idx])
    rt.right = build(nums[rt_idx+1:]) 
    return rt 


def dfs(rt , target) :
    # if not rt : return False 
    if target > rt.val :
        if rt.right :
            print('R' , end='')
            return dfs(rt.right , target) 
        else :
            return False
    elif target < rt.val :
        if rt.left : 
            print('L' , end='')
            return dfs(rt.left , target)
        else :      
            return False
    return True 


def main():
    input = sys.stdin.read().split() 
    ptr = 0
    a = list(map(int,input[:]))
    target = a[-1] 
    a = a[:-1] 
    # print(target , a)
    a.sort() 
    root = build( a)  
    # print(root)
    print('S' , end='')
    find = dfs(root,target)
    if find :
        print("Y" , end='')
    else :
        print('N' , end='')

if __name__ == '__main__' :
    main() 

2.足球队员射门能力排序
球队有n个足球队员参，的次射心训练，每次射门进球用1表示，射失则用0表示，依据如下规则对该n个队员的射门能力做排序
1、进球总数更多的队是射门能力更强
2、若进球总数一样多，则比较最多-次连续进球的个数，最多的队员能力
更强
3、若最多 次连续进球的个数一样多，则比较第一次射失的先居顺序，其
中后射丢的队员更强，若第一次射丢顺序相同，则按继续比较第二次射丢
的顺序，后丢球的队员能力如强，依次类推
4、若前3个规则批序后还能力相等，则队员编与更小的能力更强

import sys


class Case:
    def __init__(self,id,case) :
        self.id = id 
        self.case = case 
        self.one_cnt = 0 
        self.conse_one = 0 
        self.zero_pos = -1 
        self.cal()
    def cal(self):
        self.get_one_cnt() 
        self.get_conse_one() 
        self.get_zero_pos() 
    def get_one_cnt(self) :
        res = 0 
        for x in self.case :
            if x == '1' : res += 1
        self.one_cnt =  res 
    def get_conse_one(self):
        res = 0 
        sw = False
        cur = 0 
        for i , x in enumerate(self.case) :
            if not sw and x == '1' :
                sw = True 
                cur = 1 
            elif sw and x == '1' :
                cur += 1 
            elif sw and x == '0' :
                sw = False 
                res = max(cur,res)
                cur = 0 
        res = max(res,cur)
        self.conse_one = res 
    def get_zero_pos(self):
        for i , x in enumerate(self.case) :
            if x == '0' :
                self.zero_pos = i 
                return 
        self.zero_pos = float('inf') 


def main():
    input = sys.stdin.read().split() 
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    k = int(input[ptr])
    ptr += 1
    case = [] 
    for i in range(n) :
        cur = input[ptr]
        ptr += 1 
        case.append(Case(id=i+1,case=cur))
    # for c in case :
    #     print(c.id,c.case,c.one_cnt,c.conse_one,c.zero_pos)

    case = sorted(case,key=lambda x : (-x.one_cnt,-x.conse_one,-x.zero_pos,x.id))
    for c in case :
        print(c.id , end=' ')

if __name__ == '__main__' :
    main() 

1. 找到内聚值最大的微服务群组
   开发团队为了调研微服务调用情况，对n个微服务调用数据进行了采集分析，微服务使用数字0至n-1进行编号，给你一个下标从0开始的数组edges ，其中 edges[i]表示存在一条从微服务i到微服务 edges[i]的接口调用。
   我们将形成1个环的多个微服务称为微服务群组，一个微服务群组的所有微服务数量为L，能够访问到该微服务群组的微服务数量为V，这个微服务群组的内聚值H=L-V。
   已知提供的数据中有1个或多个微服务群组，请按照内聚值H的结果从大到小的顺序对所有微服务群组(H相等时，取环中最大的数进行比较)排序，输出排在第一的微服务群组，输出时每个微服务群组输出的起始编号为环中最小的数。

import sys

class Loop:
    def __init__(self, min_id, max_id, H):
        self.min_id = min_id
        self.max_id = max_id
        self.H = H

def main():
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    a = list(map(int, input[ptr:ptr + n]))

    # 并查集初始化
    f = list(range(n))
    sz = [1] * n

    def find(x):
        if f[x] != x:
            f[x] = find(f[x])
        return f[x]

    def union(a_, b_):
        fa = find(a_)
        fb = find(b_)
        if fa != fb:
            if sz[fa] < sz[fb]:
                fa, fb = fb, fa
            f[fb] = fa
            sz[fa] += sz[fb]

    # 建立并查集
    for i in range(n):
        union(i, a[i])

    # 寻找所有环
    vis = [False] * n
    loops = []

    for i in range(n):
        if vis[i]:
            continue
        path = []
        current = i
        while True:
            if vis[current]:
                if current in path:
                    idx = path.index(current)
                    loop_nodes = path[idx:]
                    loop_len = len(loop_nodes)
                    min_id = min(loop_nodes)
                    max_id = max(loop_nodes)
                    # 计算H值
                    H = 2 * loop_len - sz[find(current)] 
                    loops.append(Loop(min_id, max_id, H))

                break
            else:
                vis[current] = True
                path.append(current)
                current = a[current]

    loops.sort(key=lambda x: (-x.H, -x.max_id))

    if not loops:
        return

    # 获取最佳环的节点顺序
    best_loop = loops[0]
    start_node = best_loop.min_id
    current = start_node
    loop_members = []
    while True:
        loop_members.append(current)
        current = a[current]
        if current == start_node:
            break

    print(' '.join(map(str, loop_members)) , end='')

if __name__ == '__main__':
    main()