題目描述
手上有一副撲克牌，每張牌按牌面數(shù)字記分（J=11,Q=12,K=13，沒(méi)有大小王)，出牌時(shí)按照以下規(guī)則記分：
- 出單張，記牌面分?jǐn)?shù)，例如出一張2，得分為2
- 出對(duì)或3張，記牌面分?jǐn)?shù)總和再x2，例如出3張3，得分為(3+3+3)x2=18
- 出5張順，記牌面分?jǐn)?shù)總和再x2，例如出34567順，得分為(3+4+5+6+7)x2=50
- 出4張炸彈，記牌面分?jǐn)?shù)總和再x3，例如出4張4，得分為4x4x3=48
求出一副牌最高的得分?jǐn)?shù)
輸入描述
按順序排好的一副牌，最少1張，最多15張。
1-9輸入為數(shù)字1-9，10輸入為數(shù)字0，JQK輸入為大寫字母JQK.
無(wú)需考慮輸入非法的情況，例如輸入字符不在[0-9JQK]范圍或某一張牌超過(guò)4張
輸出描述
最高的得分?jǐn)?shù)
備注
積分規(guī)則中沒(méi)有的出牌方式不支持，例如不支持3帶1、4帶2，不支持5張以上的順，且10JQKA (0JQK1) 不算順。
用例
| 輸入 | 33445677 |
| 輸出 | 67 |
| 說(shuō)明 | 出對(duì)3、對(duì)4、對(duì)7，單張5、6，得分為67; 出34567順，再出單張3、4、7，得分為64 因此最高得分是按對(duì)出，可得到最高分67，輸出結(jié)果67 |
題目解析
本題數(shù)量級(jí)不大，可以考慮暴力破解。
首先定義一個(gè)數(shù)組card_count，數(shù)組索引就是牌分?jǐn)?shù)，數(shù)組元素就是牌數(shù)量
因?yàn)楸绢}中牌面是不連續(xù)的，比如0代表10，但是牌分?jǐn)?shù)是連續(xù)的。
因此，將牌分?jǐn)?shù)作為數(shù)組索引來(lái)看的話，就可以用一個(gè)長(zhǎng)度為5的滑窗來(lái)在card_count中找順子。
由于K牌面分?jǐn)?shù)是13，因此我們只需要定義card_count數(shù)組長(zhǎng)度為14即可，題目用例可得數(shù)組如下：
有了card_count之后，我們就可以開(kāi)始遍歷每一種牌（即遍歷card_count數(shù)組的索引 i ）：
- card_count[i] >= 1，則說(shuō)明當(dāng)前牌面 i 至少有1張，那么此時(shí)可以選擇：
- 出單張，那么總牌數(shù)量 - 1，總分 + i
- 出順子，但是需要先檢查 i+1, i+2, i+3, i+4 牌的數(shù)量是否至少有1張，如果有的話，才可以出順子，那么總牌數(shù)了 - 5，總分+? ( i + (i+1) + (i+2) + (i+3) + (i+4) ) * 2
- card_count[i] >= 2，則說(shuō)明當(dāng)前牌面 i 至少有2張，那么此時(shí)可以選擇出對(duì)子，總牌數(shù)量 - 2，總分 + i * 2 * 2
- card_count[i] >= 3，則說(shuō)明當(dāng)前牌面 i 至少有3張，那么此時(shí)可以選擇出三張，總牌數(shù)量 - 3，總分 + i * 3 * 2
- card_count[i] >= 4，則說(shuō)明當(dāng)前牌面 i 至少有4張，那么此時(shí)可以選擇出炸彈，總牌數(shù)量 - 4，總分 + i * 4 * 3
對(duì)于上面這些出牌策略，我們都可以選或者不選，
比如當(dāng)前card_count[i] >= 2，那么我們可以選擇出對(duì)子，也可以選擇不出對(duì)子
只有這樣，我們才能嘗試出所有出牌的策略組合，這里明顯需要用到遞歸和回溯。
2023.10.29
之前的代碼邏輯中，如下（C語(yǔ)言代碼，其他語(yǔ)言的考友可以當(dāng)成偽代碼看）
上面代碼邏輯是存在重復(fù)探索的。
startIdx 位置的牌，可以從 for 循環(huán)進(jìn)入出牌邏輯，也可以從 遞歸進(jìn)入出牌邏輯，這會(huì)產(chǎn)生冗余探索。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-661542.html
我們可以只基于遞歸來(lái)完成所有出牌策略的探索。只是需要增加 card_count[startIdx] == 0 時(shí)，即 startIdx 位置沒(méi)有牌時(shí)，自動(dòng)遞歸到 startIdx + 1 位置出牌的邏輯。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-661542.html
JS算法源碼
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
const cards = await readline();
// 數(shù)組索引是牌面分?jǐn)?shù), 數(shù)組元素是牌面數(shù)量, 其中 0 索引不用
const card_count = new Array(14).fill(0);
// 統(tǒng)計(jì)各種牌的數(shù)量
for (let card of cards) {
// 1-9輸入為數(shù)字1-9，10輸入為數(shù)字0，JQK輸入為大寫字母JQK
// 1-9 牌面分?jǐn)?shù)就是 1-9, 0的牌面分?jǐn)?shù)是 10, J=11,Q=12,K=13, 可以發(fā)現(xiàn)牌面分?jǐn)?shù)是連續(xù)的，可以和card_count數(shù)組的索引對(duì)應(yīng)起來(lái)
if (card == "0") card_count[10]++;
else if (card == "J") card_count[11]++;
else if (card == "Q") card_count[12]++;
else if (card == "K") card_count[13]++;
else card_count[card - "0"]++;
}
// 記錄最大得分
let max_score = 0;
getMaxScore(card_count, cards.length, 1, 0);
console.log(max_score);
/**
* 獲取最大分?jǐn)?shù)
* @param {*} card_count 各種牌的數(shù)量
* @param {*} unused_card_count 剩余牌的總數(shù)量
* @param {*} i 從哪個(gè)位置開(kāi)始選牌
* @param {*} score 此時(shí)已獲得的總分?jǐn)?shù)
*/
function getMaxScore(card_count, unused_card_count, i, score) {
if (unused_card_count == 0) {
max_score = Math.max(max_score, score);
return;
}
// 沒(méi)有可以出的牌，則繼續(xù)遞歸到i+1開(kāi)始出牌
if (card_count[i] == 0) {
getMaxScore(card_count, unused_card_count, i + 1, score);
}
// 還有可以出的牌，則從i開(kāi)始出牌
// 如果當(dāng)前牌的數(shù)量至少1張
if (card_count[i] >= 1) {
// 策略1、可以嘗試出順子，由于最大的順子是9,10,J,Q,K,因此 i 作為順子起始牌的話，不能超過(guò)9，且后續(xù)牌面 i+1, i+2, i+3, i+4 的數(shù)量都至少有1張
if (
i <= 9 &&
card_count[i + 1] >= 1 &&
card_count[i + 2] >= 1 &&
card_count[i + 3] >= 1 &&
card_count[i + 4] >= 1
) {
card_count[i] -= 1;
card_count[i + 1] -= 1;
card_count[i + 2] -= 1;
card_count[i + 3] -= 1;
card_count[i + 4] -= 1;
// 順子是5張牌，因此出掉順子后，可用牌數(shù)量減少5張，總分增加 (i + (i+1) + (i+2) + (i+3) + (i+4)) * 2
getMaxScore(
card_count,
unused_card_count - 5,
i,
score + (5 * i + 10) * 2
);
// 回溯
card_count[i] += 1;
card_count[i + 1] += 1;
card_count[i + 2] += 1;
card_count[i + 3] += 1;
card_count[i + 4] += 1;
}
// 策略2、出單張
card_count[i] -= 1;
getMaxScore(card_count, unused_card_count - 1, i, score + i);
card_count[i] += 1;
}
// 如果當(dāng)前牌的數(shù)量至少2張，那么可以出對(duì)子
if (card_count[i] >= 2) {
card_count[i] -= 2;
getMaxScore(card_count, unused_card_count - 2, i, score + i * 2 * 2);
card_count[i] += 2;
}
// 如果當(dāng)前牌的數(shù)量至少3張，那么可以出三張
if (card_count[i] >= 3) {
card_count[i] -= 3;
getMaxScore(card_count, unused_card_count - 3, i, score + i * 3 * 2);
card_count[i] += 3;
}
// 當(dāng)前當(dāng)前牌的數(shù)量至少4張，那么可以出炸彈
if (card_count[i] >= 4) {
card_count[i] -= 4;
getMaxScore(card_count, unused_card_count - 4, i, score + i * 4 * 3);
card_count[i] += 4;
}
}
})();
Java算法源碼
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(getResult(sc.nextLine()));
}
// 保存最大分?jǐn)?shù)
static int max_score = 0;
public static int getResult(String cards) {
// 數(shù)組索引是牌面分?jǐn)?shù), 數(shù)組元素是牌面數(shù)量, 其中 0 索引不用
int[] card_count = new int[14];
// 統(tǒng)計(jì)各種牌的數(shù)量
for (int i = 0; i < cards.length(); i++) {
char card = cards.charAt(i);
// 1-9輸入為數(shù)字1-9，10輸入為數(shù)字0，JQK輸入為大寫字母JQK
// 1-9 牌面分?jǐn)?shù)就是 1-9, 0的牌面分?jǐn)?shù)是 10, J=11,Q=12,K=13, 可以發(fā)現(xiàn)牌面分?jǐn)?shù)是連續(xù)的，可以和card_count數(shù)組的索引對(duì)應(yīng)起來(lái)
if (card == '0') card_count[10]++;
else if (card == 'J') card_count[11]++;
else if (card == 'Q') card_count[12]++;
else if (card == 'K') card_count[13]++;
else card_count[card - '0']++;
}
getMaxScore(card_count, cards.length(), 1, 0);
return max_score;
}
/**
* 獲取最大分?jǐn)?shù)
*
* @param card_count 各種牌的數(shù)量
* @param unused_card_count 剩余牌的總數(shù)量
* @param startIdx 從哪個(gè)位置開(kāi)始選牌
* @param score 此時(shí)已獲得的總分?jǐn)?shù)
*/
public static void getMaxScore(int[] card_count, int unused_card_count, int startIdx, int score) {
// 所有牌都打完了
if (unused_card_count == 0) {
// 則比較此時(shí)出牌策略獲得的總分score，和歷史最高分max_score，保留較大者
max_score = Math.max(score, max_score);
return;
}
// 沒(méi)有可以出的牌，則繼續(xù)遞歸到startIdx+1開(kāi)始出牌
if (card_count[startIdx] == 0) {
getMaxScore(card_count, unused_card_count, startIdx + 1, score);
}
// 還有可以出的牌，則從startIdx開(kāi)始出牌
// 如果當(dāng)前牌的數(shù)量至少1張
if (card_count[startIdx] >= 1) {
// 策略1、可以嘗試出順子，由于最大的順子是9,10,J,Q,K,因此 i 作為順子起始牌的話，不能超過(guò)9，且后續(xù)牌面 i+1, i+2, i+3, i+4 的數(shù)量都至少有1張
if (startIdx <= 9
&& card_count[startIdx + 1] >= 1
&& card_count[startIdx + 2] >= 1
&& card_count[startIdx + 3] >= 1
&& card_count[startIdx + 4] >= 1) {
card_count[startIdx] -= 1;
card_count[startIdx + 1] -= 1;
card_count[startIdx + 2] -= 1;
card_count[startIdx + 3] -= 1;
card_count[startIdx + 4] -= 1;
// 順子是5張牌，因此出掉順子后，可用牌數(shù)量減少5張，總分增加 (i + (i+1) + (i+2) + (i+3) + (i+4)) * 2
getMaxScore(card_count, unused_card_count - 5, startIdx, score + (5 * startIdx + 10) * 2);
// 回溯
card_count[startIdx] += 1;
card_count[startIdx + 1] += 1;
card_count[startIdx + 2] += 1;
card_count[startIdx + 3] += 1;
card_count[startIdx + 4] += 1;
}
// 策略2、出單張
card_count[startIdx] -= 1;
getMaxScore(card_count, unused_card_count - 1, startIdx, score + startIdx);
card_count[startIdx] += 1;
}
// 如果當(dāng)前牌的數(shù)量至少2張，那么可以出對(duì)子
if (card_count[startIdx] >= 2) {
card_count[startIdx] -= 2;
getMaxScore(card_count, unused_card_count - 2, startIdx, score + startIdx * 2 * 2);
card_count[startIdx] += 2;
}
// 如果當(dāng)前牌的數(shù)量至少3張，那么可以出三張
if (card_count[startIdx] >= 3) {
card_count[startIdx] -= 3;
getMaxScore(card_count, unused_card_count - 3, startIdx, score + startIdx * 3 * 2);
card_count[startIdx] += 3;
}
// 當(dāng)前當(dāng)前牌的數(shù)量至少4張，那么可以出炸彈
if (card_count[startIdx] >= 4) {
card_count[startIdx] -= 4;
getMaxScore(card_count, unused_card_count - 4, startIdx, score + startIdx * 4 * 3);
card_count[startIdx] += 4;
}
}
}
Python算法源碼
# 輸入獲取
cards = input()
# 保存最大分?jǐn)?shù)
max_score = 0
# 獲取牌的最大得分
def getMaxScore(card_count, unused_card_count, i, score):
"""
獲取最大分?jǐn)?shù)
:param card_count: 各種牌的數(shù)量
:param unused_card_count: 剩余牌的總數(shù)量
:param i: 從哪個(gè)位置開(kāi)始選牌
:param score: 此時(shí)已獲得的總分?jǐn)?shù)
"""
global max_score
# 所有牌都打完了
if unused_card_count == 0:
# 則比較此時(shí)出牌策略獲得的總分score，和歷史最高分max_score，保留較大者
max_score = max(max_score, score)
return
# 沒(méi)有可以出的牌，則繼續(xù)遞歸到i+1開(kāi)始出牌
if card_count[i] == 0:
getMaxScore(card_count, unused_card_count, i + 1, score);
# 還有可以出的牌，則從i開(kāi)始出牌
# 如果當(dāng)前牌的數(shù)量至少1張
if card_count[i] >= 1:
# 策略1、可以嘗試出順子，由于最大的順子是9,10,J,Q,K,因此 i 作為順子起始牌的話，不能超過(guò)9，且后續(xù)牌面 i+1, i+2, i+3, i+4 的數(shù)量都至少有1張
if i <= 9 and card_count[i + 1] >= 1 and card_count[i + 2] >= 1 and card_count[i + 3] >= 1 and card_count[i + 4] >= 1:
card_count[i] -= 1
card_count[i + 1] -= 1
card_count[i + 2] -= 1
card_count[i + 3] -= 1
card_count[i + 4] -= 1
# 順子是5張牌，因此出掉順子后，可用牌數(shù)量減少5張，總分增加 (i + (i+1) + (i+2) + (i+3) + (i+4)) * 2
getMaxScore(card_count, unused_card_count - 5, i, score + (5 * i + 10) * 2)
# 回溯
card_count[i] += 1
card_count[i + 1] += 1
card_count[i + 2] += 1
card_count[i + 3] += 1
card_count[i + 4] += 1
# 策略2、出單張
card_count[i] -= 1
getMaxScore(card_count, unused_card_count - 1, i, score + i)
card_count[i] += 1
# 如果當(dāng)前牌的數(shù)量至少2張，那么可以出對(duì)子
if card_count[i] >= 2:
card_count[i] -= 2
getMaxScore(card_count, unused_card_count - 2, i, score + i * 2 * 2)
card_count[i] += 2
# 如果當(dāng)前牌的數(shù)量至少3張，那么可以出三張
if card_count[i] >= 3:
card_count[i] -= 3
getMaxScore(card_count, unused_card_count - 3, i, score + i * 3 * 2)
card_count[i] += 3
# 當(dāng)前當(dāng)前牌的數(shù)量至少4張，那么可以出炸彈
if card_count[i] >= 4:
card_count[i] -= 4
getMaxScore(card_count, unused_card_count - 4, i, score + i * 4 * 3)
card_count[i] += 4
# 算法入口
def getResult():
# 數(shù)組索引是牌面分?jǐn)?shù), 數(shù)組元素是牌面數(shù)量, 其中 0 索引不用
card_count = [0] * 14
# 統(tǒng)計(jì)各種牌的數(shù)量
for card in cards:
# 1-9輸入為數(shù)字1-9，10輸入為數(shù)字0，JQK輸入為大寫字母JQK
# 1-9 牌面分?jǐn)?shù)就是 1-9, 0的牌面分?jǐn)?shù)是 10, J=11,Q=12,K=13, 可以發(fā)現(xiàn)牌面分?jǐn)?shù)是連續(xù)的，可以和card_count數(shù)組的索引對(duì)應(yīng)起來(lái)
if card == '0':
card_count[10] += 1
elif card == 'J':
card_count[11] += 1
elif card == 'Q':
card_count[12] += 1
elif card == 'K':
card_count[13] += 1
else:
i = ord(card) - ord('0')
card_count[i] += 1
getMaxScore(card_count, len(cards), 1, 0)
return max_score
# 算法調(diào)用
print(getResult())
C算法源碼
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 15
#define CARD_KINDS 14
#define MAX(a, b) a > b ? a : b
void getMaxScore(int *card_count, int unused_card_count, int startIdx, int score);
int max_score = 0; // 保存最大分?jǐn)?shù)
int main() {
char cards[MAX_SIZE];
scanf("%s", cards);
// 數(shù)組索引是牌面分?jǐn)?shù), 數(shù)組元素是牌面數(shù)量, 其中 0 索引不用
int card_count[CARD_KINDS] = {0};
// 統(tǒng)計(jì)各種牌的數(shù)量
for (int i = 0; i < strlen(cards); i++) {
char card = cards[i];
// 1-9輸入為數(shù)字1-9，10輸入為數(shù)字0，JQK輸入為大寫字母JQK
// 1-9 牌面分?jǐn)?shù)就是 1-9, 0的牌面分?jǐn)?shù)是 10, J=11,Q=12,K=13, 可以發(fā)現(xiàn)牌面分?jǐn)?shù)是連續(xù)的，可以和card_count數(shù)組的索引對(duì)應(yīng)起來(lái)
switch (card) {
case '0':
card_count[10]++;
break;
case 'J':
card_count[11]++;
break;
case 'Q':
card_count[12]++;
break;
case 'K':
card_count[13]++;
break;
default:
card_count[card - '0']++;
}
}
getMaxScore(card_count, strlen(cards), 1, 0);
printf("%d\n", max_score);
return 0;
}
/**
* 獲取最大分?jǐn)?shù)
*
* @param card_count 各種牌的數(shù)量
* @param unused_card_count 剩余牌的總數(shù)量
* @param i 從哪個(gè)位置開(kāi)始選牌
* @param score 此時(shí)已獲得的總分?jǐn)?shù)
*/
void getMaxScore(int *card_count, int unused_card_count, int i, int score) {
// 所有牌都打完了
if (unused_card_count == 0) {
// 則比較此時(shí)出牌策略獲得的總分score，和歷史最高分max_score，保留較大者
max_score = MAX(score, max_score);
return;
}
// 沒(méi)有可以出的牌，則繼續(xù)遞歸到i+1開(kāi)始出牌
if(card_count[i] == 0) {
getMaxScore(card_count, unused_card_count, i + 1, score);
}
// 還有可以出的牌，則從i開(kāi)始出牌
// 如果當(dāng)前牌的數(shù)量至少1張
if (card_count[i] >= 1) {
// 策略1、可以嘗試出順子，由于最大的順子是9,10,J,Q,K,因此 i 作為順子起始牌的話，不能超過(guò)9，且后續(xù)牌面 i+1, i+2, i+3, i+4 的數(shù)量都至少有1張
if (i <= 9 && card_count[i + 1] >= 1 && card_count[i + 2] >= 1 && card_count[i + 3] >= 1 &&
card_count[i + 4] >= 1) {
card_count[i] -= 1;
card_count[i + 1] -= 1;
card_count[i + 2] -= 1;
card_count[i + 3] -= 1;
card_count[i + 4] -= 1;
// 順子是5張牌，因此出掉順子后，可用牌數(shù)量減少5張，總分增加 (i + (i+1) + (i+2) + (i+3) + (i+4)) * 2
getMaxScore(card_count, unused_card_count - 5, i, score + (5 * i + 10) * 2);
// 回溯
card_count[i] += 1;
card_count[i + 1] += 1;
card_count[i + 2] += 1;
card_count[i + 3] += 1;
card_count[i + 4] += 1;
}
// 策略2、出單張
card_count[i] -= 1;
getMaxScore(card_count, unused_card_count - 1, i, score + i);
card_count[i] += 1;
}
// 如果當(dāng)前牌的數(shù)量至少2張，那么可以出對(duì)子
if (card_count[i] >= 2) {
card_count[i] -= 2;
getMaxScore(card_count, unused_card_count - 2, i, score + i * 2 * 2);
card_count[i] += 2;
}
// 如果當(dāng)前牌的數(shù)量至少3張，那么可以出三張
if (card_count[i] >= 3) {
card_count[i] -= 3;
getMaxScore(card_count, unused_card_count - 3, i, score + i * 3 * 2);
card_count[i] += 3;
}
// 當(dāng)前當(dāng)前牌的數(shù)量至少4張，那么可以出炸彈
if (card_count[i] >= 4) {
card_count[i] -= 4;
getMaxScore(card_count, unused_card_count - 4, i, score + i * 4 * 3);
card_count[i] += 4;
}
}到了這里，關(guān)于華為OD機(jī)試 - 最佳的出牌方法（Java & JS & Python）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
