9.5搜狗算法笔试

菜鸡第三题没做出来 a了2.5667

第一题是个很奇怪的模拟题
说实话写完之后我自己都看不懂 整整花了30分钟

class Solution:
    def numberofprize(self , a , b , c ):
        # write code here
        t = min(a, b, c)
        res = t
        abc = []
        abc.append(a)
        abc.append(b)
        abc.append(c)
        rem = [x - t for x in abc if x > t]
        remt0 = 0
        if len(rem) == 2:
            t = min(rem)
            rem_t = [x - t for x in rem if x > t]
            if rem_t:
                remt0 = rem_t[0]
            if remt0 // 2 >= t:
                res += t
                cc = rem_t[0] - t*2
                res += cc//5
            else:
                k = remt0 // 2
                res += k
                t -= k
                res += t//2
        elif len(rem) == 1:
            remt0 = rem[0]
            res += remt0 // 5
        return res

第二题 统计每个空隙够不够放房屋就行 如果大于t 就是两个 等于t就正好一个
这里由于会存在占半格的情况 考虑浮点数精度问题做了一点点处理

class Solution:
    def getHouses(self , t , xa ):
        # write code here
        n = len(xa)//2
        res = 2
        for i in range(n-1):
            l = xa[2*i] + xa[2*i+1]/2
            r = xa[2*(i+1)] - xa[2*(i+1)+1]/2
            if abs(r - l - t) < 1e-3:
                res += 1
            elif r - l - t < -1e-3:
                pass
            else:
                res += 2
        return res

第三题直接暴力写了个解法 爆掉50% 提示wa 没有tle
后来用java抄了一遍 ac变成56.67% 之后没想出原因 直接交卷了
事后和一位朋友交流得知 如果不用暴力法做 可以O(n)解决 需要对方差计算公式做一些小小的化简
代码就不贴了