华为OD机试 - 最长的顺子 - 感谢@禁止你发言提供的更简便算法(Java 2023 B卷 200分)

这篇具有很好参考价值的文章主要介绍了华为OD机试 - 最长的顺子 - 感谢@禁止你发言提供的更简便算法(Java 2023 B卷 200分)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

华为OD机试 - 最长的顺子 - 感谢@禁止你发言提供的更简便算法(Java 2023 B卷 200分),华为OD机试(JAVA)真题(A卷+B卷),华为od,java,七日集训,学习,原力计划

华为OD机试 2023B卷题库疯狂收录中,刷题点这里

专栏导读

本专栏收录于《华为OD机试(JAVA)真题(A卷+B卷)》。

刷的越多,抽中的概率越大,每一题都有详细的答题思路、详细的代码注释、样例测试,发现新题目,随时更新,全天CSDN在线答疑。

一、题目描述

斗地主起源于湖北十堰房县,据说是一位叫吴修全的年轻人根据当地流行的扑克玩法”跑得快”改编的,如今已风靡整个中国,并流行于互联网上。

牌型:单顺,又称顺子,最少5张牌,最多12张牌(3…A)不能有2,也不能有大小王,不计花色。

例:3-4-5-6-7-8,7-8-9-10-J-Q,3-4-5-6-7-8-9-10-J-Q-K-A可用的牌3<4<5<6<7<8<9<10<J<Q<K<A<2<B(小王)C(大王),每种牌除大小王外有四种花色(共有13x4+2张牌)。

1、输入

  1. 手上有的牌
  2. 已经出过的牌(包括对手出的和自己出的牌)

2、输出

对手可能构成的最长的顺子(如果有相同长度的顺子,输出牌面最大的那一个)

如果无法构成顺子,则输出NO-CHAIN

二、输入描述

输入的第一行为当前手中的牌

输入的第二行为已经出过的牌

三、输出描述

最长的顺子

输入 输出 说明
3-3-3-3-4-4-5-5-6-7-8-9-10-J-Q-K-A
A-4-5-6-7-8-8-8
9-10-J-Q-K-A

四、解题思路

  1. 定义jqkaMap,进行JQKA的映射转换,便于排序;
  2. 第一行输入当前手中的牌;
  3. 第二行输入已经出过的牌;
  4. 定义集合list,存储当前手中的牌 + 已经出过的牌;
  5. 定义map,存储对手的牌;
    • 全部牌 - 当前手中的牌 - 已经出过的牌;
    • key:3-A,value:每张牌的数量;
  6. 获取最大的龙;
    • 定义集合dragonList,存储符合要求的最大的龙;
    • map倒序遍历,获取符合要求的最大的龙;
      • 有剩余牌时,拼接龙;
      • 当没有牌时,表示能获取到的最大的龙;
      • 如果获取的龙,符合斗地主要求,则直接返回,否则清空dragonList,重新计算;
  7. 如果能获取到的最大的龙,不符合斗地主要求,直接返回NO-CHAIN;
  8. 按指定格式输出。

五、Java算法源码

private static Map<String, Integer> jqkaMap = new HashMap<>();
private static Map<Integer, String> reverseMap = new HashMap<>();

// B(小王)C(大王)
private static String specialStr = "2BC";

static {
    jqkaMap.put("J", 11);
    jqkaMap.put("Q", 12);
    jqkaMap.put("K", 13);
    jqkaMap.put("A", 14);

    reverseMap.put(11, "J");
    reverseMap.put(12, "Q");
    reverseMap.put(13, "K");
    reverseMap.put(14, "A");
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    // 当前手中的牌
    List<Integer> line1 = Arrays.asList(sc.nextLine().split("-")).stream().filter(x->!specialStr.contains(x)).map(x -> {
        if (jqkaMap.containsKey(x)) {
            return String.valueOf(jqkaMap.get(x));
        }
        return x;
    }).mapToInt(Integer::parseInt).boxed().collect(Collectors.toList());

    // 已经出过的牌
    List<Integer> line2 = Arrays.asList(sc.nextLine().split("-")).stream().filter(x->!specialStr.contains(x)).map(x -> {
        if (jqkaMap.containsKey(x)) {
            return String.valueOf(jqkaMap.get(x));
        }
        return x;
    }).mapToInt(Integer::parseInt).boxed().collect(Collectors.toList());

    // 当前手中的牌 + 已经出过的牌
    List<Integer> list = new ArrayList<>();
    list.addAll(line1);
    list.addAll(line2);
    System.out.println(list);

    /**
     * 对手的牌 = 全部牌 - 当前手中的牌 - 已经出过的牌
     *
     * key:3-A,value:每张牌的数量
     */
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < list.size(); i++) {
        Integer s = list.get(i);
        s = jqkaMap.getOrDefault(s, s);
        Integer sum = map.getOrDefault(s, 4);
        map.put(s, --sum);
    }
    System.out.println(map);

    // 获取最大的龙
    List<Integer> dragonList = getDragonList(map);
    // 如果能获取到的最大的龙,不符合斗地主要求,直接返回NO-CHAIN
    if(dragonList.size() < 5){
        System.out.println("NO-CHAIN");
        return;
    }

    // 按指定格式输出
    StringJoiner stringJoiner = new StringJoiner("-");
    dragonList.stream().sorted((o1, o2) -> {
        return o1.compareTo(o2);
    }).map(x -> {
        if (reverseMap.containsKey(x)) {
            String temp = String.valueOf(reverseMap.get(x));
            stringJoiner.add(temp);
            return temp;
        }
        stringJoiner.add(String.valueOf(x));
        return x;
    }).collect(Collectors.toList());
    System.out.println(stringJoiner);
}

/**
 * 获取最大的龙
 * @param map 对手的牌 key:3-A,value:每张牌的数量
 * @return 最大的龙
 */
private static List<Integer> getDragonList(Map<Integer, Integer> map){
    // 获取符合要求的最大的龙
    List<Integer> dragonList = new ArrayList<>();
    // map倒序遍历,获取符合要求的最大的龙
    ListIterator<Map.Entry<Integer, Integer>> mapList = new ArrayList<>(map.entrySet()).listIterator(map.size());
    while (mapList.hasPrevious()) {
        Map.Entry<Integer, Integer> previousMap = mapList.previous();
        // 有剩余牌时,拼接龙
        if (previousMap.getValue() > 0) {
            dragonList.add(previousMap.getKey());
        } else if (previousMap.getValue() == 0) {// 当没有牌时,表示能获取到的最大的龙
            // 如果获取的龙,符合斗地主要求,则直接返回,否则清空dragonList,重新计算
            if(dragonList.size()>=5){
                break;
            }else {
                dragonList = new ArrayList<>();
            }
        }
    }
    System.out.println(dragonList);
    return dragonList;
}

六、感谢@禁止你发言提供的更简单、更优质的算法

解题思路

1、获取输入:当前手中的牌 + 已经出过的牌,并合并字符串,分割为数组;

2、定义char2int map,进行JQKA的映射转换,便于排序;

3、定义reverseMap,int转回JQKA,方便最后打印顺子;

4、定义数组theirPokers表示对手的牌,遍历前述的合并牌数组(当前手中的牌 + 已经出过的牌),每遍历到一张牌,对手的牌对应的数组元素 - 1。

注意:

  1. 数组长度由来:有题目可知,顺子有效的牌为3-14,所以长度为14 - 3 + 1
  2. 为什么-3:有效的顺子牌从3开始,而数组下标需要从0开始

5、动态规划获取最长的顺子,以当前牌结尾的顺子长度只与以前一个牌结尾的顺子长度和当前牌是否可用有关。

  1. 如果对方的牌含有3,则初始值设置为1,否则为0
  2. 定义start记录最长顺子的起始牌
  3. 定义max记录最长顺子的长度
  4. 有剩余牌时,拼接顺子,即以当前牌结尾的顺子长度为以前一个牌结尾的顺子长度 + 1
  5. 没有剩余牌时,顺子长度置为0

注意这里有个优化技巧,由于当前牌的顺子长度只与前一个牌的顺子长度和当前牌是否可用有关,因此我们不需要定义dp数组
可优化为:

int prev = theirPokers[0] > -4 ? 1 : 0;
int current;
int max = Integer.MIN_VALUE;
//记录最长顺子的起始牌
int start = 1;
for (int i = 1; i < theirPokers.length; i++) {
    //有剩余牌时,拼接顺子
    if (theirPokers[i] > -4) {
        current = prev + 1;
        if (current > max) {
            max = current;
            start = i + 3 - max + 1;  //注意这里+3,是由于数组下标和扑克牌之间差了3
        }
        // 无剩余牌,顺子长度置为0
    } else {
        current = 0;
    }
    prev = current;
}

存储空间降低,但可读性差了点。

6、如果符合条件(顺子长度不小于5),则按格式输出

7、如果不符合,则输出NO-CHAIN

优质算法源码

public static void main(String[] args) {
    //获取输入:当前手中的牌 + 已经出过的牌, 并合并
    Scanner scanner = new Scanner(System.in);
    String myPokers = scanner.next();
    String alreadyPokers = scanner.next();
    String[] mergePokers = myPokers.concat("-").concat(alreadyPokers).split("-");

    //为方便后续判断顺子,将JQKA转为int, reverse为供后续打印顺子使用
    Map<Character, Integer> char2int = new HashMap<>();
    char2int.put('J', 11);
    char2int.put('Q', 12);
    char2int.put('K', 13);
    char2int.put('A', 14);
    Map<Integer, Character> reverseMap = char2int.entrySet().stream()
            .collect(Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey));

    // 定义数组表示对手的牌,遍历前面合并牌数组(当前手中的牌 + 已经出过的牌),每遍历到一张牌,对手的牌对应的数组元素 - 1
    // 注意: 数组长度由来:有题目可知,顺子有效的牌为3-14,所以长度为14 - 3 + 1
    // 注意:为什么-3:有效的顺子牌从3开始,而数组下标需要从0开始
    int[] theirPokers = new int[14 - 3 + 1];
    for (String poker : mergePokers) {
        if (poker.length() > 1) {                                      // 10
            theirPokers[Integer.parseInt(poker) - 3]--;
        } else if (char2int.containsKey(poker.charAt(0))) {            //JQKA
            theirPokers[char2int.get(poker.charAt(0)) - 3]--;
        } else if (poker.charAt(0) != '2' && poker.charAt(0) != 'B' && poker.charAt(0) != 'C') {
            theirPokers[Integer.parseInt(poker) - 3]--;
        }
    }

    // 动态规划获取最长的顺子,当前牌的顺子长度只与前一个牌的顺子长度和当前牌是否可用有关
    //如果对方的牌含有3,则初始值设置为1,否则为0
    int prev = theirPokers[0] > -4 ? 1 : 0;
    int current;
    int max = Integer.MIN_VALUE;
    //记录最长顺子的起始牌
    int start = 1;
    for (int i = 1; i < theirPokers.length; i++) {
        //有剩余牌时,拼接顺子
        if (theirPokers[i] > -4) {
            current = prev + 1;
            if (current > max) {
                max = current;
                // 注意这里+3,是由于数组下标和扑克牌之间差了3
                start = i + 3 - max + 1;
            }
            // 无剩余牌,顺子长度置为0
        } else {
            current = 0;
        }
        prev = current;
    }

    // 符合条件
    if (max >= 5) {
        String straight = IntStream.range(start, start + max)
                .mapToObj(poker -> poker > 10 ? reverseMap.get(poker) : poker)
                .map(String::valueOf).collect(Collectors.joining("-"));
        System.out.println(straight);
        //长度小于5, 输出NO-CHAIN
    } else {
        System.out.println("NO-CHAIN");
    }
}

七、效果展示

1、输入

3-3-4-4-5-A-5-6-2-8-3-9-10-Q-7-K-J-10-B
A-4-5-8-8-10-C-6-7-8

2、输出

9-10-J-Q-K-A

3、说明

  1. 拼接两个字符串,排除掉不能成龙的2和大小王;
  2. [3, 3, 4, 4, 5, 14, 5, 6, 8, 3, 9, 10, 12, 7, 13, 11, 10, 14, 4, 5, 8, 8, 10, 6, 7, 8]
  3. 获取对手的牌,{3=1, 4=1, 5=1, 6=2, 7=2, 8=0, 9=3, 10=1, 11=3, 12=3, 13=3, 14=2};
  4. 获取对手的牌能组成的最大的龙,[14, 13, 12, 11, 10, 9];
  5. 数值映射转换9-10-J-Q-K-A。

华为OD机试 - 最长的顺子 - 感谢@禁止你发言提供的更简便算法(Java 2023 B卷 200分),华为OD机试(JAVA)真题(A卷+B卷),华为od,java,七日集训,学习,原力计划


🏆下一篇:华为OD机试 - 荒岛求生 - 栈Stack(Java 2023 B卷 100分)

🏆本文收录于,华为OD机试(JAVA)真题(A卷+B卷)

刷的越多,抽中的概率越大,每一题都有详细的答题思路、详细的代码注释、样例测试,发现新题目,随时更新,全天CSDN在线答疑。

华为OD机试 - 最长的顺子 - 感谢@禁止你发言提供的更简便算法(Java 2023 B卷 200分),华为OD机试(JAVA)真题(A卷+B卷),华为od,java,七日集训,学习,原力计划文章来源地址https://www.toymoban.com/news/detail-726291.html

到了这里,关于华为OD机试 - 最长的顺子 - 感谢@禁止你发言提供的更简便算法(Java 2023 B卷 200分)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【华为OD机试真题】1220 - 斗地主之顺子(JAVA C++ Python JS) | 机试题+算法思路+考点+代码分析

    🍂个人博客首页: KJ.JK   🍂专栏介绍: 华为OD机试真题汇总,定期更新华为OD各个时间阶段的机试真题,每日定时更新,本专栏将使用Python语言进行更新解答,包含真题,思路分析,代码参考,欢迎大家订阅学习

    2024年02月06日
    浏览(55)
  • 华为OD机试-求满足要求的最长子串

    给定一个字符串,只包含字母和数字,按要求找出字符串中的最长(连续)子串的长度,字符串本身是其最长的子串,子串要求: 1、只包含1个字母(a-z,A~Z),其余必须是数字; 2、字母可以在子串中的任意位置; 如果找不到满足要求的子串,如全是字母或全是数字,则返回-1。 字

    2024年02月10日
    浏览(34)
  • 华为OD机试 - 最长公共后缀(Java & JS & Python)

    题目描述 编写一个函数来查找字符串数组中的最长公共后缀; 如果不存在公共后缀,返回固定字符串: @Zero。 补充说明: 字符串长度范围:[2, 1000] 字符串中字符取值范围为[1, 126] 输入描述 无 输出描述 无 用例 输入 [\\\"abc\\\",\\\"bbc\\\",\\\"c\\\"] 输出 \\\"c\\\" 说明 返回公共后缀: c 输入 [\\\"aa\\\",\\\"b

    2024年02月13日
    浏览(56)
  • 华为OD机试之最长连续子序列(Java源码)

    题目描述 有N个正整数组成的一个序列。给定整数sum,求长度最长的连续子序列,使他们的和等于sum,返回此子序列的长度, 如果没有满足要求的序列,返回-1。 输入描述 第一行输入是:N个正整数组成的一个序列 第二行输入是:给定整数sum 输出描述 最长的连续子序列的长

    2024年02月09日
    浏览(44)
  • 华为OD机试之求满足条件的最长子串的长度

    题目描述 给定一个字符串,只包含字母和数字,按要求找出字符串中的最长(连续)子串的长度,字符串本身是其最长的子串,子串要求: 1、 只包含1个字母(a-z, A-Z),其余必须是数字; 2、 字母可以在子串中的任意位置; 如果找不到满足要求的子串,如全是字母或全是数字

    2024年02月05日
    浏览(40)
  • 华为OD机试 - 最长合法表达式(Java & JS & Python & C)

    题目描述 提取字符串中的最长合法简单数学表达式,字符串长度最长的,并计算表达式的值。如果没有,则返回 0 。 简单数学表达式只能包含以下内容: 0-9数字,符号+-* 说明: 所有数字,计算结果都不超过long 如果有多个长度一样的,请返回第一个表达式的结果 数学表达

    2024年02月04日
    浏览(45)
  • 华为OD机试 - 寻找符合要求的最长子串(Java & JS & Python)

    题目描述 给定一个字符串s,找出这样一个子串: 该子串中任意一个字符最多出现2次 该子串不包含指定某个字符 请你找出满足该条件的最长子串的长度 输入描述 第一行为:要求不包含的指定字符,为单个字符,取值范围[0-9a-zA-Z] 第二行为:字符串s,每个字符范围[0-9a-zA-

    2024年02月05日
    浏览(49)
  • 【独家】华为OD机试提供C语言题解 - 事件推送

    华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单 华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典 【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南) 华为od机试,独家整理 已参加机试人员的实战技巧

    2024年02月15日
    浏览(41)
  • 华为OD机试 - 最长子字符串的长度(一)(Java & JS & Python & C)

    题目描述 给你一个字符串 s,首尾相连成一个环形,请你在环中找出 \\\'o\\\' 字符出现了偶数次最长子字符串的长度。 输入描述 输入是一个小写字母组成的字符串 输出描述 输出是一个整数 备注 1 ≤ s.length ≤ 500000 s 只包含小写英文字母 用例 输入 alolobo 输出 6 说明 最长子字符串

    2024年02月01日
    浏览(44)
  • 华为OD机试 - 求满足条件的最长子串的长度 - 双指针(Java 2023 B卷 100分)

    华为OD机试 2023B卷题库疯狂收录中,刷题 点这里 本专栏收录于

    2024年02月11日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包