(B卷,100分)- 斗地主之顺子（Java & JS & Python）

题目描述

在斗地主扑克牌游戏中，扑克牌由小到大的顺序为：3,4,5,6,7,8,9,10,J,Q,K,A,2，玩家可以出的扑克牌阵型有：单张、对子、顺子、飞机、炸弹等。

其中顺子的出牌规则为：由至少5张由小到大连续递增的扑克牌组成，且不能包含2。

例如：{3,4,5,6,7}、{3,4,5,6,7,8,9,10,J,Q,K,A}都是有效的顺子；而{J,Q,K,A,2}、 {2,3,4,5,6}、{3,4,5,6}、{3,4,5,6,8}等都不是顺子。

给定一个包含13张牌的数组，如果有满足出牌规则的顺子，请输出顺子。

如果存在多个顺子，请每行输出一个顺子，且需要按顺子的第一张牌的大小（必须从小到大）依次输出。

如果没有满足出牌规则的顺子，请输出No。

输入描述

13张任意顺序的扑克牌，每张扑克牌数字用空格隔开，每张扑克牌的数字都是合法的，并且不包括大小王：2 9 J 2 3 4 K A 7 9 A 5 6

不需要考虑输入为异常字符的情况

输出描述

组成的顺子，每张扑克牌数字用空格隔开：3 4 5 6 7

用例

输入	2 9 J 2 3 4 K A 7 9 A 5 6
输出	3 4 5 6 7
说明	13张牌中，可以组成的顺子只有1组：3 4 5 6 7。

输入	2 9 J 10 3 4 K A 7 Q A 5 6
输出	3 4 5 6 7 9 10 J Q K A
说明	13张牌中，可以组成2组顺子，从小到大分别为：3 4 5 6 7 和 9 10 J Q K A

输入	2 9 9 9 3 4 K A 10 Q A 5 6
输出	No
说明	13张牌中，无法组成顺子。

题目解析

先看一个例子：

3 4 5 6 6 7 7 8 9 10

这个例子该输出什么呢？

如果是优先最长顺子的话，那么应该输出：

3 4 5 6 7 8 9 10

如果是优先最多顺子的话，那么应该输出：

3 4 5 6 7

6 7 8 9 10

下面提供两种解法，分别实现优先最长顺子解法，和优先最多顺子解法。

2023.07.10

之前有考友在评论区反馈优先最长顺子解法的通过率是80%，今天评论区又有一个考友提供了一个用例：

3 4 5 6 7 3 4 5 6 7 A A A

之前，优先最长顺子解法是基于栈结构实现的，在测试该用例时，产生死循环。因此我怀疑20%未通过的用例就是类似于这个。

现在我对优先最长顺子解法做了更新优化，已支持该类型用例，大家考试时可以尝试使用优先最长顺子解法。

优先最长顺子解法

我的解题思路如下：

首先定义一个mapToNum方法，即将字符串牌面映射为数值。具体映射关系可看代码中mapToNum方法的实现。

然后，将输入的牌数组，按照mapToNum映射的数值，进行升序排序。

之后，我创建多个顺子容器，外层遍历牌数组，内层遍历顺子容器：

如果顺子容器是空的，则直接将当前牌加入该顺子容器
如果顺子容器不是空的，则比较当前牌cur 和顺子容器尾牌tail

如果cur – tail = 1，则当前牌cur可以加入当前顺子尾部。
如果cur – tail != 1，则当前牌cur不能加入当前顺子尾部，我们应该继续尝试将cur拼接到下一个顺子容器的尾部。

按照上面逻辑，我们最后可以得到多个顺子容器，我们需要过滤掉其中长度小于5的顺子，如果过滤完后没有了，则打印输出“No”，如果过滤完后还有，则剩余顺子容器按照第一张牌数值从小到大排序后，依次打印。

Java算法源码

import java.util.*;
import java.util.stream.Collectors;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String[] cards = sc.nextLine().split(" ");
    getResult(cards);
  }

  public static void getResult(String[] cards) {
    Arrays.sort(cards, (a, b) -> mapToNum(a) - mapToNum(b));

    ArrayList<LinkedList<String>> straights = new ArrayList<>();
    straights.add(creatStraight(cards[0]));

    outer:
    for (int i = 1; i < cards.length; i++) {
      String card = cards[i];

      for (LinkedList<String> s : straights) {
        if (mapToNum(card) - mapToNum(s.getLast()) == 1) {
          s.add(card);
          continue outer;
        }
      }

      straights.add(creatStraight(card));
    }

    List<LinkedList<String>> collect =
        straights.stream().filter(straight -> straight.size() >= 5).collect(Collectors.toList());

    if (collect.size() == 0) {
      System.out.println("No");
      return;
    }

    collect.stream()
        .sorted((a, b) -> mapToNum(a.getFirst()) - mapToNum(b.getFirst()))
        .forEach(straight -> System.out.println(String.join(" ", straight)));
  }

  public static LinkedList<String> creatStraight(String card) {
    LinkedList<String> straight = new LinkedList<>();
    straight.add(card);
    return straight;
  }

  public static int mapToNum(String card) {
    switch (card) {
      case "J":
        return 11;
      case "Q":
        return 12;
      case "K":
        return 13;
      case "A":
        return 14;
      case "2":
        return 16;
      default:
        return Integer.parseInt(card);
    }
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  const cards = line.split(" ");
  getResult(cards);
});

function getResult(cards) {
  cards.sort((a, b) => mapToNum(a) - mapToNum(b));

  let staights = [[cards[0]]];

  outer: for (let i = 1; i < cards.length; i++) {
    const card = cards[i];

    for (let s of staights) {
      if (mapToNum(card) - mapToNum(s.at(-1)) == 1) {
        s.push(card);
        continue outer;
      }
    }

    staights.push([card]);
  }

  staights = staights.filter((staight) => staight.length >= 5);

  if (staights.length == 0) return console.log("No");

  staights
    .sort((a, b) => mapToNum(a[0]) - mapToNum(b[0]))
    .forEach((s) => console.log(s.join(" ")));
}

function mapToNum(card) {
  switch (card) {
    case "J":
      return 11;
    case "Q":
      return 12;
    case "K":
      return 13;
    case "A":
      return 14;
    case "2":
      return 16;
    default:
      return parseInt(card);
  }
}

Python算法源码

# 输入获取
cards = input().split()


def mapToNum(card):
    if card == "J":
        return 11
    elif card == "Q":
        return 12
    elif card == "K":
        return 13
    elif card == "A":
        return 14
    elif card == "2":
        return 16
    else:
        return int(card)


# 算法入口
def getResult():
    cards.sort(key=lambda x: mapToNum(x))

    straights = [[cards[0]]]

    for i in range(1, len(cards)):
        card = cards[i]

        flag = True

        for straight in straights:
            if mapToNum(card) - mapToNum(straight[-1]) == 1:
                straight.append(card)
                flag = False
                break

        if flag:
            straights.append([card])

    straights = list(filter(lambda x: len(x) >= 5, straights))

    if len(straights) == 0:
        print("No")
        return

    straights.sort(key=lambda x: mapToNum(x[0]))

    for straight in straights:
        print(" ".join(straight))


# 调用算法
getResult()

优先最多顺子解法

我的解题策略如下：

首先定义一个长度为15的数组count，分别记录2~A扑克牌的数量，其中2~A扑克牌分别对应索引2~14。

再定义一个total变量，记录总牌数。

然后，开始找五张顺子，查找索引 i 范围依次是：3~7，4~8，5~9，6~10，…，10~14

如果对应范围的每一个count[i] 都大于 0，则对应范围可以形成五张顺子，只要形成五张顺子，则

total -= 5
范围内每一个 count[i] -= 1

当把五张顺子找完后，继续检查total 是否大于 0，若total > 0，则说明还有剩余牌，此时我们外层遍历每一个顺子，内层遍历每一个剩余牌，如果剩余牌可以追加到顺子尾巴，形成新顺子，则更新顺子尾巴。

最后，打印每一个顺子即可。

注意，由于我们找五张顺子时，是按照从左到右查找的，因此顺子找出来后就是符合要求顺序的，因此不需要额外排序。

Java算法源码

import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String[] cards = sc.nextLine().split(" ");
    getResult(cards);
  }

  public static void getResult(String[] cards) {
    // 总牌数
    int total = cards.length;

    // 记录每张牌的数量
    int[] count = new int[15];
    for (String card : cards) {
      int num = mapToNum(card);
      count[num]++;
    }

    // 记录顺子，顺子表示为数组，数组含义：[起始牌，结束牌]
    ArrayList<int[]> straights = new ArrayList<>();

    int from = 3;
    while (from <= 10) {
      // 先求五张的顺子
      if (isStraight(count, from, from + 4)) {
        // 如果可以组成五张顺子，则记录该顺子
        straights.add(new int[] {from, from + 4});
        // 总牌数减5
        total -= 5;
        // 对应的牌的数量减1
        for (int j = from; j <= from + 4; j++) count[j]--;
      } else {
        from++;
      }
    }

    // 如果五张的顺子求解完后，还有剩余牌
    if (total > 0) {
      // 则尝试将剩余牌追加到五张顺子后面
      for (int[] straight : straights) {
        for (int i = 3; i <= 14; i++) {
          if (count[i] > 0 && i - straight[1] == 1) {
            straight[1] = i;
            count[i]--;
          }
        }
      }
    }

    // 如果没有顺子，则返回No
    if (straights.size() == 0) {
      System.out.println("No");
      return;
    }

    // 如果有顺子，则打印顺子
    for (int[] straight : straights) {
      int start = straight[0];
      int end = straight[1];

      StringJoiner sj = new StringJoiner(" ");
      for (int i = start; i <= end; i++) sj.add(mapToCard(i));
      System.out.println(sj);
    }
  }

  public static boolean isStraight(int[] count, int start, int end) {
    int i = start;
    for (; i <= end; i++) {
      if (count[i] == 0) break;
    }
    return i > end;
  }

  public static int mapToNum(String card) {
    switch (card) {
      case "J":
        return 11;
      case "Q":
        return 12;
      case "K":
        return 13;
      case "A":
        return 14;
      default:
        return Integer.parseInt(card);
    }
  }

  public static String mapToCard(int num) {
    switch (num) {
      case 11:
        return "J";
      case 12:
        return "Q";
      case 13:
        return "K";
      case 14:
        return "A";
      default:
        return num + "";
    }
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  const cards = line.split(" ");
  getResult(cards);
});

function getResult(cards) {
  // 总牌数
  let total = cards.length;

  // 记录每张牌的数量
  const count = new Array(15).fill(0);
  for (let card of cards) {
    const num = mapToNum(card);
    count[num]++;
  }

  // straights记录顺子，其元素是顺子，顺子表示为数组：[起始牌，结束牌]
  const straights = [];

  let from = 3;
  while (from <= 10) {
    // 先求五张的顺子
    if (isStraights(count, from, from + 4)) {
      // 如果可以组成五张顺子，则记录该顺子
      straights.push([from, from + 4]);
      // 总牌数减5
      total -= 5;
      // 对应的牌的数量减1
      for (let j = from; j <= from + 4; j++) count[j]--;
    } else {
      from++;
    }
  }

  // 如果五张的顺子求解完后，还有剩余牌
  if (total > 0) {
    // 则尝试将剩余牌追加到五张顺子后面
    for (let straight of straights) {
      for (let i = 3; i <= 14; i++) {
        if (count[i] > 0 && i - straight[1] == 1) {
          straight[1] = i;
          count[i]--;
        }
      }
    }
  }

  // 如果没有顺子，则返回No
  if (straights.length == 0) {
    console.log("No");
    return;
  }

  // 如果有顺子，则打印顺子
  for (let [start, end] of straights) {
    const ans = [];
    for (let i = start; i <= end; i++) ans.push(mapToCard(i));
    console.log(ans.join(" "));
  }
}

function isStraights(count, start, end) {
  let i = start;
  for (; i <= end; i++) {
    if (count[i] == 0) break;
  }
  return i > end;
}

function mapToNum(card) {
  switch (card) {
    case "J":
      return 11;
    case "Q":
      return 12;
    case "K":
      return 13;
    case "A":
      return 14;
    default:
      return parseInt(card);
  }
}

function mapToCard(num) {
  switch (num) {
    case 11:
      return "J";
    case 12:
      return "Q";
    case 13:
      return "K";
    case 14:
      return "A";
    default:
      return num + "";
  }
}

Python算法源码

# 输入获取
cards = input().split()


def mapToCard(num):
    if num == 11:
        return "J"
    elif num == 12:
        return "Q"
    elif num == 13:
        return "K"
    elif num == 14:
        return "A"
    else:
        return str(num)


def mapToNum(card):
    if card == "J":
        return 11
    elif card == "Q":
        return 12
    elif card == "K":
        return 13
    elif card == "A":
        return 14
    else:
        return int(card)


def isStraights(count, start, end):
    i = start
    while i <= end:
        if count[i] == 0:
            break
        else:
            i += 1
    return i > end


# 算法入口
def getResult():
    # 总牌数
    total = len(cards)

    # 记录每张牌的数量
    count = [0] * 15
    for card in cards:
        num = mapToNum(card)
        count[num] += 1

    # 记录顺子，顺子表示为数组，数组含义：[起始牌，结束牌]
    straights = []

    s = 3
    while s < 11:
        # 先求五张的顺子
        if isStraights(count, s, s + 4):
            # 如果可以组成五张顺子，则记录该顺子
            straights.append([s, s + 4])
            # 总牌数减5
            total -= 5
            # 对应的牌的数量减1
            for j in range(s, s + 5):
                count[j] -= 1
        else:
            s += 1

    # 如果五张的顺子求解完后，还有剩余牌
    if total > 0:
        # 则尝试将剩余牌追加到五张顺子后面
        for straight in straights:
            for i in range(3, 15):
                if count[i] > 0 and i - straight[1] == 1:
                    straight[1] = i
                    count[i] -= 1

    # 如果没有顺子，则返回No
    if len(straights) == 0:
        print("No")
        return

    # 如果有顺子，则打印顺子
    for start, end in straights:
        ans = [mapToCard(num) for num in range(start, end + 1)]
        print(" ".join(ans))


# 调用算法
getResult()

免责声明：

1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

3、原文链接：https://moreit.club/?blog=b%e5%8d%b7100%e5%88%86-%e6%96%97%e5%9c%b0%e4%b8%bb%e4%b9%8b%e9%a1%ba%e5%ad%90%ef%bc%88java-js-python%ef%bc%89，转载请注明出处。

2024华为OD机试题库