每日第1題為中文站(LCCN) ，第2題為英文站(LCUS) ，題目連結皆統一為英文站的題目連結。
Easy 、Medium 、Hard 難度的題目分別用🟢🟡🔴表示。
若為周賽題目會額外標註由 @zreotrac 零神計算的rating分數。

All problems solved by python

2023-11-01

🔴 2127. Maximum Employees to Be Invited to a Meeting 2449

美好的一個月要從內向基環樹開始 (X)。
不得不說這題是超過我的能力範圍了，看了幾篇題解，還是似懂非懂，只能先記錄下來。

題意

  • 有 nn 名員工要參加會議，會議桌是圓形的，且可以坐下任意數目的人。
  • 每個員工都有一位喜歡的員工，且喜歡的員工不會是自己，只有旁邊坐在喜歡員工的旁邊時，該員工才會參加會議。
  • 給定 favoritefavorite ，其中 favorite[i]favorite[i] 表示第 i 位員工喜歡的員工，請問最多有幾位員工可以參加會議？

思路：內向基環樹

  • 將每個員工視為圖上的一個點，並且從 ii 向 favorite[i]favorite[i] 連一條有向邊，則可以得到一張有向圖。由於每個大小為 kk 的連通塊都有 kk 個點和 kk 條邊，所以每個連通塊必定有且僅有一個環 ，且由於每個點的出度均為11，這樣的有向圖又叫做內向基環樹(pseudotree)，由基環樹組成的森林叫基環樹森林(pseudoforest)。
    • 「內向」是指樹中任意節點有且只有一條出邊，對應的「外向」是指樹中任意節點有且只有一條入邊。
    • 每一個內向基環樹（連通塊）都由一個基環和其餘指向基環的樹枝組成。
    • 需要注意，基環可能只包含兩個節點 。
  • 對於基環長度 >2>2 的情況，圓桌的最大員工數目即為最大的基環長度，記作 maxRingSize\textit{maxRingSize} 。
  • 對於基環長度 =2=2 的情況，其基環與兩側最長鏈拼起來，也就是為該基環樹所能組成的圓桌的最大員工數。而對於多個基環長度等於 22 的基環樹，每個基環樹所對應的鏈，都可以拼在其餘鏈的末尾，因此可以將這些鏈全部拼成一個圓桌，其大小記作 sumChainSize\textit{sumChainSize}。
  • 由於每個點的出度均為 11，所以可以統計其 in-degree\textit{in-degree} ，從入度為 00 的點開始對圖進行拓撲排序，剩餘的點都是基環上的點，
  • 在 拓撲排序 的過程中，對非基環上的點，建立一個反向圖，用作查詢基環上的點上最長鏈的長度。

參考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        n = len(favorite)
        indeg = [0] * n # in-degree
        for f in favorite:
            indeg[f] += 1

        rg = [[] for _ in range(n)] # reverse graph
        q = deque(i for i, deg in enumerate(indeg) if deg == 0)
        while q: # topological sort, BFS，剪枝
            x = q.popleft()
            y = favorite[x] # 根據題意，x 的最愛是 y，所以只有一條out-edge
            rg[y].append(x) # 反向建圖
            indeg[y] -= 1
            if indeg[y] == 0:
                q.append(y)

        # 通過 reverse graph，找到最深的路徑
        def rdfs(x: int) -> int:
            max_depth = 1
            for son in rg[x]:
                max_depth = max(max_depth, rdfs(son) + 1)
            return max_depth

        max_ring_size = sum_chain_size = 0
        for i, d in enumerate(indeg): # 遍歷所有基環上的點
            if d == 0: # 入度為0代表非基環上的點，則跳過，或者已經訪問過，也跳過
                continue

            # 遍歷基環上的點
            indeg[i] = 0 # 將基環上的點的入度標記為 0，避免重複訪問
            ring_size = 1 # 基環長度
            x = favorite[i] 
            while x != i:
                indeg[x] = 0 # 將基環上的點的in-degree標記為 0，避免重複訪問
                ring_size += 1
                x = favorite[x]

            if ring_size == 2: # 基環長度為 2，則兩條最長路徑的長度之和即為答案
                sum_chain_size += rdfs(i) + rdfs(favorite[i]) # 累加兩條最長路徑的長度
            else:
                max_ring_size = max(max_ring_size, ring_size) # 取所有基環長度的最大值
        return max(max_ring_size, sum_chain_size)

🟢 501. Find Mode in Binary Search Tree

題意

  • 給定一個包含重複值的BST的根 rootroot ，找出並返回BST中的所有眾數（即出現頻率最高的元素）。
  • 如果樹中有不只一個眾數，可以依任意順序傳回。
  • 進階：不使用額外的空間（假設由遞歸產生的隱式呼叫堆疊的開銷不被計算在內）

思路：Counter / Inorder Traversal

  • 以任意方式訪問一次BST，並計算每個值出現的次數，最後返回出現次數最多的值，但這樣的話空間複雜度就是 O(n)O(n) 了。
  • 利用BST的中序遍歷，可以得到一個遞增的序列，並且相同的值會連續出現，因此可以在遍歷的過程中計算每個值出現的次數，並且在遍歷的過程中更新眾數。
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        cnt = Counter()
        def dfs(node):
            if node:
                cnt[node.val] += 1
                dfs(node.left)
                dfs(node.right)
        dfs(root)
        maxCnt = max(cnt.values())
        return [k for k, v in cnt.items() if v == maxCnt]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        base, cnt, maxCnt = 0, 0, 0

        def update(x):
            nonlocal ans, base, cnt, maxCnt
            if x == base:
                cnt += 1
            else:
                cnt = 1
                base = x
            if cnt == maxCnt:
                ans.append(base)
            if cnt > maxCnt:
                maxCnt = cnt
                ans = [base]

        def dfs(root: Optional[TreeNode]):
            if not root:
                return
            dfs(root.left)
            update(root.val)
            dfs(root.right)

        dfs(root)
        return ans

2023-11-02

🟢 2103. Rings and Rods 1258

題意

  • 總計有 nn 個物品，物品的種類有三種，分別以 ′R′'R'、′G′'G'、′B′'B' 表示，並且每個物品都被放置在編號 ii 的箱子內，其中 0≤i≤90 \leq i \leq 9 。
  • 給你一個長度為 2n 的字串 ringsrings ，rings[2∗i]rings[2*i] 表示第 ii 個物品的顏色，rings[2∗i+1]rings[2*i+1] 表示第 ii 個物品所在的箱子編號。
  • 求包含所有種類物品的箱子，並返回這種箱子的數量。

思路：計數

直接統計每個箱子內每種物品的數量，然後遍歷所有箱子，檢查每種物品的數量是否都 >0>0 。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def countPoints(self, rings: str) -> int:
        n = len(rings) // 2
        cnt = [defaultdict(int) for _ in range(10)]
        for i in range(n):
            color, pos = rings[2*i], rings[2*i+1]
            cnt[int(pos)][color] += 1
        ans = 0
        for i in range(10):
            if cnt[i]['R'] > 0 and cnt[i]['G'] > 0 and cnt[i]['B'] > 0:
                ans += 1
        return ans

🟡 2265. Count Nodes Equal to Average of Subtree 1473

題意

  • 給定一棵Binary Tree的根 rootroot ，找出並返回滿足要求的節點數，要求節點的值等於其子樹中所有值的平均值。
  • 注意：nn 個元素的平均值可以由 nn 個元素求和然後再除以 nn ，並向下捨入到最近的整數。
  • rootroot 的子樹由 rootroot 和它的所有後代組成。

思路：DFS

在遍歷的過程中，對每個節點，計算其子樹的和 ss 和節點數 cc ，如果 s//c==root.vals // c == root.val ，則答案 +1+1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(root: int) -> [int, int]:
            nonlocal ans
            if not root:
                return 0, 0 # sum, cnt
            ls, lc = dfs(root.left)
            rs, rc = dfs(root.right)
            s = ls + rs + root.val # 子樹的和
            c = lc + rc + 1 # 子樹的節點數
            if s // c == root.val:
                ans += 1
            return s, c
        dfs(root)
        return ans

2023-11-03

🟡 117. Populating Next Right Pointers in Each Node II

題意

給定一個 Binary Tree 的根 rootroot ，將每個節點的 next 指針指向其下一個右側節點。如果找不到下一個右側節點，則將 next 指標設為 NULL 。

思路：Level Order Traversal (BFS)

用BFS做Level Order Traversal遍歷每一層，在訪問每層第1個節點前，queuequeue的大小為本層的節點數量。在遍歷的過程中，將每個節點的 next 指向下一個節點即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        q = deque([root])
        while q:
            size = len(q)
            for i in range(size):
                node = q.popleft()
                if i < size - 1:
                    node.next = q[0]
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return root

🟡 1441. Build an Array With Stack Operations 1180

題意

  • 給定一個Array targettarget 和一個整數 nn。每次操作中，可以將 [1,n][1, n] 中下一個整數 push 到 stackstack 中，或者從 stackstack 中 pop 掉最後面的元素，返回操作成 targettarget 的操作順序，如果存在多個可行方案，返回任一即可。
  • 題目資料保證目標陣列嚴格遞增，並且只包含 1 到 n 之間的數字。

思路：模擬

  • 由於題目資料保證目標陣列嚴格遞增，因此可以直接模擬操作過程，並且在過程中檢查是否與目標陣列相同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        ans = []
        idx = 0 # target[idx] is the next target
        for i in range(1, n+1): # i is the current number
            if idx == len(target):
                break
            if i == target[idx]:
                ans.append("Push")
                idx += 1
            else:
                ans.append("Push")
                ans.append("Pop")
        return ans

2023-11-04

🟡 421. Maximum XOR of Two Numbers in an Array

題意

給你一個整數Array numsnums ，傳回 nums[i]XORnums[j]nums[i] XOR nums[j] 的最大運算結果，其中 0≤i≤j<n0 ≤ i ≤ j < n 。

思路

<++>

參考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    """
        1. XOR + Greedy + bit mask
        
    """
    def findMaximumXOR(self, nums: List[int]) -> int:
        ans = 0
        mask = 0
        for bit in range(30, -1, -1): # Greedy，逐位確定最大值
            mask |= (1 << bit)

            seen = set()
            for num in nums:
                seen.add(mask & num)

            temp = ans | (1 << bit) # 逐位確定最大值

            for prefix in seen:
                if temp ^ prefix in seen:
                    ans = temp
                    break
        return ans

🟡 1503. Last Moment Before All Ants Fall Out of a Plank 1619

題意

<++>

思路：腦筋急轉彎

<++>

類題

1
2
3
class Solution:
    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
        return max(max(left + [0]), n-min(right + [n]))

2023-11-

🟢🟡🔴 XXXX rating

題意

思路

1

🟢🟡🔴 XXXX rating

題意

<++>

思路

<++>

1

寫在最後

瞧瞧你發現了什麼？你看，是一串魔法咒語！

1
2
3
(masterpiece, best quality), 1girl, solo, cowboy_shot Musician, Musical attire, Recording studio, Composing music, Performing live, playing guitar, Collaborating with other musicians, gotou1, gotou1, gotou hitori, solo, skirt, pink jacket, track jacket, bangs, hair between eyes, long sleeves, <lora:gotou_hitori_v1:0.800000>
Negative prompt: (worst quality,  low quality:1.4),  negative_hand-neg,  EasynegativeV2,  bad-artist-anime,  verybadimagenegative_v1.3,  bad_prompt_version2
Steps: 45, Sampler: DPM++ 2M Karras, CFG scale: 8.0, Seed: 1083072644, Size: 960x540, Model: EMS-8822-EMS, VAE: ClearVAE.safetensors, Denoising strength: 0.5, Style Selector Enabled: True, Style Selector Randomize: False, Style Selector Style: base, Hires resize: 1920x1080, Hires steps: 30, Hires upscaler: 4x-AnimeSharp, Lora hashes: "EMS-2893-EMS: 1757182f367d", TI hashes: "negative_hand-neg, EasyNegativeV2, bad-artist-anime, verybadimagenegative_v1.3, bad_prompt_version2", Version: v1.6.0.96-8-g0d823e6, TaskID: 668018464237043112, Used Embeddings: "negative_hand-neg, EasyNegativeV2, bad-artist-anime, verybadimagenegative_v1.3, bad_prompt_version2, negative_hand-neg, EasyNegativeV2, bad-artist-anime, verybadimagenegative_v1.3, bad_prompt_version2"