9.3 百度研发笔试题

第一题

若一个整数的数字和能被9整除，则这个整数能被9整除
AC

def first():
    n = int(input())
    zero, five = 0, 0
    temp = list(map(int, input().split(' ')))
    for i in range(n):
        t = temp[i]
        if t == 0:
            zero += 1
        else:
            five += 1
    if zero == 0:
        print(-1)
    else:
        print(int('5' * (five // 9 * 9) + '0' * zero))

第二题

暴力超时，也没想到什么好办法

第三题

还是动态规划的思路，需要保存更多的状态
通过60%

def third():
    from collections import defaultdict
    n, m = map(int, input().split(' '))
    dp = defaultdict(dict)
    # length, pre, pre-pre
    for i in range(1, m + 1):
        dp[i][(i, 0)] = 1

    for i in range(3, n + 1):
        for j in range(1, min(i, m + 1)):
            for (pre, ppre) in dp[i - j]:
                if j == ppre or j == pre:
                    continue
                if (j, pre) in dp[i]:
                    dp[i][(j, pre)] += dp[i - j][(pre, ppre)]
                else:
                    dp[i][(j, pre)] = dp[i - j][(pre, ppre)]
    res = 0
    for t in dp[n].values():
        res = (res + t) % int(1e9 + 7)
    print(res)