xampp网站后台,html代码图片,哪些彩票网站可做代理赚钱,seo网站诊断书文章目录 问题描述解题思路分析1. 数据预处理2. 特殊情况处理3. 普通情况计算4. 结果输出 Java代码实现复杂度分析与优化 在经典德州扑克中#xff0c;“葫芦”是一种较强的牌型。它由五张牌组成#xff0c;其中三张牌面值相同#xff0c;另外两张牌面值也相同。本文将探讨一… 文章目录 问题描述解题思路分析1. 数据预处理2. 特殊情况处理3. 普通情况计算4. 结果输出 Java代码实现复杂度分析与优化 在经典德州扑克中“葫芦”是一种较强的牌型。它由五张牌组成其中三张牌面值相同另外两张牌面值也相同。本文将探讨一个有趣的变形问题在限定总牌面值的情况下如何找到符合规则的最大“葫芦”组合。
问题描述
我们需要从给定的一组牌中找到一个满足以下条件的“葫芦”组合
该组合由三张相同牌面值的牌 (a) 和两张相同牌面值的牌 (b) 组成牌面值的总和不能超过指定的最大值 max在多个可能组合中优先选择牌面值 (a) 较大的组合若 (a) 相同则选择 (b) 较大的组合。
牌面值遵循德州扑克的大小规则即 A1 K13 Q12 J11 10 9 … 2。
解题思路分析
1. 数据预处理
首先我们需要统计输入牌组中每张牌的数量。这样做可以快速识别哪些牌出现了三次及以上用于构成牌 (a)哪些牌出现了两次及以上用于构成牌 (b)。通过一个哈希映射HashMap来实现统计能够保证在 (O(n)) 时间复杂度内完成遍历和计数。
2. 特殊情况处理
根据题目中的描述A牌1具有特殊的地位。为了最大化组合的大小我们需优先考虑是否能使用A作为三张牌或两张牌的一部分并在满足条件的情况下更新“葫芦”组合的值。
若 A 出现了三次或更多则A可能作为三张牌中的 (a)。在这种情况下我们需要在其他牌中找到数量至少为2的牌 (b)并确保该组合的牌面和在最大值 max 之内。若 A 出现了两次则A可能作为两张牌中的 (b)。在这种情况下我们需要在其他牌中找到数量至少为3的牌 (a)并判断该组合是否符合最大值要求。
3. 普通情况计算
当 A 不能参与组合或未能找到符合条件的组合时我们可以在其他牌中寻找“葫芦”
从具有三张相同牌面值的牌中选择最大的作为 (a)从具有两张相同牌面值的牌中选择最大的作为 (b)比较多个组合的总和以确保不会超过最大值 max。
4. 结果输出
在所有符合条件的“葫芦”组合中我们输出最大牌面值的 (a) 和 (b) 值若没有符合条件的组合则输出 [0, 0]。
Java代码实现
以下是完整的 Java 实现代码 import java.util.HashMap;
import java.util.Map;public class bigestHulu {public static int[] solution(int n, int max, int[] array) {// 由于最大A的牌面值为1所以要特殊考虑// 1. 首先用map记录array中每个元素出现的次数MapInteger, Integer map new HashMap();// 为了后面特殊考虑map.put(1,0);for (int card : array) {map.put(card, map.getOrDefault(card, 0) 1);}int x 0; // 三张相同的牌面值int y 0; // 两张相同的牌面值// 2.1 A出现3次以上if (map.get(1) 3){// 遍历map找到最大的bfor (Integer b : map.keySet()) {if (b ! 1 map.get(b) 2){// 没有爆牌if (1 * 3 b * 2 max){if (b y){x 1;y b;}}}}return new int[]{x, y};}// 2.2 A出现2次if (map.get(1) 2){// 遍历map找到最大的bfor (Integer b : map.keySet()) {if (b ! 1 map.get(b) 3){// 没有爆牌if (1 * 2 b * 3 max){if (b y){x b;y 1;}}}}return new int[]{x, y};}// 3. A不被选择的情况for (Integer a : map.keySet()) {if (map.get(a) 3){for (Integer b : map.keySet()) {if (b ! a map.get(b) 2){// 没有爆牌if (a * 3 b * 2 max){// 规则是优先比较牌a的大小若牌a相同则再比较牌b的大小if (a x || (a x b y)){x a;y b;}}}}}}if (x 0 y 0){return new int[]{0, 0};}else {return new int[]{x, y};}}public static void main(String[] args) {// Add your test cases hereSystem.out.println(java.util.Arrays.equals(solution(9, 34, new int[]{6, 6, 6, 8, 8, 8, 5, 5, 1}), new int[]{8, 5}));System.out.println(java.util.Arrays.equals(solution(9, 37, new int[]{9, 9, 9, 9, 6, 6, 6, 6, 13}), new int[]{6, 9}));System.out.println(java.util.Arrays.equals(solution(9, 40, new int[]{1, 11, 13, 12, 7, 8, 11, 5, 6}), new int[]{0, 0}));}}
复杂度分析与优化
时间复杂度主循环遍历了牌组中的元素并将其计数复杂度为 (O(n))。随后对计数结果进行两重嵌套的选择在所有可能的三张和两张牌中查找最大组合这部分复杂度约为 (O(k^2))其中 (k) 是去重后牌面值的数量。空间复杂度使用了一个 HashMap 来存储牌的计数空间复杂度为 (O(k))。
外链找到最大“葫芦”组合
