完美世界笔试
机器学习岗，选择题全是C和爪哇😥。
编程题都是动态规划
import sys
n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())
arr = list(map(int, sys.stdin.readline().strip().split(" ")))
res = [[0] * m for _ in range(n)]
c = 0
for i in range(n):
for j in range(m):
res[i][j] = arr[c]
c += 1
class Solution:
def calculateMinimumHP(self, dungeon):
rows = len(dungeon)
cols = len(dungeon[0])
dp = [[0] * cols for _ in range(rows)]
# 初始化，最右下角的血量。至少为1，并且若有损失，还需要增加
dp[-1][-1] = max(1,1 - dungeon[-1][-1])
for i in range(cols-2, -1, -1):
# 只能朝右侧走
dp[rows-1][i] = max(1, dp[-1][i+1] - dungeon[-1][i])
for i in range(rows-2, -1, -1):
dp[i][cols-1] = max(1, dp[i+1][-1] - dungeon[i][-1])
for i in range(rows-2, -1, -1):
for j in range(cols-2, -1, -1):
dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
return dp[0][0]
print(Solution().calculateMinimumHP(res))
钱用最少不同金额的硬币组成，求最少的个数。第一个方法，没考虑边界，超时80%，第二AC
n = int(sys.stdin.readline().strip())
arr = list(map(int, sys.stdin.readline().strip().split(" ")))
money = int(sys.stdin.readline().strip())
class Solution:
def getLeastquan(self, money, arr, n):
if min(arr) > money:
return -1
if money in arr:
return 1
min_count = money
for i in range(n):
count_num = self.getLeastquan(money - arr[i], arr, n) + 1
if count_num < min_count:
min_count = count_num
return min_count
def getLeastCoins(self, money, arr, n):
dicts = {}
if min(arr) > money:
return -1
dicts = {0:0}
for i in range(1, money+1):
dicts[i] = money + 1
for j in arr:
if j <= i:
dicts[i] = min(dicts[i], dicts[i-j] + 1)
if dicts[money] == money + 1:
return -1
else:
return dicts[money]
# print(Solution().getLeastquan(money, arr, n))
print(Solution().getLeastCoins(money, arr, n))
