微软8.13笔试(python版)
code1 [5,19,8,1]输出3 19/2/2+8/2共计3次
遍历列表每次对最大值除2,三个测试案例都能过复杂度应该也还可以
def solution(A): A.sort() target = sum(A)/2 A = A[::-1] if len(A)<=2: return len(A) B = A[:] res,count = 0,0 while res<target: temp = [] m = max(B)/2 res += m indx = B.index(m*2) B[indx] = m count += 1 return countcode2 给X,Y两个数组,分别代表分子分母,求X[i]/Y[i]+X[j]/Y[j] =1的对数
没想到特别好的优化方法,其实也就是暴力找解,但是在循环过程中增加了判断条件减少循环次数,三个测试案例同样也过了,但是可能时间复杂度会超
def solution(X,Y): count = 0 for i in range(len(X)-1): target = X[i]/Y[i] if target >=1: continue for j in range(i+1,len(Y)): m = min(X[j:len(X)])/min(Y[j:len(Y)]) if m+target >1: break elif target+(X[i]/Y[j])==1: count += 1 return countcode3 我理解就是步长为Y,在列表中找X个数,求和最小,3个测试案例过了
A=[4,2,3,7] X=2,Y=2,return 7=4+3 思路其实也挺简单,依次按照步长Y,个数X去遍历列表,添加到temp中,如果temp元素个数=X,那在target列表中求个和,最后输出最小cost的那个
def solution(A,X,Y): target = [] for i in range(len(A)-Y): temp = [] step = i for j in range(X): temp.append(A[step]) if step+Y>=len(A): break else: step += Y if len(temp) == X: target.append(sum(temp)) return min(target)最后,欢迎大家讨论啊,我挺菜的 ,考试130分钟只能想到这些方法去解答