一，搜索连通域
M, N = list(map(int, input().split(','))) print(M,N) book = [] for i in range(M): line = list(map(int, input().split(','))) book.append(line) print(book) # M=N=3 # book=[[1, 0, 0], [0, 1, 0], [0, 1, 1]] print('book=',book) class Solution: def __init__(self,pos): self.pos=pos#给定的矩阵 print('self.pos',self.pos) print(self.pos[0][0]) self.dp=[]#保存所有区域的人数 self.cnt=0#记录当前区域的人数 #搜索联通区域 def dfs(self,i,j): if 0<=i<M and 0<=j<N: if self.pos[i][j]==1:#确保递归遍历的时候有人才加人 self.cnt+=1 self.pos[i][j] =0#遍历过置0,避免重复搜索 self.dfs(i, j-1) self.dfs(i, j+1) self.dfs(i-1, j) self.dfs(i+1, j) self.dfs(i - 1, j-1) self.dfs(i - 1, j +1) self.dfs(i +1, j - 1) self.dfs(i +1, j +1) def solver(self): for i in range(M): for j in range(N): if self.pos[i][j]==1: self.cnt=0#清零人数重新计数 self.dfs(i,j) if self.cnt>0: self.dp.append(self.cnt) return self.dp s=Solution(book) dp=s.solver() print('球队个数={},球队的最大群体人数={}'.format(len(dp),max(dp)))二，简单二叉树的实现
#简单二叉树的实现 class Node: def __init__(self,number): self.number=number self.lchild=None self.rchild=None class Tree: lis=[] def __init__(self): self.root=None #增加节点 def add(self,number): node=Node(number) if self.root==None: self.root=node print('add root') Tree.lis.append(self.root) print('Tree.lis=', Tree.lis) else: while True: point=Tree.lis[0] print('point=',point) if point.lchild==None: point.lchild=node Tree.lis.append(point.lchild) print('add lchild') print('Tree.lis=', Tree.lis) return if point.rchild==None: point.rchild=node Tree.lis.append(point.rchild) print('add rchild') print('Tree.lis=', Tree.lis) Tree.lis.pop(0)#更换root节点 print('Tree.lis=', Tree.lis) return if __name__ == '__main__': t=Tree() L=[1,2,3,4,5,6,7] for x in L: t.add(x) # print('success')三，找列表里的最长字符串
#找列表里的最长字符串 res=['a','v','f','sd','456','dfgg'] num_list=[len(i) for i in res] max_length_str=res[num_list.index(max(num_list))] print(max_length_str) #找列表里的最长字符串 a=sorted(res,key=lambda x:len(x),reverse=True) print(a[0])四，找两个字符串的最长公共字符串(暴力解法)
def function(s1): #找所有子字符串的结果 a=[] for i in range(0,len(s1)): for j in range(i+1,len(s1)+1): a.append(s1[i:j]) return a s1='sadsadarefcsfdsfds' s2='sadsafcvwertdfgdfg' res1=function(s1) res2=function(s2) res=[] for i in res1: if i in res2: #找共同字符串 res.append(i) #找出共同字符串中的最长字符串 res=sorted(res,key=lambda x:len(x),reverse=True) print(res[0])五，如题
A=list(map(int,input().split(','))) print(A) # A=[1,3,4,4] for i in range(len(A)-1): if sum(A[:i])==A[i] and A[i]==sum(A[i+1:]): print(A[i]) else: print(False)六，如题
a1,a2=input().split('-') print('a1,a2=',a1,a2) a1=list(map(int,a1.split(','))) a2,k=a2.split(':') a2=list(map(int,a2.split(','))) k=int(k) print('a1,a2,k=',a1,a2,k) tem=[] for i in a1: tem+=[i+j for j in a2] print('tem=',tem) print(list(map(str,sorted(tem,reverse=True)))[:k]) print(','.join(list(map(str,sorted(tem,reverse=True)))[:k]))七，如题
X,Y,Z=sorted(list(map(int,input().split(' ')))) print(X,Y,Z) def solve(X,Y,Z): cnt = 0 for a in range(1,X+1): for b in range(1,Y+1): #最短边 min_c=abs(a-b)+1 # print(min_c) # 最长边 max_c=min(a+b-1,Z) # print(max_c) cnt+=max_c-min_c+1 cnt%=1000000007 return cnt cnt=solve(X,Y,Z) print('cnt=',cnt)
八，如题，采用贪心算法
N=int(input()) line=[] for i in range(N): a,b=sorted(list(map(int,input().split(' ')))) line.append([a,b]) print(line) # line=[[3, 6], [1, 3], [2, 5]] line=sorted(line,key=lambda x:x[1]) print('line=',line) ret = [line[0]] print('ret=',ret) for item in line[1:]: print('item=',item) if ret[-1][1]>item[0]: pass else: ret.append(item) print(ret) print(len(ret))九，如题，
N,M,P=list(map(int,input().split(' '))) print('N={},M={},p={}'.format(N,M,P)) A=list(map(int,input().split(' '))) print(A) # N,M,P=3,4,2 # A=[5,3,1] for i in range(M): flag,t=input().split(' ') t=int(t) if flag=='A': A[t-1]+=1 else: A[t - 1] -= 1 print('A=',A) # A=[4,5,2] A=list(zip(A,range(1,len(A)+1))) print('A=',A) #按照份数进行排序 A=sorted(A,reverse=True) print('A=',A) #排名第一的第二种食物，value=1 ret={A[0][1]:1} print('ret=',ret) for i in range(1,len(A)): if A[i][0]==A[i-1][0]: ret[A[i][1]]=ret[A[i][0]] else:#key->value ret[A[i][1]] =i+1 print(ret) print(ret[P])十.教学任务指派问题,匈牙利算法,由谁去做某某件事情总体的时间或者效率最高
#教学任务指派问题 #匈牙利算法,由谁去做某某件事情最合适 import numpy as np from scipy.optimize import linear_sum_assignment def printf(row_ind,col_ind):#输出 print("最优教师课程指派：") for i in range(len(row_ind)): print("教师",row_ind[i], "->课程", col_ind[i],end='; ') print() #教师与课程一样多 #各个教师对各个课的擅长程度矩阵 goodAt =np.array([[18, 5, 7, 16], [10, 16, 6, 5], [11, 6, 4, 7], [13, 12, 9, 11]]) print('==每个老师对课程的擅长矩阵:\n', goodAt) #由最大值减去矩阵,变成求解最小值问题 weakAt = 20 - goodAt row_ind, col_ind = linear_sum_assignment(weakAt) print('==row_ind:', row_ind)#开销矩阵对应的行索引 print('==col_ind:', col_ind)#对应行索引的最优指派的列索引 print('==goodAt[row_ind, col_ind]:', goodAt[row_ind, col_ind])#提取每个行索引的最优指派列索引所在的元素，形成数组 print('最优结果为', goodAt[row_ind, col_ind].sum())#数组求和 printf(row_ind, col_ind)