【华为OD题库-087】最长的顺子-Java

本文主要是介绍【华为OD题库-087】最长的顺子-Java，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

题目描述
斗地主起源于湖北十堰房县，据说是一位叫昊修全的年轻人根据当地流行的扑克玩法"跑得快"改编的，如今已风靡整个中国，并流行于互联网上。
牌型:
单顺，又称顺子，最少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(大王)，每种牌除大小王外有四种花色(共有13×4+2张牌)
输入描述
输入的第一行为当前手中的牌
输入的第二行为已经出过的牌(包括对手出的和自己出的牌)
输出描述
最长的顺子
对手可能构成的最长的顺子(如果有相同长度的顺子，输出牌面最大的那一个)，如果无法构成顺子，则输出NO-CHAIN。
示例
示例1
输入
3-3-3-4-4-5-5-6-7-8-9-10-J-Q-K-A-A-A-A
4-5-6-7-8-8-8
输出
9-10-J-Q-K
示例2
输入
3-3-3-3-8-8-8-8
K-K-K-K
输出
NO-CHAIN
说明
剩余的牌无法构成顺子

思路

题不难，但是边界计算最繁琐

顺子只可能在这个范围(记作字符串sz)：3-4-5-6-7-8-9-10-J-Q-K-A，也就是结果是输出该字符串的一个子串，输出形式是sz.subString(i,j)，为了统一长度，可以将10这个两位数换一个任意字母表示，比如M，sz变为：3-4-5-6-7-8-9-M-J-Q-K-A。
根据已经出的牌和当前手上的牌，可以得到每种牌的剩余量（或者直接正向统计，统计每种牌出现的次数，大小王和2没必要统计，无论剩余多少张，都不影响顺子的判断）。用hashmap统计，命名为freqMap，key使用单个字符代表牌种类，val代表该牌已经出现的次数。
因为顺子长度相等时，取牌面相对较大的值，所以可以从右向左遍历sz。
设初始右边界right=sz.length-1，顺子长度length=0;开始遍历：
J初始指向右边界，记录初始值k=J，左移J，直到J位置的牌剩余个数为0（因为sz有-连接符，所以每次向左移动两个单位，j当前指向的值为sz.charAt(j)，将它作为key值在freqMap中查找可以得到个数，如果个数小于4，说明该牌还有剩余）
此时计算从j到k的长度为：(k-J)/2，除2的原因还是因为有链接符“-”，如果该长度不小于5说明能构成顺子，因为要求最大长度的顺子（等长取牌面大的值），所以只有当长度不小于5且大于上次的长度，才能更新right和length。
更新完成后，J指向的牌剩余数量为0，从J结尾必不可能构成顺子，所以直接将j继续左移两个单位。
当遍历完整个SZ后，可以得到最长顺子（根据右边界和长度确定左边界为：right - length * 2 + 2，记得把最初的M替换为10）

题解

package hwod;import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class TheLongestShunzi {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String curPoker = sc.nextLine();String usedPoker = sc.nextLine();System.out.println(theLongestShunzi(curPoker + "-" + usedPoker));}private static String theLongestShunzi(String usePoker) {Map<Character, Integer> freqMap = new HashMap<>();String[] used = usePoker.replaceAll("10", "M").split("-");String sz = "3-4-5-6-7-8-9-M-J-Q-K-A";for (String s : used) {if (!"2BC".contains(s)) {freqMap.put(s.charAt(0), freqMap.getOrDefault(s.charAt(0), 0) + 1);}}int right = sz.length() - 1, length = 0;int j = sz.length() - 1;while (j >= 0) {int k = j;while (j >= 0 && freqMap.getOrDefault(sz.charAt(j), 0) < 4) j -= 2;int n = (k - j) / 2;if (n > length && n >= 5) {length = n;right = k;}j -= 2;}if (length == 0) return "NO-CHAIN";return sz.substring(right - length * 2 + 2, right + 1).replaceAll("M", "10");}
}