我好像申请了机器学习的开发冈，只能说定向和非定向很多不会
编程题只做对了第一道，第二道用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) 回帖