难度: Hard
运行时间: 387 ms
内存: 19.7 MB
class Solution:
def maxGroupNumber(self, tiles: List[int]) -> int:
count = Counter(tiles)
dp = {(0, 0): 0} # dp[i, j]: 遍历到num时，要求(num + 1)保留i个、(num + 2)保留j个时所能得到的最大牌组数
for num in sorted(count):
new = defaultdict(int)
x, y, z = count[num], count[num + 1], count[num + 2]
for (i, j), c in dp.items():
# 用num, num + 1, num + 2组成k个顺子
for k in range(3):
# 能够组成k个顺子且满足保留要求
if i + k <= x and j + k <= y and k <= z:
new[j + k, k] = max(new[j + k, k], c + (x - i - k) // 3 + k)
dp = new
return max(dp.values())
本题解采用动态规划的方法来决定最大牌组数。首先，使用Counter统计每张牌的数量。定义状态dp[i, j]表示当考虑到当前数字num时，并且(num+1)剩下i张，(num+2)剩下j张时，可以形成的最大组数。遍历每个数字num，对于每个num，我们查看可以使用当前num及其后两个数字(num+1和num+2)来形成多少组顺子。考虑到num, num+1, num+2可以组成的顺子数量，并更新状态。最后，dp字典中的最大值即为答案。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def maxGroupNumber(self, tiles: List[int]) -> int:
count = Counter(tiles) # 统计每个数字的出现次数
dp = {(0, 0): 0} # 初始化dp字典，dp[i, j]表示当(num+1)剩i张，(num+2)剩j张时的最大组数
for num in sorted(count): # 对牌数进行排序
new = defaultdict(int) # 新的dp状态
x, y, z = count[num], count[num + 1], count[num + 2] # 当前num及后两个数字的牌数
for (i, j), c in dp.items(): # 遍历当前的dp状态
for k in range(3): # 顺子的可能数量为0到2
if i + k <= x and j + k <= y and k <= z: # 检查是否可以形成k个顺子
new[j + k, k] = max(new[j + k, k], c + (x - i - k) // 3 + k) # 更新状态
dp = new # 更新dp
return max(dp.values()) # 返回dp中的最大值
在这个动态规划设计中，`dp[i, j]`表示在处理到当前数字`num`时，若`(num+1)`剩余`i`张，`(num+2)`剩余`j`张时，可以得到的最大组数。这个设计利用了牌的有序属性和连续性。动态规划的状态转移保证了每一步都是基于前一状态的最优解来进行更新的。通过枚举在当前数字`num`下，利用不同数量的`num`，`num+1`和`num+2`来形成顺子的可能性（即循环变量`k`的使用），可以确保这三个数字能组成的所有有效组合均被考虑。此外，状态转移考虑了所有可能的`i`和`j`的值，确保了状态空间的完整覆盖。
这一计算方法的选择基于如何最大化使用当前数字`num`形成的组数。这里`x`是`num`的数量，`i`是之前状态中`num+1`的剩余数量，`k`是在当前状态决定使用的组成顺子的数量。`x - i - k`表示在形成`k`个顺子后，`num`还剩下的数量。将这个剩余数量除以3是因为三张相同的牌可以单独形成一个组。因此，`(x - i - k) // 3`表示除了形成顺子外，剩余的`num`还可以独立形成的组数。加上`k`（已形成顺子的组数）得到的总和就是当前状态可以得到的最大组数。
在这种情况下，可以认为`num+1`或`num+2`的牌数为0。这是因为在实际的计数中，任何未明确出现的数字其数量默认为0。因此，在动态规划过程中，当我们查看`num+1`或`num+2`的牌数时，若它们不存在于`Counter`对象中，它们的值将被视为0。这种处理自然地适应了边界条件，无需特殊处理即可在状态转移中正确使用。