LeetCode冲刺：Day35

发布于 2022-12-12 42 次阅读

1. 找到最接近 0 的数字

难度

Easy
Medium
Hard

完成情况

独立完成
参考思路
参考答案

思路

最接近0的值，其实就是绝对值最小的值。

代码

class Solution:
    def findClosestNumber(self, nums: List[int]) -> int:
        ans = inf
        for num in nums:
            if abs(num) < abs(ans): ans = num
            elif abs(num) == abs(ans): ans = ans if ans > num else num
        return ans

2. 买钢笔和铅笔的方案数

难度

Easy
Medium
Hard

完成情况

独立完成
参考思路
参考答案

思路

看题干是很标准的完全背包求方法的组合数的问题，于是两层循环，外层遍历物品，内层遍历容量，都是从前向后遍历。

不同之处在于，不买也算一个方案，即背包不一定要装满，于是把dp数组初始值设为1即可。

代码

class Solution:
    def waysToBuyPensPencils(self, total: int, cost1: int, cost2: int) -> int:
        cost = [cost1, cost2]
        dp = [1 for i in range(total + 1)]
        for i in range(2):
            for j in range(total + 1):
                if j >= cost[i]: dp[j] += dp[j - cost[i]]
        return dp[total]

3. 设计一个 ATM 机器

难度

Easy
Medium
Hard

完成情况

独立完成
参考思路
参考答案

思路

没打草稿写的，又debug好久。

代码

class ATM:
    account = []
    money = [20, 50, 100, 200, 500]
    n = len(money)
    def __init__(self):
        self.account = [0 for i in range(self.n)]

    def deposit(self, banknotesCount: List[int]) -> None:
        for i in range(self.n):
            self.account[i] += banknotesCount[i]

    def withdraw(self, amount: int) -> List[int]:
        backAccount = list(self.account)
        res = [0 for i in range(self.n)]
        flag = True
        while amount > 0 and flag:
            for i in range(self.n - 1, -1, -1):
                if amount >= self.money[i] and self.account[i] > 0:
                    cnt = min(int(amount / self.money[i]), self.account[i])
                    res[i] += cnt
                    self.account[i] -= cnt
                    amount -= self.money[i] * cnt
                    break
                if i == 0: flag = False
        if amount > 0:
            self.account = backAccount
            return [-1]
        else: return res