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)
投递腾讯等公司10个岗位