完美世界笔试

机器学习岗，选择题全是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))

#完美世界##机器学习##笔试题目#