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

G vo

🔗
 楼主| TXLX 2022-7-1 06:46:50 | 只看该作者
全局:
Falldawn 发表于 2022-6-30 16:05
这就是DFS不断尝试了,每次都要次从开头遍历找

的确不一定是optimal solution,n=20, 不太在意速度。可能加上同花色分类再找同花顺,加上同数字分类再找炸弹,应该能好一些。
回复

使用道具 举报

🔗
louisgogogo 2022-7-1 08:14:18 | 只看该作者
全局:
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;
    }
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-HJUXT  2022-7-1 09:02:13
straight flush需要考虑 "A,2,3,4,5"这种情况吗
回复

使用道具 举报

🔗
Falldawn 2022-7-1 09:48:54 | 只看该作者
全局:
匿名用户 发表于 2022-6-30 18:02
straight flush需要考虑 "A,2,3,4,5"这种情况吗

这个不算吧
回复

使用道具 举报

🔗
Falldawn 2022-7-1 09:52:27 | 只看该作者
全局:
louisgogogo 发表于 2022-6-30 17:14
public boolean canWin(List cards) {     // int[0]  花色 0 ~3,  int[1] 点数  2 ~ 14
        Map boo ...

用2 ~14 代表 2 ~ 10 + J Q K A,其中A用14表示
recursion tree最多有4层
每层的节点最多2个分支,1~组成four of a kind, 2~往上组成同花顺
每个节点组成four of a kind时,记录结果最多4次
每个节点组成同花顺时,记录结果最多5次
所以时间复杂度为5 * 2 ^ 4 ~O(1),空间复杂度call stack 为O(4) ~ O(1),heap上只有复制结果时有,最多O(5) * 4层 = O(1)
下面代码为了验证结果正确,仅仅记录了一种结果finalRes,这里注意了,如果想记录多重结果,DFS函数就只能返回void,并且最终结果是现在finalRes的List。由于在DFS函数中curHand已经清空了所以不需要再吐了,因为这里传的是一个空
如果不记录结果,直接去掉curHand和res以及finalRes参数

follow up有些麻烦
  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> set = new HashSet<>(sortedCards[i]); // MUST DEEP COPY
  28.            for (int color: sortedCards[i]) {
  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] = set;
  38.            res.remove(res.size() - 1);
  39.        }
  40.        if (i + 4 < 15) {
  41.            for (int color: sortedCards[i]) {
  42.                if (sortedCards[i + 1].contains(color) && sortedCards[i + 2].contains(color) && sortedCards[i + 3].contains(color) && sortedCards[i + 4].contains(color)) {
  43.                    for (int j = 0; j < 5; j++) {
  44.                        curHand.add(new int[]{i + j, color});
  45.                        sortedCards[i + j].remove(color);
  46.                    }
  47.                    res.add(new ArrayList<>(curHand));
  48.                    curHand.clear();
  49.                   if (canBreakFourHands(hand + 1, sortedCards, curHand, res)) {
  50.                       return true;
  51.                   }
  52.                    for (int j = 0; j < 5; j++) {
  53.                        sortedCards[i + j].add(color);
  54.                    }
  55.                }
  56.            }
  57.        }
  58.    }
  59.    return false;
  60. }

复制代码
回复

使用道具 举报

🔗
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.     }
复制代码
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-UCQSH  2022-7-6 04:24:11
这个题停难写的,不过一般的texas holdem是把Ace当成两个数字处理的(1 or 14),所以(A,2,3,4,5)(10,J,Q,K,A)都算是straight,花色相同就是straight flush。
比较tricky的一点是four of a kind 只需要4+random, 而straight flush需要5张牌
回复

使用道具 举报

🔗
andyghw 2022-7-6 04:41:39 | 只看该作者
全局:
本帖最后由 andyghw 于 2022-7-5 13:45 编辑

第一题为什么不能用两个map解决呢,一个Map<Integer, Integer>存每张牌数字的个数,用来check 4 of a kind,另一个Map<String, Set<Integer>>存每个花色对应的牌的set,用来check royal flush(10 J Q K A)。
才看到lz改成了straight flush,nvm
回复

使用道具 举报

🔗
Falldawn 2022-7-9 05:33:55 | 只看该作者
全局:
本帖最后由 Falldawn 于 2022-7-8 14:42 编辑

3. coding -- given a dictionary of file tree, find entire size of the given file or directory(sum of the files in it). Follow up to implement a directory-delete function.

楼主,请问这个题要自己定义一个数据结构吧,你怎么写的?

感觉第一问就是DFS,检查当前节点是否file,是就加进去,BFS也可以。其实file就是leafNode,folder不是,所以就是求所有leafNode节点的和第二问不就是找到那个节点的母结点,断掉就行了嘛
  1. public int sumOfLeftLeaves(TreeNode root) {
  2.         if (root == null) return 0;
  3.         if (root.left == null && root.right == null) {
  4.             return root.val;
  5.         }
  6.         return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
  7.     }
复制代码
回复

使用道具 举报

🔗
Falldawn 2022-7-9 05:58:01 | 只看该作者
全局:
Falldawn 发表于 2022-7-8 14:33
3. coding -- given a dictionary of file tree, find entire size of the given file or directory(sum of ...

第二问类似1110. Delete Nodes And Return Forest
  1. public TreeNode delNodes(TreeNode root, int target) {
  2.         if (root.val == target)  {
  3.             return null;
  4.         }
  5.         return deleteNodes(root, target);
  6.     }

  7.     private TreeNode deleteNodes(TreeNode cur, int target) {
  8.         if (cur == null) {
  9.             return null;
  10.         }

  11.         if (cur.left != null && cur.left.val == target) {
  12.             cur.left = null;
  13.             return cur;
  14.         }

  15.         if (cur.right != null && cur.right.val == target) {
  16.             cur.right = null;
  17.             return cur;
  18.         }
  19.         cur.left = deleteNodes(cur.left, target);
  20.         cur.right = deleteNodes(cur.right, target);

  21.         return cur;
  22.     }
复制代码
回复

使用道具 举报

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

本版积分规则

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