class Solution {
public:
int maxGroupNumber(vector<int>& tiles) {
}
};
LCP 36. 最多牌组数
麻将的游戏规则中，共有两种方式凑成「一组牌」：
给定若干数字作为麻将牌的数值（记作一维数组 tiles），请返回所给 tiles 最多可组成的牌组数。
注意：凑成牌组时，每张牌仅能使用一次。
示例 1：
输入：
tiles = [2,2,2,3,4]输出：
1解释：最多可以组合出 [2,2,2] 或者 [2,3,4] 其中一组牌。
示例 2：
输入：
tiles = [2,2,2,3,4,1,3]输出：
2解释：最多可以组合出 [1,2,3] 与 [2,3,4] 两组牌。
提示：
1 <= tiles.length <= 10^51 <= tiles[i] <= 10^9原站题解
java 解法, 执行用时: 137 ms, 内存消耗: 55.4 MB, 提交时间: 2023-09-13 23:56:16
class Solution {
public int maxGroupNumber(int[] tiles) {
int num,tol;
Map<Integer, Integer> countMap = new HashMap<>();
for (int tile : tiles) {
countMap.put(tile,countMap.getOrDefault(tile,0)+1);
}
int[][] dp = new int[5][5];
int[] array = Arrays.stream(tiles).distinct().sorted().toArray();
for (int tile : array) {
int[][] tmp = new int[5][5];
Integer cur = countMap.getOrDefault(tile, 0);
Integer pre = countMap.getOrDefault(tile-1, 0);
Integer first = countMap.getOrDefault(tile-2, 0);
for (int row = 0; row < Math.min(5,pre+1); row++) {
for (int col = 0; col < Math.min(5,cur+1); col++) {
num = Integer.MIN_VALUE;
tol = cur - col;
for (int r = 0; r < Math.min(5,first+1); r++) {
for (int c = 0; c < Math.min(5-row,pre+1-row); c++) {
int shunzi = Math.min(Math.min(2,tol),Math.min(r,c));
for (int i = 0; i <= shunzi; i++) {
num = Math.max(num,i+(r-i)/3+(c-i)/3+(tol-i)/3+dp[r][c+row]);
}
}
}
tmp[row][col] = num;
}
}
dp = tmp;
}
return dp[0][0];
}
}
python3 解法, 执行用时: 532 ms, 内存消耗: 19.9 MB, 提交时间: 2023-09-13 23:55:17
'''
排序后，按顺序遍历tiles中的值，滚动更新顺子的使用数组凑成的最大值。
'''
class Solution:
def maxGroupNumber(self, tiles: List[int]) -> int:
tiles = Counter(tiles)
nums = sorted(tiles)
# dp滚动更新，存储的是num的上一个数last_num组成的结尾为last_num+1和结尾为last_num+2的顺子数
dp = {(0, 0): 0}
# nums中有断层，或者，假如没有num+2，也就是num+1为最大值的时候,动态规划更新d是否正确？
# 因为当num遍历到最大值（断层）时，v1必然是0，那么所有大于0的d1都不会出现在最后一轮的d的循环中;
# 满足条件的只有d1=0的情况，而d1=0的循环中，d也必然是0,新的dp只有(0,0)是有值的,也就是之前d0的分配所组成的最大值;
# 这也符合实际的逻辑，如果没有tiles里面num+1，那就无法构成num-1,num,num+1的顺子和num,num+1,num+2的顺子
for num in nums:
v0, v1 = tiles[num], tiles[num+1]
new_dp = Counter()
# 枚举用num-2,num-1,num 和 num-1,num,num+1能组成的顺子中,num和num+1的使用情况
for (d0, d1), c in dp.items():
# 枚举所有num和num+1已经使用的情况
t0, t1 = v0 - d0, v1 - d1
for d in range(min(t0, t1, 2) + 1):
# num+1变为下一个num,num+1使用情况为:原来使用的 d1 + 当前组成新的顺子使用的 d
# num+2要使用掉 d
k = (d1 + d, d)
# 动态规划, k的使用情况的最大结果为 原来凑成的顺子数 + 新凑出的顺子数 + 剩余num可以组成的刻子数
# 到这里所有num能使用的情况已经枚举完毕，剩余的num必然是按刻子分
# 当前num的使用：
# 组成d0-d1个num-2,num-1,num的顺子，
# 组成d1个num-1,num,num+1的顺子，
# 组成d个num,num+1,num+2个顺子
new_dp[k] = max(new_dp[k], c + d + (t0 - d) // 3)
dp = new_dp
return max(dp.values())