G vo

1. coding -- check if the given 20 cards can be divided into 4 hands (Texas Holdem) which are either royal flush or 4 of a kind. Follow up to ch

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

[3,4,5,6,7]. Follow up to find longest sublist strictly increasing e.g. [3,4,5,6,7,9].

Falldawn 发表于 2022-6-30 18:52
用2 ~14 代表 2 ~ 10 + J Q K A，其中A用14表示
recursion tree最多有4层
每层的节点最多2个分支，1~组 ...

发现还是有个bug，第二个for循环没有deep copy
在DFS函数中for循环前必须DEEP COPY要循环的内容，因为在循环中修改了内容

1. public static List<List<int[]>> finalRes = new ArrayList<>();
   
2.     public boolean isFourHands(int[][] cards) {
   
3.         if (cards == null || cards.length == 0 || cards.length != 20) {
   
4.             return false;
   
5.         }
   
6. 
   
7.         Set<Integer>[] sortedCards = new Set[15];
   
8.         for (int i = 0; i < 15; i++) {
   
9.             sortedCards[i] = new HashSet<>();
   
10.         }
    
11.         for (int[] card: cards) {
    
12.             sortedCards[card[0]].add(card[1]);
    
13.         }
    
14.         List<List<int[]>> res = new ArrayList<>();
    
15.         List<int[]> curHand = new ArrayList<>();
    
16.         return canBreakFourHands(0, sortedCards, curHand, res);
    
17.     }
    
18. 
    
19.     private boolean canBreakFourHands(int hand, Set<Integer>[] sortedCards, List<int[]> curHand, List<List<int[]>> res) {
    
20.         if (hand == 4) {
    
21.             finalRes = new ArrayList<>(res);
    
22.             return true;
    
23.         }
    
24. 
    
25.         for (int i = 2; i < 15; i++) {
    
26.             if (sortedCards[i].isEmpty()) {
    
27.                 continue;
    
28.             }
    
29.             if (sortedCards[i].size() == 4) {
    
30.                 Set<Integer> colors = new HashSet<>(sortedCards[i]); // MUST DEEP COPY
    
31.                 for (int color: colors) {
    
32.                     curHand.add(new int[]{i, color});
    
33.                 }
    
34.                 res.add(new ArrayList<>(curHand));
    
35.                 curHand.clear();
    
36.                 sortedCards[i].clear();
    
37.                 if (canBreakFourHands(hand + 1, sortedCards, curHand, res)) {
    
38.                     return true;
    
39.                 }
    
40.                 sortedCards[i] = colors;
    
41.                 res.remove(res.size() - 1);
    
42.             }
    
43.             if (i + 4 < 15) {
    
44.                 Set<Integer> colors = new HashSet<>(sortedCards[i]);
    
45.                 for (int color: colors) {
    
46.                     if (sortedCards[i + 1].contains(color) && sortedCards[i + 2].contains(color) && sortedCards[i + 3].contains(color) && sortedCards[i + 4].contains(color)) {
    
47.                         for (int j = 0; j < 5; j++) {
    
48.                             curHand.add(new int[]{i + j, color});
    
49.                             sortedCards[i + j].remove(color);
    
50.                         }
    
51.                         res.add(new ArrayList<>(curHand));
    
52.                         curHand.clear();
    
53.                        if (canBreakFourHands(hand + 1, sortedCards, curHand, res)) {
    
54.                            return true;
    
55.                        }
    
56.                         for (int j = 0; j < 5; j++) {
    
57.                             sortedCards[i + j].add(color);
    
58.                         }
    
59.                     }
    
60.                 }
    
61.             }
    
62.         }
    
63.         return false;
    
64.     }

复制代码

public boolean canWin(List<int[]> cards) {     // int[0]  花色 0 ~3，  int[1] 点数  2 ~ 14
        Map<Integer, Integer> boom = new HashMap<>(); // 存重复数
        List<Integer>[] cardList = new List[4];
        for (List<Integer> list: cardList) {
            list = new ArrayList<>();
        }
        for (int[] card: cards) {
            boom.put(card[1], boom.getOrDefault(card[1], 0) + 1); //有炸弹？
            if (boom.get(card[1]) == 4) {
                return true;
            }
            cardList[card[0]].add(card[1]);
        }
        // 遍历4个花色
        int flushNum = 0;
        int falseIndex = 0;  // 找出哪个index没有同花顺
        
        for (int i = 0; i < 4; i++) {
            if (findFlush(cardList[i])) {
                flushNum++;
            } else {
                falseIndex = i;
            }
        }
        if (flushNum == 4) {
            return true;
        } else if (flushNum < 3) {
            return false;
        }
        //开始replace,  反正牌多 多出20 - 15（3个同花顺） = 5张， 直接加，不减
        for (int i = 2; i <= 14; i++) {
            cardList[falseIndex].add(i);
            if (findFlush(cardList[falseIndex])) {
                return true;
            }
            cardList[falseIndex].remove(i);
        }
        
        return false;
    }
    private boolean findFlush(List<Integer> cards) {
        Collections.sort(cards);
        int count = 1;
        for (int i = 1; i < cards.size(); i++) {
            if (cards.get(i) == cards.get(i - 1) + 1) {
                count++;
                if (count == 5) {
                    return true;
                }
            } else {
                count = 1;
            }
        }
        return false;
    }

谢谢分享，祝好运！

已米，请教下第一个问题。
是不是问这20张牌能否组合4个顺子or炸？

多谢，请问第一题怎么做的

neverlate 发表于 2022-6-30 09:49
已米，请教下第一个问题。
是不是问这20张牌能否组合4个顺子or炸？

Royal Flush是 10 ~ A的同花顺，4 of a kind是炸
https://zh.wikipedia.org/wiki/%E ... B%E7%89%8C%E5%9E%8B

查了一下发现只有一副扑克
Only one deck is in play at a given time, and it’s very important that it’s only one

所以算法如下：
遍历，记录牌和对应的花色，可以用List<List>或者List[]
记录有牌面数字出现4次的个数x
if x = 0，那简单，必须有4个royal flush，也就是 10 - A必须都出现4次，但这就违背了x = 0，所以不可能 x = 0
else if x = 1
if 这个数字 < 10，那就10 - A必须都出现3次
else 不可能
else if x = 2
if 这2个数字 < 10，那就10 - A必须都出现2次
else 不可能
else if x = 3 这3个数字 < 10，那就10 - A必须都出现1次
if 这3个数字 < 10，那就10 - A必须都出现1次
else 不可能
else if x >= 4, return true

Follow up to check if it will work by replacing only one card?

这里只可能增加1个Four of a kind或Royal Flush，所以可能情况如下：

3 * Four of a kind + 0 * Royal Flush，缺一个Four of a kind或Royal Flush
2 * Four of a kind + 1 * Royal Flush，缺一个Four of a kind或Royal Flush
1 * Four of a kind + 2 * Royal Flush，缺一个Four of a kind或Royal Flush
0 * Four of a kind + 3 * Royal Flush，缺一个Four of a kind或Royal Flush

neverlate 发表于 2022-6-30 11:49
已米，请教下第一个问题。
是不是问这20张牌能否组合4个顺子or炸？

是的，我写错了，应该是straight flush or 4 of a kind

Falldawn 发表于 2022-6-30 11:53
多谢，请问第一题怎么做的

loop20张的每一张开始进行查看，先查能否组成同花顺或炸弹，如能那么进入剩余15张牌情况，如再能发现同花顺或炸弹，则进入10张牌情况，然后进入5张牌情况，最后是0张牌请况。ok
follow up也是这个思路

TXLX 发表于 2022-6-30 11:47
loop20张的每一张开始进行查看，先查能否组成同花顺或炸弹，如能那么进入剩余15张牌情况，如再能发现同花 ...

这就是DFS不断尝试了，每次都要次从开头遍历找

TXLX 发表于 2022-6-30 11:47
loop20张的每一张开始进行查看，先查能否组成同花顺或炸弹，如能那么进入剩余15张牌情况，如再能发现同花 ...

follow up这个思路很麻烦了吧，任意换嘛