首页 > 9.5 搜狗研究方向笔试3ac笔经
头像
匿名牛油果
编辑于 2020-09-05 20:28
+ 关注

9.5 搜狗研究方向笔试3ac笔经

写在最开始,最近笔试面试一直被虐,终于有个全ac的- -开心,



第一题,汪仔换道具,主要思路就是先减去直接换的,然后排序,此时a=0,分为两种情况,b,c给a,以及c给b和a。设x解方程就可以求出表达式

class Solution:
    def numberofprize(self , a , b , c ):
        # write code here
        res = 0
        res+= min(a,b,c)
        a -= res
        b -= res
        c -= res
        a,b,c = sorted([a,b,c])
        
        return min(res + (2*b+c)//5,res + (b+c)//4)

第二题,建房子,思路是找房子间隔,大于t就+2,等于t就+1,最后考虑最左和最右,+2就可以了

class Solution:
    def getHouses(self , t , xa ):
        # write code here
        res = 0
        for i in range(0,len(xa),2):
            xa[i],xa[i+1] = xa[i]-xa[i+1]/2,xa[i]+xa[i+1]/2
        for i in range(len(xa)//2 -1):
            if xa[2*i+2] - xa[2*i+1] == t:
                res += 1
            elif xa[2*i+2] - xa[2*i+1] > t:
                res += 2
        return res+2

第三题 求方差和最小的idx,这个题是原题= =有舍友阿里被问过。方法就是D(x) = E(X^2) - E(X)^2,利用前缀和数组,可以很快计算出arr[i:j]的E(X)^2和E(X^2).

class Solution:
    def find_best_cut(self , arr ):
        # write code here
        n = len(arr)
        prex = [0]
        prex2 = [0]
        for num in arr:
            prex.append(prex[-1]+num)
            prex2.append(prex2[-1]+num**2)
        def var(i,j):
            if i>=j:return 0
            n = j-i+1
            Ex = (prex[j+1]-prex[i])/n
            Ex2 = (prex2[j+1]-prex2[i])/n
            return Ex2-Ex**2
        v = float('inf')
        res = 0
        for i in range(0,n):
            temp = abs(var(0,i-1) + var(i,n-1))
            if temp < v:
                res = i
                v = temp
        return res



全部评论

(6) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐