回复: 20
跳转到指定楼层
上一主题 下一主题
收起左侧

G vo

全局:

2022(4-6月) 码农类General 硕士 全职@google - 内推 - Onsite  | 😐 Neutral 😐 Average | WaitList | 应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
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].

评分

参与人数 5大米 +9 收起 理由
匿名用户-FQIPQ + 5
微信用户_ed1be9a + 1 给你点个赞!
neverlate + 1 很有用的信息!
Falldawn + 1 给你点个赞!
微信用户_b4a29f7 + 1 很有用的信息!

查看全部评分


上一篇:砖厂店面+虚拟表演
下一篇:【地里最全前端面试题型总结】
推荐
Falldawn 2022-7-2 00:54:07 | 只看该作者
全局:
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.         Set<Integer>[] sortedCards = new Set[15];
  7.         for (int i = 0; i < 15; i++) {
  8.             sortedCards[i] = new HashSet<>();
  9.         }
  10.         for (int[] card: cards) {
  11.             sortedCards[card[0]].add(card[1]);
  12.         }
  13.         List<List<int[]>> res = new ArrayList<>();
  14.         List<int[]> curHand = new ArrayList<>();
  15.         return canBreakFourHands(0, sortedCards, curHand, res);
  16.     }

  17.     private boolean canBreakFourHands(int hand, Set<Integer>[] sortedCards, List<int[]> curHand, List<List<int[]>> res) {
  18.         if (hand == 4) {
  19.             finalRes = new ArrayList<>(res);
  20.             return true;
  21.         }

  22.         for (int i = 2; i < 15; i++) {
  23.             if (sortedCards[i].isEmpty()) {
  24.                 continue;
  25.             }
  26.             if (sortedCards[i].size() == 4) {
  27.                 Set<Integer> colors = new HashSet<>(sortedCards[i]); // MUST DEEP COPY
  28.                 for (int color: colors) {
  29.                     curHand.add(new int[]{i, color});
  30.                 }
  31.                 res.add(new ArrayList<>(curHand));
  32.                 curHand.clear();
  33.                 sortedCards[i].clear();
  34.                 if (canBreakFourHands(hand + 1, sortedCards, curHand, res)) {
  35.                     return true;
  36.                 }
  37.                 sortedCards[i] = colors;
  38.                 res.remove(res.size() - 1);
  39.             }
  40.             if (i + 4 < 15) {
  41.                 Set<Integer> colors = new HashSet<>(sortedCards[i]);
  42.                 for (int color: colors) {
  43.                     if (sortedCards[i + 1].contains(color) && sortedCards[i + 2].contains(color) && sortedCards[i + 3].contains(color) && sortedCards[i + 4].contains(color)) {
  44.                         for (int j = 0; j < 5; j++) {
  45.                             curHand.add(new int[]{i + j, color});
  46.                             sortedCards[i + j].remove(color);
  47.                         }
  48.                         res.add(new ArrayList<>(curHand));
  49.                         curHand.clear();
  50.                        if (canBreakFourHands(hand + 1, sortedCards, curHand, res)) {
  51.                            return true;
  52.                        }
  53.                         for (int j = 0; j < 5; j++) {
  54.                             sortedCards[i + j].add(color);
  55.                         }
  56.                     }
  57.                 }
  58.             }
  59.         }
  60.         return false;
  61.     }
复制代码
回复

使用道具 举报

全局:
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;
    }
回复

使用道具 举报

🔗
lucius323 2022-6-30 12:51:16 | 只看该作者
全局:
谢谢分享,祝好运!
回复

使用道具 举报

🔗
neverlate 2022-7-1 00:49:02 | 只看该作者
全局:
已米,请教下第一个问题。
是不是问这20张牌能否组合4个顺子or炸?
回复

使用道具 举报

🔗
Falldawn 2022-7-1 00:53:17 | 只看该作者
全局:
多谢,请问第一题怎么做的
回复

使用道具 举报

🔗
Falldawn 2022-7-1 01:31:39 | 只看该作者
全局:
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
回复

使用道具 举报

🔗
Falldawn 2022-7-1 02:07:32 | 只看该作者
全局:
查了一下发现只有一副扑克
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
回复

使用道具 举报

🔗
 楼主| TXLX 2022-7-1 02:38:52 | 只看该作者
全局:
neverlate 发表于 2022-6-30 11:49
已米,请教下第一个问题。
是不是问这20张牌能否组合4个顺子or炸?

是的,我写错了,应该是straight flush or 4 of a kind
回复

使用道具 举报

🔗
 楼主| TXLX 2022-7-1 02:47:29 | 只看该作者
全局:
Falldawn 发表于 2022-6-30 11:53
多谢,请问第一题怎么做的

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

使用道具 举报

🔗
Falldawn 2022-7-1 05:05:17 | 只看该作者
全局:
TXLX 发表于 2022-6-30 11:47
loop20张的每一张开始进行查看,先查能否组成同花顺或炸弹,如能那么进入剩余15张牌情况,如再能发现同花 ...

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

使用道具 举报

🔗
Falldawn 2022-7-1 05:32:11 | 只看该作者
全局:
TXLX 发表于 2022-6-30 11:47
loop20张的每一张开始进行查看,先查能否组成同花顺或炸弹,如能那么进入剩余15张牌情况,如再能发现同花 ...

follow up这个思路很麻烦了吧,任意换嘛
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表