Kimi LeetCode LCP 36. 最多牌组数 Java实现

根据已收集的信息我来为你提供 LCP 36. 最多牌组数 的 Java 实现。题目分析这道题是经典的麻将牌组最大化问题每组牌可以是- 刻子三张相同数值的牌如 [7,7,7]- 顺子三张连续数值的牌如 [4,5,6]核心难点贪心策略不成立。例如 [1,1,1,2,2,2,3,4,4,4]优先顺子只能得到2组但最优解是3组刻子而 [1,1,1,2,2,3,3]优先刻子只能得到1组但最优解是2组顺子 [1,2,3],[1,2,3]。因此需要使用 动态规划 来解决。DP 状态设计设 dp[i][t1][t2] 表示处理到第 i 种牌按数值排序去重后- t1 以 [i-1, i, i1] 形式开头的顺子数量即用到当前牌 i 和下一个牌 i1 的顺子数- t2 以 [i, i1, i2] 形式开头的顺子数量关键观察3个顺子等价于3个刻子所以每种顺子数量只需枚举 0, 1, 2 三种情况。Java 实现javaimport java.util.*;class Solution {// 初始化一个3x3的DP数组初始值为负无穷表示不可达private int[][] getArr() {int[][] res new int[3][3];for (int i 0; i 3; i) {for (int j 0; j 3; j) {res[i][j] Integer.MIN_VALUE;}}return res;}public int maxGroupNumber(int[] tiles) {// 1. 排序并统计每种牌的出现次数Arrays.sort(tiles);int[] nums new int[tiles.length]; // 去重后的牌面值int[] cnt new int[tiles.length]; // 每种牌的出现次数int idx 0;for (int i 0; i tiles.length; i) {if (i 0 || tiles[i] ! tiles[i - 1]) {nums[idx] tiles[i];cnt[idx] 1;idx;} else {cnt[idx - 1];}}// 2. DP 转移// prev[t1][t2]: 上一个牌面值的状态// next[t1][t2]: 当前牌面值的状态int[][] prev null;int[][] next getArr();int prevK -1; // 上一个处理的牌面值next[0][0] 0; // 初始状态0个顺子0个组for (int i 0; i idx; i) {prev next;next getArr();if (prevK 1 nums[i]) {// 当前牌与上一个牌面值连续可以形成顺子// t1: 以 [i-1, i, i1] 开头的顺子数用到当前牌和下一个牌// t2: 以 [i, i1, i2] 开头的顺子数// t3: 以 [i-2, i-1, i] 开头的顺子数来自prev的状态for (int t1 0; t1 3; t1) {for (int t2 0; t2 3; t2) {for (int t3 0; t3 3; t3) {// t3个顺子 [i-2,i-1,i] 消耗了t3张当前牌// t1个顺子 [i-1,i,i1] 消耗了t1张当前牌// t2个顺子 [i,i1,i2] 消耗了t2张当前牌// 剩余牌组成刻子if (t1 t2 t3 cnt[i]) {next[t1][t2] Math.max(next[t1][t2],prev[t3][t1] t3 (cnt[i] - t1 - t2 - t3) / 3);}}}}} else {// 当前牌与上一个牌面值不连续无法形成跨牌面的顺子// 只能将当前牌的剩余部分组成刻子// t1: 以 [i, i1, i2] 开头的顺子数留给下一个连续牌用for (int t1 0; t1 cnt[i] t1 3; t1) {next[0][t1] prev[0][0] (cnt[i] - t1) / 3;}}prevK nums[i];}// 最终答案处理完所有牌后没有未完成的顺子return next[0][0];}}关键点解释要点 说明状态压缩 dp[t1][t2] 只需3x3因为3个顺子3个刻子顺子数只需枚举02离散化 先排序去重将 tiles 转为 (数值, 次数) 的数组连续性判断 prevK 1 nums[i] 判断当前牌与上一个是否连续转移方程 next[t1][t2] max(prev[t3][t1] t3 (cnt[i]-t1-t2-t3)/3)不连续处理 牌面值不连续时无法形成顺子只能做刻子且 t1 必须为0复杂度分析- 时间复杂度O(N \log N U \times 27)其中 N 为 tiles.lengthU 为不同牌面值的数量。排序 O(N \log N)DP 转移每层27种状态。- 空间复杂度O(N)用于存储去重后的数组和DP状态。示例验证示例1tiles [2,2,2,3,4]- 排序后2(3张), 3(1张), 4(1张)- 最优[2,2,2] 刻子 或 [2,3,4] 顺子输出 1 ✓示例2tiles [2,2,2,3,4,1,3]- 排序后1(1张), 2(3张), 3(2张), 4(1张)- 最优[1,2,3] [2,3,4]输出 2 ✓