G vo

Falldawn 发表于 2022-6-30 16:05
这就是DFS不断尝试了，每次都要次从开头遍历找

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

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;
    }

straight flush需要考虑 "A,2,3,4,5"这种情况吗

匿名用户 发表于 2022-6-30 18:02
straight flush需要考虑 "A,2,3,4,5"这种情况吗

这个不算吧

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

复制代码

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.     }

复制代码

这个题停难写的，不过一般的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张牌

第一题为什么不能用两个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

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-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. 
   
8.     private TreeNode deleteNodes(TreeNode cur, int target) {
   
9.         if (cur == null) {
   
10.             return null;
    
11.         }
    
12. 
    
13.         if (cur.left != null && cur.left.val == target) {
    
14.             cur.left = null;
    
15.             return cur;
    
16.         }
    
17. 
    
18.         if (cur.right != null && cur.right.val == target) {
    
19.             cur.right = null;
    
20.             return cur;
    
21.         }
    
22.         cur.left = deleteNodes(cur.left, target);
    
23.         cur.right = deleteNodes(cur.right, target);
    
24. 
    
25.         return cur;
    
26.     }

复制代码