首页 > 阿里笔试 7/29 9-10点场
头像
悦兮
编辑于 2020-07-29 13:25
+ 关注

阿里笔试 7/29 9-10点场

  1. 给 n 个恐龙蛋及恐龙蛋的大小,按从大到小排列,第 i 个恐龙蛋每天增大 i,问最少几天会出现两个同样大小的恐龙蛋。
  2. n 个客栈依次排列,给出 n - 1 条路的权重。从任意一处出发,每走过一条路,该路的权重减 1,但得到 1 点利益。不能走权重为 0 的路。求最大利益。

😭 我太菜了

1. 暴力法,每过一天增加恐龙蛋大小,然后判断是否有同样大小的。测试用例能通过 80%。
import itertools

n = int(input())
sizes = list(map(int, input().split()))
sizes.sort(reverse=True)


def judge_equal(sizes):
    hSet = set()
    for s in sizes:
        if s in hSet:
            return True
        hSet.add(s)
    return False


def update_sizes(sizes):
    for i in range(len(sizes)):
        sizes[i] += i + 1


for i in itertools.count(1):
    update_sizes(sizes)
    if judge_equal(sizes):
        print(i)
        break
思路:两个恐龙蛋 i, j (j > i),增长速度可知,初始大小已知,可计算 i,j 在几天后达到同样大小。测试用例仅能通过 10%(还是 20% 忘记了,反正很少)。
欢迎大佬指正:是思路问题还是效率问题?
n = int(input())
sizes = list(map(int, input().split()))
sizes.sort(reverse=True)

min_days = float('inf')

for i in range(len(sizes) - 1):
    for j in range(i + 1, len(sizes)):
        diff = sizes[i] - sizes[j]
        k = j - i
        if diff % k == 0:
            min_days = min(min_days, diff // k)

print(min_days)
2. 回溯,没想到更好的方法。通过率仅 10%。
def try_all():
    n = int(input())
    weights = list(map(int, input().split()))

    MAX = 0

    def dfs(weight, cur, value):
        nonlocal MAX
        MAX = max(MAX, value)
        if cur >= 1 and weight[cur - 1] > 0:  # 向左走
            weight[cur - 1] -= 1
            dfs(weight, cur - 1, value + 1)
            weight[cur - 1] += 1  # 回溯
        if cur < len(weight) and weight[cur] > 0:  # 向右走
            weight[cur] -= 1
            dfs(weight, cur + 1, value + 1)
            weight[cur] += 1  # 回溯

    for i in range(n):
        dfs(weights, i, 0)

    print(MAX)


try_all()



全部评论

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

推荐话题

相关热帖

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

近期精华帖

热门推荐