算法笔试题
一,搜索連通域?
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+=1self.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=numberself.lchild=Noneself.rchild=None class Tree:lis=[]def __init__(self):self.root=None#增加節點def add(self,number):node=Node(number)if self.root==None:self.root=nodeprint('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=nodeTree.lis.append(point.lchild)print('add lchild')print('Tree.lis=', Tree.lis)returnif point.rchild==None:point.rchild=nodeTree.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 as1='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 = 0for 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+1cnt%=1000000007return 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]:passelse: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]+=1else:A[t - 1] -= 1print('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->valueret[A[i][1]] =i+1 print(ret) print(ret[P])十.教學任務指派問題,匈牙利算法,由誰去做某某件事情總體的時間或者效率最高
#教學任務指派問題 #匈牙利算法,由誰去做某某件事情最合適import numpy as np from scipy.optimize import linear_sum_assignmentdef 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) 創作挑戰賽新人創作獎勵來咯,堅持創作打卡瓜分現金大獎總結
- 上一篇: Python中Turtle绘图函数-绘制
- 下一篇: vscode debug c++与ope