首页 > 奇安信笔试复盘
头像
大鹏呀
发布于 2021-08-23 19:52
+ 关注

奇安信笔试复盘

我好像申请了机器学习的开发冈,只能说定向和非定向很多不会
编程题只做对了第一道,第二道用dfs没写出来,在牛客上看了大神的思路才写出来简单的

1.给出一个0.01到0.99之间的小数,找出分子与分母均不超过200的最简分数,使其最接近给出的小数。
“最接近”是指在数轴上该分数距离给出的小数最近,如果这个分数不惟一,输出分子分母之和最小的一个。
输入 0.333333,输出 [1,3]
输入 0.375,输出 [3,8]
我的思路是暴力遍历,找出最接近的分子分母,然后看分子分母有没有公约数
class Solution:
    def getFraction(self, a):
        index = float(2.0)
        m, n = 0, 0
        result = []
        for i in range(200, 0, -1):
            for j in range(i - 1, 0, -1):
                k = float(j / i)
                if float(abs(a - k)) < float(abs(index - a)):
                    index = k
                    m = i
                    n = j
        if m % n == 0:
            result.append(1)
            result.append(int(m / n))
        else:
            a, b = n, m
            while a != 0:
                temp = b % a
                b = a
                a = temp
            result.append(int(n / b))
            result.append(int(m / b))
        return result


s = Solution()
print(s.getFraction(0.0083))
2.连珠子
第一象限(x>=0&&y>=0)内有n个珠子(n>3),已知它们的坐标,你可以从任意一个珠子开始,一笔画连接共三个珠子,问最小的连接距离是多少?
要求:一笔画的过程中,只能沿着横轴或者纵轴行走。相当于在格子图中只能沿着线走,珠子都在横线竖线的交点处。
输入:一组珠子坐标,比如 [[0,0], [0,2], [1,1], [10,10]] 
输出:最小距离,4
自己一开始的思路是dfs结果没写出来,参考牛客评论区的一位大神的思路进行改编
首先便利每个点到其他点的曼哈顿距离,然后逸这个点到他最近两个点的曼哈顿距离之和
比较上述所有求得得距离和,最小的即为题目所求的和
class Solution:
    def getMinLength(self, pearls):
        pearls_len = len(pearls)
        Alldistance_list = []
        for i in range(pearls_len):
            distance_list = []
            for j in range(pearls_len):
                if i != j:
                    distance = abs(pearls[i][0] - pearls[j][0]) \
                               + abs(pearls[i][1] - pearls[j][1])
                    distance_list.append(distance)
            distance_list.sort()
            Alldistance_list.append(distance_list[0] + distance_list[1])

        Alldistance_list.sort()
        print(Alldistance_list[0])
s = Solution()
s.getMinLength([[0, 0], [1, 0], [0, 2], [1, 2]])



全部评论

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

相关热帖

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

近期精华帖

热门推荐