算法题记录 4

3180.执行操作可获得的最大总奖励（1849/2688）

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：

从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。
以整数形式返回执行最优操作能够获得的 最大 总奖励。

涉及知识点

背包、动态规划、位操作

解决思路

很显然的动态规划背包问题，问题在于每个rewardValues[i]选取还是不选取。有转移方程f[i][j]=f[i-1][j] || f[i-1][j-v]，v为rewardValues[i]的值。
但是该题可以进一步算法简化，首先注意到[i]只由[i-1]得来，我们可以直接去掉这一维度变成f[j]=f[j] || f[j-v]。而后模拟选取过程，为了进一步简化发现可以将传统的dp循环过程转换为位操作。f |= (f & ((1 << v) - 1)) << v。

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        f = 1
        for v in sorted(set(rewardValues)):
            f |= (f & ((1 << v) - 1)) << v
        return f.bit_length() - 1

2241.设计一个ATM机器（1616）

一个 ATM 机器，存有 5 种面值的钞票：20 ，50 ，100 ，200 和 500 美元。初始时，ATM 机是空的。用户可以用它存或者取任意数目的钱。

取款时，机器会优先取 较大 数额的钱。

比方说，你想取 $300 ，并且机器里有 2 张 $50 的钞票，1 张 $100 的钞票和1 张 $200 的钞票，那么机器会取出 $100 和 $200 的钞票。
但是，如果你想取 $600 ，机器里有 3 张 $200 的钞票和1 张 $500 的钞票，那么取款请求会被拒绝，因为机器会先取出 $500 的钞票，然后无法取出剩余的 $100 。注意，因为有 $500 钞票的存在，机器 不能 取 $200 的钞票。
请你实现 ATM 类：

ATM() 初始化 ATM 对象。
void deposit(int[] banknotesCount) 分别存入 $20 ，$50，$100，$200 和 $500 钞票的数目。
int[] withdraw(int amount) 返回一个长度为 5 的数组，分别表示 $20 ，$50，$100 ，$200 和 $500 钞票的数目，并且更新 ATM 机里取款后钞票的剩余数量。如果无法取出指定数额的钱，请返回 [-1] （这种情况下 不 取出任何钞票）。

涉及知识点

模拟

解决思路

非常简单的模拟题，按题意模拟过程更新状态即可。

DENOMINATIONS=[20,50,100,200,500]
KINDS=len(DENOMINATIONS)

class ATM:

    def __init__(self):
        self.banknotes=[0]*KINDS

    def deposit(self, banknotesCount: List[int]) -> None:
        for i,count in enumerate(banknotesCount):
            self.banknotes[i]+=count

    def withdraw(self, amount: int) -> List[int]:
        ans=[0]*KINDS

        for i in range(KINDS-1,-1,-1):
            ans[i]=min(amount//DENOMINATIONS[i],self.banknotes[i])
            amount-=ans[i]*DENOMINATIONS[i]
        
        if amount>0:
            return [-1]

        for i,count in enumerate(ans):
            self.banknotes[i]-=count
        
        return ans

3219.切蛋糕的最小总开销2（1789）

有一个 m x n 大小的矩形蛋糕，需要切成 1 x 1 的小块。

给你整数 m ，n 和两个数组：

horizontalCut 的大小为 m - 1 ，其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。
verticalCut 的大小为 n - 1 ，其中 verticalCut[j] 表示沿着垂直线 j 切蛋糕的开销。
一次操作中，你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一：

沿着水平线 i 切开蛋糕，开销为 horizontalCut[i] 。
沿着垂直线 j 切开蛋糕，开销为 verticalCut[j] 。
每次操作后，这块蛋糕都被切成两个独立的小蛋糕。

每次操作的开销都为最开始对应切割线的开销，并且不会改变。

请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。

涉及知识点

贪心算法/最小生成树

解决思路

很显然，该题采取贪心策略，每次选取开销最大的横/竖切法，最后得到的最优值是全局最优。

或者，也可以逆向思路，将切的动作改为1x1的蛋糕拼成mxn的蛋糕，这时变成了最小生成树的问题。

贪心

class Solution:
    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        horizontalCut=[-x for x in horizontalCut]
        verticalCut=[-x for x in verticalCut]

        heapq.heapify(horizontalCut)
        heapq.heapify(verticalCut)

        result=0
        horizParts,vertParts=1,1

        while horizontalCut or verticalCut:
            if not verticalCut or (horizontalCut and horizontalCut[0]<verticalCut[0]):
                result+=-heapq.heappop(horizontalCut)*horizParts
                vertParts+=1
            else:
                result+=-heapq.heappop(verticalCut)*vertParts
                horizParts+=1
        
        return result

最小生成树

class Solution:
    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        horizontalCut.sort()
        verticalCut.sort()
        ans = i = j = 0
        for _ in range(m + n - 2):
            if j == n - 1 or i < m - 1 and horizontalCut[i] < verticalCut[j]:
                ans += horizontalCut[i] * (n - j)  # 上下连边
                i += 1
            else:
                ans += verticalCut[j] * (m - i)  # 左右连边
                j += 1
        return ans

1742.盒子中小球的最大数量（1278）

你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit ，即 n == highLimit - lowLimit + 1）。另有无限数量的盒子，编号从 1 到 infinity 。

你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。

给你两个整数 lowLimit 和 highLimit ，返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。

涉及知识点

暴力枚举、前缀和

解决思路

暴力枚举所有小球编号上每位数字的和，统计数量最多的即可

或者采用前缀和，s[i][j]代表从0到i的小球编号数位和为j的小球数量。那么题意要求的是s[highLimit][j]-s[lowLimit-1][j]，因为限制了小球编号到100001，所以数位和最大值为45，也就是要求max(s[highLimit][j]-s[lowLimit-1][j])这里的j从1到45。于是让i从1到100001预先循环生成前缀和所有情况，最后按上述公式计算求得即可。

暴力枚举

class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        cnt = Counter(
            sum(map(int, str(i))) for i in range(lowLimit, highLimit + 1)
        )
        return max(cnt.values())

前缀和

s = [[0] * 46]
for i in range(1, 100_001):
    s.append(s[i-1][:])
    s[i][sum(map(int, str(i)))] += 1

class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        return max(s[highLimit][j] - s[lowLimit - 1][j] for j in range(1, len(s[0])))

2414.最长的字母序连续子字符串的长度（1222）

字母序连续字符串 是由字母表中连续字母组成的字符串。换句话说，字符串 “abcdefghijklmnopqrstuvwxyz” 的任意子字符串都是 字母序连续字符串 。

例如，”abc” 是一个字母序连续字符串，而 “acb” 和 “za” 不是。
给你一个仅由小写英文字母组成的字符串 s ，返回其 最长 的 字母序连续子字符串 的长度。

涉及知识点

字符串

解决思路

简单题，字母换为数字后比较是否连续递增即可。

class Solution:
    def longestContinuousSubstring(self, s: str) -> int:
        ans=cnt=1
        for x,y in pairwise(map(ord,s)):
            cnt=cnt+1 if x+1==y else 1
            ans=max(ans,cnt)
        return ans

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。